中國大學MOOC_浙大資料結構_第三周程式設計作業

索引

1、樹的同構
2、List Leaves
3、Tree Traversals Again
用堆棧實作後序周遊的非遞歸程式

第三周程式設計作業

利用結構數組表示二叉樹。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // bool true false
#define MAX 10 + 1
#define SIZE 26 + 1
#define NONE -1

struct RawData {
    char ch;
    int left;
    int right; // 用 -1 表示不存在 
};
typedef struct RawData* MyRawData;

struct Tree {
    int a;
    int b;
};
typedef struct Tree* MyTree;

MyRawData mrds1[MAX];
MyRawData mrds2[MAX];
MyTree tr1[SIZE] = {NULL};
MyTree tr2[SIZE] = {NULL};

void rawData2tree(int N, MyRawData mrds[], MyTree tr[])
{
    int k, temp;
    for (int i = 0; i != N; ++i) {
        // 1. 計算字母所對應的下标 
        k = mrds[i]->ch - 'A';    
        
        // 2. 初始化結點 
        tr[k] = (MyTree) malloc(sizeof(struct Tree));
        tr[k]->a = NONE;
        tr[k]->b = NONE;    
        
        // 3. 将子結點資訊儲存到目前下标的結點 
        if (mrds[i]->left != NONE) {
            tr[k]->a = mrds[mrds[i]->left]->ch;
            // 将 結點值 直接儲存到 a b 
        }
        if (mrds[i]->right != NONE) {
            tr[k]->b = mrds[mrds[i]->right]->ch;
        }        
        
        // 4. 排序便于比較
        if (tr[k]->a < tr[k]->b) {
            temp = tr[k]->a;
            tr[k]->a = tr[k]->b;
            tr[k]->b = temp;
        }
    }
}

