二叉树札记 II 树的遍历

Author: sandyzikun

前面讲过了二叉树的基本构造方法，于此我们来审察二叉树的三种遍历方法

  • 先序遍历 (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. 百度百科词条 二叉树 ↩