树#

树是一种常见的数据结构，在许多地方都有使用

二叉树则是其中更加广泛使用的一种树

二叉树#

一个常见的二叉树节点的定义是这样的：

1
template<typename T>
2
struct Node {
3
    T element;
4
    Node* left = nullptr;
5
    Node* right = nullptr;
6
}

一个二叉树节点内有两个特殊的成员：left 和 right 用于指向其下的子节点

一些二叉树的特性#

深度从根节点开始延伸下来到目标节点的经过的边数
高度从目标节点开始向下到最远的叶子节点的层数

形象理解，对于下面的这个二叉树：对于其节点B：

深度：从A开始到B只有一条边，所以深度为1
高度：从B往下的最远的叶子节点是F，中间有两层，所以高度为2

二叉树最值得注意的便是它的各种遍历：

先序遍历#

1
void preorderTraversal() {
2
    std::cout << element;
3
    if (left && !leftThread) {
4
        left->preorderTraversal(isTidy);
5
    }
6
    if (right && !rightThread) {
7
        right->preorderTraversal(isTidy);
8
    }
9
}

先序遍历，就是先访问该节点下的元素后，再访问其各个子节点的方式

后序遍历#

1
void postorderTraversal() {
2
    if (left && !leftThread) {
3
        left->postorderTraversal(isTidy);
4
    }
5
    if (right && !rightThread) {
6
        right->postorderTraversal(isTidy);
7
    }
8
    std::cout << element;
9
}

后序遍历，就是先访问该节点下的两个子节点后，再访问自己所拥有的元素的方式

中序遍历#

1
void inorderTraversal() {
2
    if (left && !leftThread) {
3
        left->inorderTraversal(isTidy);
4
    }
5
    std::cout << element;
6
    if (right && !rightThread) {
7
        right->inorderTraversal(isTidy);
8
    }
9
}