树形结构

树与森林

树时一种新的数据结构，像一颗树一样，有很多的分枝，并且会不一段延伸。只要不断前进，道路就会不断延伸。

树结构介绍(Tree)

可以看到，现在一个结点下面可能会连接多个节点，并不断延伸，就像树枝一样，每个结点都有可能是一个分支点，延伸出多个分支，从位于最上方的结点开始不断向下，而这种数据结构，我们就称为树（Tree）注意分支只能向后单独延伸，之后就分道扬镳了，不能与其他分支上的结点相交！

  • 根节点(Root)：位于最上方的结点，整棵树都是从这里开始延伸出去的
  • 度(Degree)：每个节点连接的子节点的数目（分支的数目）。而各个结点中度的最大值称为树的度。
  • 子树(SubTree)：每个结点所延伸的子结点，都可以称为是一个子树。比如结点B及其之后延伸的所有分支合在一起，就是一棵A的子树。
  • 层次(Level)：按照从上到下的顺序，树的根节点为1，每向下一层+1，因此G的层次就为3。
  • 深度(Depth)：整棵树中所有结点的最大层次，就是这棵树的深度。本棵树的深度就为4。

因为树成长之后会显得错综复杂，所以要规定一下，结点与结点之间的称呼。

  • 子结点(Child)：与当前节点直接向下相连的结点。
  • 父结点/双亲结点(Parent)：与当前节点直接向上相连的结点。
  • 叶子结点(Leaf)：当前节点没有任何子结点。
  • 兄弟节点(Sibing)：两个结点的父结点相同。
  • 祖先节点(Ancestor)：从根结点开始一直到当前结点，该路径上的所有结点，均为当前结点的祖先结点。

森林(Forest)

森林其实很好理解，一片森林肯定是是由很多棵树构成的，比如下面的三棵树：

它们共同组成了一片森林，因此，m（m≥0）棵树的集合我们称为森林。

二叉树

二叉树，顾名思义，只有两个叉的树。也就是它各个结点的度，最大只能为2。

并且二叉树任何结点的子树是有左右之分的，不能颠倒顺序，比如A结点左边的子树，称为左子树，右边的子树称为右子树。

二叉树有5种基本形态，分别是：

当然，对于某些二叉树我们有特别的称呼，比如，在一棵二叉树中，所有分支结点都存在左子树和右子树，且叶子结点都在同一层：

这样的二叉树我们称为满二叉树，可以看到整棵树都是很饱满的，没有出现任何度为1的结点，当然，还有一种特殊情况：

可以看到只有最后一层有空缺，并且所有的叶子结点是按照从左往右的顺序排列的，这样的二叉树我们一般称其为完全二叉树，所以，一棵满二叉树，一定是一棵完全二叉树。

树和森林的转换

二叉树和树以及森林之间是可以相互转换的。

树转二叉树

第一种方式：
  1. 最左边的子结点 -> 上级的左子树
  2. 该层剩下的兄弟结点->作为刚才左子树的右结点

这里有点绕，直接看下面的详解吧。

我们以下面的这棵树为例：

我们优先从左边开始看，B、F、G都是A的子结点，根据上面的规律，我们将B作为左子树：

接着继续从左往右看，由于F是B的兄弟结点，那么根据规律，F作为B的右子树：

接着是G，G是F的兄弟结点，那么G继续作为F的右子树：

我们接着来看第三排，依然是从左往右，C是B的子节点，所以C作为B的左子树：

接着，D是C的兄弟节点，那么D就作为C的右子树了：

此时还有一个H结点，它是G的子结点，所以直接作为G的左子树：

现在只剩下最后一排了，E是D的子结点，K是H的子结点，所以最后就像这样了：

按照规律，我们就将一棵树转换为了二叉树。

第二种方法：

当然还有一种更简单的方法，我们可以直接将所有的兄弟结点连起来（橙色横线）：

接着擦掉所有结点除了最左边结点以外的连线：