bool check(MyTree tr1[], MyTree tr2[])
{
    for (int i = 0; i != SIZE; ++i) {
        if (tr1[i]) {
            // 相同結點是否存在? 
            if (tr2[i]) {
                // 其子結點是否一緻
                if (tr1[i]->a == tr2[i]->a && tr1[i]->b == tr2[i]->b) { 
                    // 
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
    }
    
    return true;
}

int main()
{
    int N;
    
    scanf("%d\n", &N); // \n不能漏！！！否則會被下面的scanf("%c", &c)讀走！ 
    
    // 1. 儲存原始資料 
    char c1, c2, c3;
    for (int i = 0; i != N; ++i) {
        mrds1[i] = (MyRawData) malloc(sizeof(struct RawData));
        scanf("%c %c %c\n", &c1, &c2, &c3);
        mrds1[i]->ch = c1;
        mrds1[i]->left = c2 == '-' ? NONE : c2 - '0'; 
        mrds1[i]->right = c3 == '-' ? NONE : c3 - '0';
    }
    
    int N2;
    scanf("%d\n", &N2);
    if (N != N2) {
        printf("No");
        return 0;
    }
    for (int i = 0; i != N2; ++i) {
        mrds2[i] = (MyRawData) malloc(sizeof(struct RawData));
        scanf("%c %c %c\n", &c1, &c2, &c3);
        mrds2[i]->ch = c1;
        mrds2[i]->left = c2 == '-' ? NONE : c2 - '0'; 
        mrds2[i]->right = c3 == '-' ? NONE : c3 - '0';
    }    
    
    
    // 2. 将樹映射到以 結點值 為下标的數組中 
    rawData2tree(N, mrds1, tr1);
    rawData2tree(N, mrds2, tr2);
    
    // 3. 同一 下标的結點應該具有相同的子結點
    printf("%s\n", check(tr1, tr2) ? "Yes" : "No");
    return 0;
}

層序周遊

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // bool true false
#include <memory.h> // memset 或者 <string.h> 
#define MAX_SIZE 10 + 1


int L[MAX_SIZE] = {-1}, R[MAX_SIZE] = {-1};
// R[MAX_SIZE] = {-1} 隻有首個元素被初始化為 -1  

int buildTree()
{
    memset(L, -1, sizeof(L));
    memset(R, -1, sizeof(R));

    int N, tmpL, tmpR;
            
    scanf("%d\n", &N);        
    for (int i = 0; i != N; ++i) { 
        scanf("%c %c\n", &tmpL, &tmpR);
        
        if (tmpL != '-') {
            L[i] = tmpL - '0'; 
        }
        
        if (tmpR != '-') {
            R[i] = tmpR - '0';
        }
    }
    
    int root;
    int flag[MAX_SIZE];
    memset(flag, 0, sizeof(flag));
    for (int i = 0; i != N; ++i) {
        if (L[i] != -1) flag[L[i]] = 1;
        if (R[i] != -1) flag[R[i]] = 1;
    }
    for (int i = 0; i != N; ++i) {
        if (flag[i] == 0) {
            root = i;
            break;
        }
    }
    
    return root;    
}

struct _Queue {
    int data[MAX_SIZE];
    int front, rear;
};
typedef struct _Queue* Queue;

Queue buildQueue()
{
    Queue q = (Queue) malloc(sizeof(struct _Queue));
    q->front = q->rear = -1;
    return q;
}

void push(Queue q, int x)
{
    q->rear++;
    q->data[q->rear] = x;
}

int pop(Queue q)
{
    if (q->front + 1 > q->rear) return -1;
    q->front++;
    return q->data[q->front];
}

int ans[MAX_SIZE];
void levelOrderTraversal(int root)
{
    memset(ans, -1, sizeof(ans));
    
    Queue q = buildQueue();
    push(q, root);
    int x , i = 0;
    while ((x = pop(q)) != -1) {
        if (L[x] != -1) {
            push(q, L[x]);
        }
        if (R[x] != -1) {
            push(q, R[x]);
        }
        if (L[x] == -1 && R[x] == -1) {
            ans[i++] = x;
        }
    }
}

void printAns()
{
    int k = 0;
    printf("%d", ans[0]);
    while (ans[++k] != -1) {
        printf(" %d", ans[k]);
    }    
}

int main()
{
    int root = buildTree();
    levelOrderTraversal(root);
    printAns();    
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> 
#include <string.h> 
#define MAX 100

typedef struct _BinTree* BinTree;
typedef BinTree Node;
struct _BinTree {
    int data;
    BinTree left;
    BinTree right;
    bool visited;
};

Node buildNode(int data)
{
    Node node = (Node) malloc(sizeof(struct _BinTree));
    node->data = data;
    node->left = NULL;
    node->right = NULL;    
    node->visited = false;
    
    return node;
}

typedef struct _Stack* Stack;
struct _Stack {
    Node nodes[MAX];
    int top;
};

Stack buildStack()
{
    Stack s = (Stack) malloc(sizeof(struct _Stack));
    s->top = -1;
    
    return s;
}

bool push(Stack s, Node node)
{
    if (s->top == MAX - 1) return false;
    s->nodes[++(s->top)] = node;
    
    return true;
}

bool isEmpty(Stack s)
{
    return s->top == -1;
}

Node getTop(Stack s)
{
    if (isEmpty(s)) return NULL;
    return s->nodes[s->top];
}

Node pop(Stack s)
{
    if (isEmpty(s)) return NULL;
    return s->nodes[(s->top)--];
}

int ans[MAX];
int ans_i = 0;
void postTraversal(Node root)
{
    if (root) {
        postTraversal(root->left);
        postTraversal(root->right);
        ans[ans_i++] = root->data;
    }
}

int main()
{
    BinTree root, tempNode, lastPop = NULL;
    int n, tempData;
    char ch[5];
    
    scanf("%d", &n);
    scanf("%s %d", ch, &tempData);
    root = buildNode(tempData);
    
    Stack s = buildStack();
    push(s, root);
    // 邊模拟入棧出棧邊構造樹。
    for (int i = 1; i != 2*n; ++i) {
        scanf("%s", ch);
        if (ch[1] == 'u') {
            scanf("%d", &tempData);
            tempNode = buildNode(tempData);            
            if (lastPop != NULL) {
                lastPop->right = tempNode;
                lastPop = NULL;
            } else {
                getTop(s)->left = tempNode;
            }
            push(s, tempNode);
        }
        if (ch[1] == 'o') {
            lastPop = pop(s);
        }
    }
    
    postTraversal(root);
    for (int i = 0; i != n - 1; ++i) {
        printf("%d ", ans[i]);
    }
    printf("%d", ans[n - 1]);
    
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> 
#include <string.h> 
#define MAX 100

typedef struct _BinTree* BinTree;
struct _BinTree {
    int data;
    BinTree left;
    BinTree right;
};

typedef struct _Block* Block;  
struct _Block { // 代碼塊
    BinTree node;
    int statement; 
};

typedef struct _Stack* Stack;
struct _Stack {
    Block blocks[MAX];
    int top;
};

BinTree buildNode(int data)
{
    BinTree node = (BinTree) malloc(sizeof(struct _BinTree));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    
    return node;
}

Stack buildStack()
{
    Stack s = (Stack) malloc(sizeof(struct _Stack));
    s->top = -1;
    
    return s;
}

bool push(Stack s, Block b)
{
    if (s->top == MAX - 1) return false;
    s->blocks[++(s->top)] = b;
    
    return true;
}

bool isEmpty(Stack s)
{
    return s->top == -1;
}

Block getTop(Stack s)
{
    if (isEmpty(s)) return NULL;
    return s->blocks[s->top];
}

Block pop(Stack s)
{
    if (isEmpty(s)) return NULL;
    return s->blocks[(s->top)--];
}

Block buildBlock(BinTree node)
{
    Block b = (Block) malloc(sizeof(struct _Block));
    b->node = node;
    b->statement = 0;
    
    return b;
}

void inorderTraversal(BinTree root)
{
    Block first = buildBlock(root);
    
    Stack s = buildStack();
    push(s, first);
    
    Block curBlock;
    BinTree curNode;
    while (!isEmpty(s)) {
        curBlock = getTop(s);
        curNode = curBlock->node;
        if (curBlock->statement == 0) {    
            curBlock->statement++;        
            if (curNode->left != NULL) {
                push(s, buildBlock(curNode->left));                
                continue; 
                // 将目前代碼塊暫時壓入棧底，執行新的代碼塊 
            }
        }
        if (curBlock->statement == 1) {
            curBlock->statement++;
            printf("%d ", curNode->data);            
        }
        if (curBlock->statement == 2) {
            curBlock->statement++;    
            if (curNode->right != NULL) {                
                push(s, buildBlock(curNode->right));
                continue;
            }        
        }
        pop(s); // 目前代碼塊相當于執行完了 
    }    
    printf("(inorderTraversal)\n");
} 

void postorderTraversal(BinTree root)
{
    Block first = buildBlock(root);
    
    Stack s = buildStack();
    push(s, first);
    
    Block curBlock;
    BinTree curNode;
    while (!isEmpty(s)) {
        curBlock = getTop(s);
        curNode = curBlock->node;
        if (curBlock->statement == 0) {    
            curBlock->statement++;        
            if (curNode->left != NULL) {
                push(s, buildBlock(curNode->left));                
                continue; 
                // 将目前代碼塊暫時壓入棧底，執行新的代碼塊 
            }
        }
        if (curBlock->statement == 1) {
            curBlock->statement++;
            if (curNode->right != NULL) {                
                push(s, buildBlock(curNode->right));
                continue;
            }    
        
        }
        if (curBlock->statement == 2) {
            curBlock->statement++;
            printf("%d ", curNode->data);        
        }
        pop(s); 
        // 壓入棧底是因為沒有執行完，而彈出則表示代碼塊執行完了。 
    }    
    printf("(postorderTraversal)\n");
} 

int main()
{
    BinTree root = buildNode(1);
    // 手動建立一棵樹
    BinTree node2 = buildNode(2);
    BinTree node3 = buildNode(3);
    BinTree node4 = buildNode(4);
    BinTree node5 = buildNode(5);
    BinTree node6 = buildNode(6);
    root->left = node2;
    root->right = node5;
    node2->left = node3;
    node2->right = node4;    
    node5->left = node6;
         
    inorderTraversal(root);
    postorderTraversal(root);
    
    return 0;
}

中國大學MOOC_浙大資料結構_第三周程式設計作業

索引

第三周程式設計作業

繼續閱讀

UVA 590 Always on the run

FZU 1978 Repair the brackets

UVA 10344- 23 out of 5

ZOJ 3935 2016

POJ 2115 C Looooops

HDU 5381 The sum of gcd

ZOJ 1104 Leaps Tall Buildings

ZOJ 3700 Ever Dream

HDU 2821 Pusher

ZOJ 1199 Point of Intersection

UVA 1401 Remember the Word

UVA 620 Cellular Structure

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

UVA 519 Puzzle (II)

開源按鍵元件Multi_Button的使用,含測試工程