資料結構：二叉樹三種遍歷算法 (遞歸/非遞歸/層次) 完整實作

資料結構：二叉樹三種遍歷算法 (遞歸/非遞歸/層次) 完整實作

中序遍歷 (LDR)

遞歸版

void InorderTraverse(BTNode *T) {
    if (T == NULL) return;
    InorderTraverse(T->Lchild);
    visit(T->data);
    InorderTraverse(T->Rchild);
}

非遞歸版 (堆疊模擬)

#define MAX_STACK_SIZE 50
void InorderTraverse(BTNode *T) {
    BTNode *Stack[MAX_STACK_SIZE], *p = T;
    int top = 0;
    if (T == NULL) { printf("Empty!\n"); return; }
    do {
        while (p != NULL) { Stack[++top] = p; p = p->Lchild; }
        if (top == 0) break;
        p = Stack[top--];
        visit(p->data);
        p = p->Rchild;
    } while (1);
}

後序遍歷 (LRD)

遞歸版

void PostorderTraverse(BTNode *T) {
    if (T != NULL) {
        PostorderTraverse(T->Lchild);
        PostorderTraverse(T->Rchild);
        visit(T->data);
    }
}

非遞歸版 (雙堆疊 + 標記)

#define MAX_STACK_SIZE 50
void PostorderTraverse(BTNode *T) {
    BTNode *S1[MAX_STACK_SIZE], *p = T;
    int S2[MAX_STACK_SIZE], top = 0;
    if (T == NULL) { printf("Empty!\n"); return; }
    do {
        while (p != NULL) {
            S1[++top] = p; S2[top] = 0; p = p->Lchild;
        }
        if (top == 0) break;
        if (S2[top] == 0) {
            p = S1[top]->Rchild; S2[top] = 1;
        } else {
            p = S1[top--]; visit(p->data); p = NULL;
        }
    } while (1);
}

層次遍歷 (Level Order)

隊列實作

#define MAX_NODE 50
void LevelorderTraverse(BTNode *T) {
    BTNode *Queue[MAX_NODE], *p = T;
    int front = 0, rear = 0;
    if (p != NULL) {
        Queue[++rear] = p;
        while (front < rear) {
            p = Queue[++front];
            visit(p->data);
            if (p->Lchild != NULL) Queue[++rear] = p->Lchild;
            if (p->Rchild != NULL) Queue[++rear] = p->Rchild;
        }
    }
}

遍歷算法應用實例

1. 前序建立二叉樹 (擴充二叉樹，# 表空)

#define NULLKY '?'
BTNode *Preorder_Create_BTree(BTNode *T) {
    char ch = getchar();
    if (ch == NULLKY) { T = NULL; return T; }
    T = (BTNode*)malloc(sizeof(BTNode));
    T->data = ch;
    Preorder_Create_BTree(T->Lchild);
    Preorder_Create_BTree(T->Rchild);
    return T;
}

2. 求葉子節點數 (非遞歸先序)

int BiTreeLeaves(BTNode *T) {
    BTNode *stack[MAX_STACK_SIZE], *p = T;
    int top = 0, num = 0;
    if (T != NULL) { stack[++top] = p; }
    while (top > 0) {
        p = stack[top--];
        if (p->Lchild == NULL && p->Rchild == NULL) num++;
        if (p->Rchild != NULL) stack[++top] = p->Rchild;
        if (p->Lchild != NULL) stack[++top] = p->Lchild;
    }
    return num;
}

3. 求樹深度

層次遍歷法：記錄每層最後節點位置

int BiTreeDepth(BTNode *T) {
    BTNode *Queue[MAX_NODE], *p = T;
    int front = 0, rear = 0, depth = 0, level = 0;
    if (T != NULL) {
        Queue[++rear] = p; level = rear;
        while (front < rear) {
            p = Queue[++front];
            if (p->Lchild != NULL) Queue[++rear] = p->Lchild;
            if (p->Rchild != NULL) Queue[++rear] = p->Rchild;
            if (front == level) { depth++; level = rear; }
        }
    }
    return depth;
}

遞歸法：

int BiTreeDepth(BiTree T) {
    if (!T) return 0;
    int l = T->Lchild ? BiTreeDepth(T->Lchild) : 0;
    int r = T->Rchild ? BiTreeDepth(T->Rchild) : 0;
    return (l > r ? l : r) + 1;
}