所有的黑色连线偏向左边，橙色连线偏向右边：

效果是一样的，这两种方式都可以，你觉得哪一种简单就使用哪一种就行了。我们会发现，无论一棵树长成啥样，转换为二叉树后，根节点一定没有右子树。

思考：那二叉树咋变回普通的树呢？实际上我们只需要反推回去就行了。

二叉树转森林

那么森林呢，森林如何转换为一棵二叉树呢？其实很简单：

首先我们还是按照二叉树转换为树的规则，将森林中所有树转换为二叉树，接着我们只需要依次连接即可：

注意连接每一棵树的时候，一律从根结点的右边开始，不断向右连接。

我们发现，相比树转换为二叉树，森林转换为二叉树之后，根节点就存在右子树了，右子树连接的都是森林中其他的树。

思考：现在有一棵二叉树，我们想要转回去，我们怎么知道到底是将其转换为森林还是转换为树呢？

二叉树的性质

由于二叉树结构特殊，我们可以总结出以下的五个性质：

  • 性质一：对于一棵二叉树，第i层的最大结点数量为 $2^{i-1}$个，比如二叉树的第一层只有一个根结点，也就是 $2^0=1$ ，而二叉树的第三层可以有 $2^2=4$个结点。

  • 性质二：对于一棵深度为k的二叉树，可以具有的最大结点数量为：

    我们发现，实际上每一层的结点数量，组成了一个等比数列，公比q为2，结合等比数列求和公式，我们可以将其简化为：

    所以一棵深度为k的二叉树最大结点数量为 $n=2^k-1$，顺便得出，结点的边数为 $E=n-1$。

  • 性质三：假设一棵二叉树中度为0、1、2的结点数量分别为$n_1$、$n_2$、$n_3$，由于一棵二叉树中只有这三种类型的结点，那么可以直接得到结点总数：

    我们不妨换一个思路，我们从二叉树的边数上考虑，因为每个结点有且仅有一条边与其父结点相连，那么边数之和就可以表示为：

    度为1的结点有一条边，度为2的结点有两条边，度为0的结点没有，加在一起就是整棵二叉树的边数之和，结合我们在性质二中推导的结果，可以得到另一种计算结点总数的方式：

    再结合我们第一个公式：

综上，对于任何一棵二叉树，如果其叶子结点个数为 $n_0$ ，度为2的结点个数为 $n_2$ ，那么两者满足以下公式：

（性质三的推导过程比较复杂，如果觉得麻烦推荐直接记忆）

  • 性质四：完全二叉树除了最后一层有空缺外，其他层数都是饱满的，假设这棵二叉树为满二叉树，那么根据我们前面得到的性质，假设层数为k，那么结点数量为：$n=2^k-1$ ，根据完全二叉树的性质，最后一层可以满可以不满，那么一棵完全二叉树结点数n满足：

    因为n肯定是一个整数，那么可以写为：

    现在我们只看左边的不等式，我们对不等式两边同时取对数，得到：

    综上所述，一棵具有n个结点的完全二叉树深度为 $k=\left \lfloor \log_{2}{n} \right \rfloor+1$ 。

    （性质四的推导过程比较复杂，如果觉得麻烦推荐直接记忆）

  • 性质五：一颗有n个结点的完全二叉树，由性质四得到深度为 $k=\left \lfloor \log_{2}{n} \right \rfloor+1$ 现在对于任意一个结点i，结点的顺序为从上往下，从左往右：

    • 对于一个拥有左右孩子的结点来说，其左孩子为2i，右孩子为2i + 1。
    • 如果i = 1，那么此结点为二叉树的根结点，如果i > 1，那么其父结点就是 $\left \lfloor i/2\right \rfloor$，比如第3个结点的父结点为第1个节点，也就是根结点。
    • 如果2i > n，则结点i没有左孩子，比如下面图中的二叉树，n为5，假设此时i = 3，那么2i = 6 > n = 5 说明第三个结点没有左子树。
    • 如果2i + 1 > n，则结点i没有右孩子。

