树 - 基础#

简述#

树是一种数据结构，本质是由有限个节点按照层级关系进行组织的结构，其形状像一个倒着的树

img/TreeBasic/TreeBasic.png

对于这样的数据结构，有一些专业的术语需要了解（下面给出的例子均针对上图进行）：

节点深度：一个节点x的深度代表这个节点到根节点的距离
例如，节点 6 的深度就是2；而对于根节点，这个深度是0
节点高度：与“深度”相反，高度的意思是一个节点x到最远的叶子节点的距离
例如，节点 3 的高度就是2
树深度：最末端叶子节点的节点深度
节点层次：从根节点开始为第一层，往下以此类推
兄弟节点：直接拥有共同父节点的子节点
度：一个节点的子节点个数
叶子节点：度为0的节点
祖先：对于一个节点x，从根节点到这个节点的路径上的所有节点均为节点x的祖先例如，节点 6 的祖先是：1, 2
后代：对于一个节点x，这个节点下的子树下的所有节点均为节点x的后代例如，节点 6 的后代是：7, 8, 9

简单的实现#

一个树可以通过下面的代码实现：

1
struct TreeNode {
2
    int val = 0;
3
    std::vector<TreeNode*> subs;
4

5
    TreeNode()=default;
6
    TreeNode(int v): val(v) {}
7

8
    TreeNode& addChild(int v) {
9
        subs.push_back(new TreeNode(v));
10
        return *this;
11
    }
12
};

针对上述代码，方法 addChild 用于向这个节点下添加子节点

给出下面的示例代码：

1
void test_normal_tree() {
2
    auto root = TreeNode();
3

4
    root.subs.push_back(new TreeNode(1));
5
    root.subs.push_back(new TreeNode(2));
6
    root.subs.push_back(new TreeNode(3));
7
    root.subs.push_back(new TreeNode(4));
8

9
    root.subs.at(0)->subs.push_back(new TreeNode(10));
10
    root.subs.at(0)->subs.push_back(new TreeNode(11));
11
    root.subs.at(0)->subs.push_back(new TreeNode(12));
12
    root.subs.at(1)->subs.push_back(new TreeNode(13));
13
    root.subs.at(1)->subs.push_back(new TreeNode(14));
14
    root.subs.at(3)->subs.push_back(new TreeNode(15));
15
}

运行完上述代码之后，如果要对这个树的内容进行输出，那么应该是下面的输出：

1
0:{
2
    1:{
3
        (10), (11), (12)
4
    },
5
    2:{
6
        (13), (14)
7
    },
8
    (3),
9
    4:{,
10
        (15),
11
    }
12
}

那么，如何输出一个树的存储内容呢？

树的遍历#

上面问题的答案是很简单的，遍历

但是，对于一个树，遍历分为两种方法：先序遍历和后序遍历，下面，我们将对这两种方法进行介绍：

先序遍历#

所谓“先序”，意思是在遍历的过程中根节点的访问顺序，那么在先序遍历中，对根节点的访问顺序也就是最先的了

因此，我们有下列代码，作为上述代码给出的 TreeNode 的方法：

1
void preorderTraversal() {
2
    if (subs.empty())
3
        std::cout <<"("<< val <<")";
4
    else
5
       std::cout << val << ":{" ;
6

7
    for (auto node: subs) {
8
        node->preorderTraversal();
9
    }
10

11
    if (!subs.empty()) {
12
        std::cout << "}";
13
    }
14
}

因为是先序遍历，所以上面的代码先把当前节点的值 val 输出，之后才对自己的子节点进行 preorderTraversal 操作

后序遍历#

了解了上述“先序”的概念，那么“后序”也是同理：即后访问根节点，先对子节点进行访问：

1
void postorderTraversal() {
2
    std::cout << "{";
3

4
    for (auto node: subs) {
5
        node->postorderTraversal();
6
    }
7

8
    if (subs.empty())
9
        std::cout << "sub: " << val << "}";
10
    else
11
        std::cout << "(" << val << ")}";
12
}

可以看到，对于后序遍历，我们先对子节点进行 postorderTraversal 操作，之后才对自己的节点内容进行输出