Next Nest

wusa!~(•㉨•)

二叉樹筆記 II 樹的遍歷

发表于 Valine：

前面講過了二叉樹的基本構造方法，於此我們來審察二叉樹的三種遍歷方法

  • 先序遍歷 (preorder traversal, root->left->right)
  • 中序遍歷 (inorder traversal, left->root->right)
  • 後序遍歷 (postorder traversal, left->right->root)

以洛谷 P1305的衍生題目QUST Q1295爲例。

假設我們現在所得到的一棵二叉樹上節點的内容為整型數據，輸入為

1
2
3
4
5
6
7
8
9
10
9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

容易發現這是一棵擁有九個節點的二叉樹如下，其個節點上的值即爲該節點的編號

root:   0   (根節點)
      /   \
    1       4
   / \     / \
  2   3   5   8
         / \
        6   7

Construction

對於容量未知的二叉樹1，我們會用一個足夠大的數組或者vector來存儲其節點

C++
1
2
3
4
struct Node {
    int val;
    struct Node *parent, *lchild, *rchild;
} *root, *treenodes[393939];

在這道題目中，我們不僅把編號存儲到節點的值當中，同時也會放在數組中對應索引的位置

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
for (int k = 0; k != m; ++k) {
    int idx, lch, rch;
    scanf("%d %d %d", &idx, &lch, &rch);
    if (treenodes[idx] == nullptr) {
        // 如若該節點不存在，則先構造該節點
        treenodes[idx] = (struct Node *)malloc(sizeof(struct Node));
        treenodes[idx]->val = idx;
    }
    if (lch != -1) {
        // 如若存在左子樹
        if (treenodes[lch] == nullptr) {
            // 如若左女兒不存在，則先構造左女兒
            treenodes[lch] = (struct Node *)malloc(sizeof(struct Node));
            treenodes[lch]->val = lch;
        }
        // 使節點與左女兒互相連接
        treenodes[idx]->lchild = treenodes[lch]; // 像節點聲明左女兒的位置
        treenodes[lch]->parent = treenodes[idx]; // 像左女兒聲明其母親即是該節點
    }
    if (rch != -1) {
        // 右側處理同理類似
        if (treenodes[rch] == nullptr) {
            treenodes[rch] = (struct Node *)malloc(sizeof(struct Node));
            treenodes[rch]->val = rch;
        }
        treenodes[idx]->rchild = treenodes[rch];
        treenodes[rch]->parent = treenodes[idx];
    }
}
// Root Tracing, (從任何一個節點都可以)尋找這棵樹的根節點
root = treenodes[0];
while (root->parent != nullptr)
    // 只要當前看到的節點還有母親，就向上爬
    root = root->parent;

此即主函數中構造這棵樹的方法。

Traversal

例如先序遍歷的輸出過程，其處理順序為根-左-右，按照這樣的順序進行輸出的函數如下：

C++
1
2
3
4
5
6
7
void __print_preorder(struct Node *rt) {
    if (rt != nullptr) {
        printf(" %d,", );
        __print_preorder(rt->lchild);
        __print_preorder(rt->rchild);
    }
}

因爲先序遍歷是先處理根節點，然後再先後處理左子樹和右子樹，處理左右子樹的時候也是按照順序處理根-左-右，因此形式上是遞歸的。

References

1. 百度百科詞條 二叉樹 ↩