以上五条二叉树的性质一般是笔试重点内容，还请务必牢记，如果觉得推导过程比较麻烦，推荐直接记忆结论。

二叉树的简单构建

前面我们介绍了二叉树的几个重要性质，那么现在我们就来尝试在程序中表示和使用一棵二叉树。

二叉树的存储形式也可以使用我们前面的两种方式，一种是使用数组进行存放，还有一种就是使用链式结构，只不过之前链式结构需要强化一下才可以表示为二叉树。

首先我们来看数组形式的表示方式，利用前面所推导的性质五，我们可以按照以下顺序进行存放：

这颗二叉树的顺序存储：

从左往右，编号i从1开始，比如现在我们需要获取A的右孩子，那么就需要根据性质五进行计算，因为右孩子为2i + 1，所以A的右边孩子的编号就是3，也就是结点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
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;

class TreeNode {
public:
    char element;
    TreeNode* left;
    TreeNode* right;

    TreeNode(char value) : element(value), left(nullptr), right(nullptr) {}
};

int main() {
    TreeNode* a = new TreeNode('A');
    TreeNode* b = new TreeNode('B');
    TreeNode* c = new TreeNode('C');
    TreeNode* d = new TreeNode('D');
    TreeNode* e = new TreeNode('E');
    TreeNode* f = new TreeNode('F');

    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->right = f;
    c->left = nullptr;
    d->left = e->right = nullptr;
    e->left = e->right = nullptr;
    f->left = f->right = nullptr;

    // 在这里进行其他操作...

    // 释放内存
    delete a;
    delete b;
    delete c;
    delete d;
    delete e;
    delete f;

    return 0;
}

二叉树遍历

前面我们通过使用链式结构，成功构建出了一棵二叉树，接着我们来看看如何遍历一棵二叉树，也就是说我们想要访问二叉树的每一个结点，由于树形结构特殊，遍历顺序并不唯一，所以一共有四种访问方式：前序遍历、中序遍历、后序遍历、层序遍历。不同的访问方式输出都结点顺序也不同。

前序遍历

首先我们来看最简单的前序遍历：

前序遍历是一种勇往直前的态度，走到哪就遍历到那里，先走左边再走右边，比如上面的这个图，首先会从根节点开始：

从A开始，先左后右，那么下一个就是B，然后继续走左边，是D，现在ABD走完之后，B的左边结束了，那么就要开始B的右边了，所以下一个是E，E结束之后，现在A的左子树已经全部遍历完成了，然后就是右边，接着就是C，C没有左子树了，那么只能走右边了，最后输出F，所以上面这个二叉树的前序遍历结果为：ABDECF

  1. 打印根节点
  2. 前序遍历左子树
  3. 前序遍历右子树

我们不难发现规律，整棵二叉树（包括子树）的根节点一定是出现在最前面的，比如A在最前面，A的左子树根结点B也是在最前面的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class TreeNode
{
    ...
    void preOrder()
    {
        cout << element<<" ";
        if (left != nullptr)
        {
            left->preOrder();
        }
        if (right != nullptr)
        {
            right->preOrder();
        }
    }
};

1
2
3
4
5
int main(){
         ...

    a->preOrder();
}

imgTree01

中序遍历

中序遍历在顺序上与前序遍历不同，前序遍历是走到哪就打印到哪，而中序遍历需要先完成整个左子树的遍历后再打印，然后再遍历其右子树。

我们还是以上面的二叉树为例：

首先需要先不断遍历左子树，走到最底部，但是沿途并不进行打印，而是到底之后，再打印，所以第一个打印的是D，接着由于没有右子树，所以我们回到B，此时再打印B，然后再去看B的右结点E，由于没有左子树和右子树了，所以直接打印E，左边遍历完成，接着回到A，打印A，然后对A的右子树重复上述操作。所以说遍历的基本规则还是一样的，只是打印值的时机发生了改变。

  1. 中序遍历左子树
  2. 打印结点
  3. 中序遍历右子树

所以这棵二叉树的中序遍历结果为：DBEACF，我们可以发现一个规律，就是在某个结点的左子树中所有结点，其中序遍历结果也是按照这样的规律排列的，比如A的左子树中所有结点，中序遍历结果中全部都在A的左边，右子树中所有的结点，全部都在A的右边（这个规律很关键，后面在做一些算法题时会用到）

那么怎么才能将打印调整到左子树全部遍历结束之后呢？其实很简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TreeNode
{
    ...
            void inOrder()
    {
        if (left != nullptr)
        {
            left->preOrder();
        }
        cout << element << " ";
        if (right != nullptr)
        {
            right->preOrder();
        }
    }
};
int main()
{
    ...
    a->inOrder();
}

imgTree02

后序遍历

后序遍历继续将打印的时机延后，需要等待左右子树全部遍历完成，才会去进行打印。

首先还是一路向左，到达结点D，此时结点D没有左子树了，接着看结点D还有没有右子树，发现也没有，左右子树全部遍历完成，那么此时再打印D，同样的，D完事之后就回到B了，此时接着看B的右子树，发现有结点E，重复上述操作，E也打印出来了，接着B的左右子树全部OK，那么再打印B，接着A的左子树就完事了，现在回到A，看到A的右子树，继续重复上述步骤，当A的右子树也遍历结束后，最后再打印A结点。

  1. 后序遍历左子树
  2. 后序遍历右子树
  3. 打印结点

所以最后的遍历顺序为：DEBFCA，不难发现，整棵二叉树（包括子树）根结点一定是在后面的，比如A在所有的结点的后面，B在其子节点D、E的后面，这一点恰恰和前序遍历相反（注意不是得到的结果相反，是规律相反）

所以，按照这个思路，我们来编写一下后序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class TreeNode
{
    ...
        void postOrder()
    {
        if (left != nullptr)
        {
            left->preOrder();
        }
        if (right != nullptr)
        {
            right->preOrder();
        }
        cout << element << " ";
    }
};
int main()
{
    a->postOrder();
}

imgTree03

层序遍历

最后我们来看层序遍历，实际上这种遍历方式是我们人脑最容易理解的，它是按照每一层在进行遍历：

层序遍历实际上就是按照从上往下每一层，从左到右的顺序打印每个结点，比如上面的这棵二叉树，那么层序遍历的结果就是：ABCDEF，像这样一层一层的挨个输出。

虽然理解起来比较简单，但是如果让你编程写出来，该咋搞？是不是感觉有点无从下手？

我们可以利用队列来实现层序遍历，首先将根结点存入队列中，接着循环执行以下步骤：

  • 进行出队操作，得到一个结点，并打印结点的值。
  • 将此结点的左右孩子结点依次入队。

不断重复以上步骤，直到队列为空。

我们来分析一下，首先肯定一开始A在里面：

接着开始不断重复上面的步骤，首先是将队首元素出队，打印A，然后将A的左右孩子依次入队：

现在队列中有B、C两个结点，继续重复上述操作，B先出队，打印B，然后将B的左右孩子依次入队：

现在队列中有C、D、E这三个结点，继续重复，C出队并打印，然后将F入队：

我们发现，这个过程中，打印的顺序正好就是我们层序遍历的顺序，所以说队列还是非常有用的。

那么现在我们就来上代码吧：

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
class TreeNode
{
    ...
        void levelOrder()
    {
        queue<TreeNode*>q;
        q.push(this);
        while (!q.empty())
        {
            TreeNode* curr = q.front();
            q.pop();
            cout << curr->element << " ";
            if (curr->left != nullptr)
            {
                q.push(curr->left);
            }
            if (curr->right != nullptr)
            {
                q.push(curr->right);
            }
        }
    }
};
int main()
{
    ...
    a->levelOrder();
}

imgTree04