一本正经的聊数据结构（4）：树

前文传送门：

「一本正经的聊数据结构（1）：时间复杂度」

「一本正经的聊数据结构（2）：数组与向量」

「一本正经的聊数据结构（3）：栈和队列」

引言

在前面的文章中，我们已经陆陆续续的介绍了一些数据结构。

根据这些数据结构的实现方式，大体上可以分成两类：基于数组的实现和基于链表的实现。

这两种实现方式各有优缺点，说不上谁一定好谁一定不好，需要根据具体的使用场景进行选型。

基于数组的实现方式，这种方式允许我们通过下标在常数的时间内找到目标对象，但是如果需要对这种结构进行修改，无论是插入还是删除，都需要耗费线性的时间。

基于链表的实现方式，这种实现方式允许我们借助位置对象，在常数的时间内插入或者删除元素，但是如果想要找到某个元素，那么不得不耗费线性的时间。

基于上面这两点，我们可以知道，如果当前的场景是修改远大于查询，那么选择链表的数据结构会比较好。

反过来如果是查询远大于修改，那么选择数组的数据结构会比较好。

上面这段没看懂的，可以翻翻前面的文章然后去面壁思过了。

树

前面这些数据结构，元素之间都有一个自然的线型的关系，所以他们都都被称为线型结构。

而我们从本篇开始介绍的树就不一样了，树的元素之间并不会有直接的直接前驱或者直接后继这种关系，但是，只要是加上某种约束条件，也是可以在树的元素之间确定某种线型次序，所以树这种结构被称为半线型结构。

先来看下树结构长啥样：

树这种结构非常像一个树倒过来，所以因此而得名。

一些基础概念：

• 结点：使用树结构存储的每一个数据元素都被称为「结点」，如节点 A ，节点 B ，节点 C 。
• 父结点（双亲结点）、子结点和兄弟结点：对于上图的结点 A、B、C、D 来说，A 是 B、C、D 结点的父结点（也称为「双亲结点」），而 B、C、D 都是 A 结点的子结点（也称「孩子结点」）。对于 B、C、D 来说，它们都有相同的父结点，所以它们互为兄弟结点。
• 树根结点（简称「根结点」）：每一个非空树都有且只有一个被称为根的结点。上图中，结点 A 就是整棵树的根结点。树根的判断依据为如果一个结点没有父结点，那么这个结点就是整棵树的根结点。
• 叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）。如图中的结点 K、L、F、G、M、I、J 都是这棵树的叶子结点。
• 结点的度（Degree）：对于一个结点，拥有的子树数（结点有多少分支）。如上图中，根结点 A 下分出了 3 个子树，所以，结点 A 的度为 3。
• 结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。所以在上面这张图中，A 结点在第一层，B、C、D 为第二层，E、F、G、H、I、J 在第三层，K、L、M 在第四层。
• 有序树和无序树：如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。在有序树中，一个结点最左边的子树称为"第一个孩子"，最右边的称为"最后一个孩子"。在上图中，如果是其本身是一棵有序树，则以结点 B 为根结点的子树为整棵树的第一个孩子，以结点 D 为根结点的子树为整棵树的最后一个孩子。

二叉树

二叉树是树结构的一种树，也是我们接触最多使用最为广泛的一种树结构。

简单地理解，满足以下两个条件的树就是二叉树：

• 本身是有序树。
• 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2 。

结果就是长这样的：

简单来讲就是每个节点下面最多只能有两个分叉，超过两个就不叫二叉树了，比如右边这个或许可以叫三叉树（这个没人定义过啊，我就这么一瞎说）？

二叉树的几个特性：

• 在二叉树中，第 i 层最多有 2^(i-1) 个结点。
• 如果二叉树的深度为 K，那么此二叉树最多有 2^K-1 个结点。

这两个特性的推导过程就不拆开讲了，基本上有初中数学基础的应该都能看得懂。

满二叉树

二叉树还可以接着分类，进而衍生出了满二叉树和完全二叉树。

满二叉树就是除了叶子结点，每个结点的度都为 2 。

简单来讲就是所有的节点都插满了，比如下面这样的：

满二叉树除了具有二叉树的特性外，还有一些单独的特性：

• 满二叉树中第 i 层的节点数为 2^(n-1) 个。
• 深度为 k 的满二叉树必有 2^k-1 个节点 ，叶子数为 2^(k-1)。
• 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
• 具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

这个意思就是完全二叉树是满二叉树的不完全体，只要最后一层满足了从左至右排布以及其余层次都是满二叉树，那么这个就叫做完全二叉树，比如下面这样的：

图 b 不是完全二叉树的原因就是因为它的最后一层并不是从左至右排布的，这个要清楚。

完全二叉树也有一些自己独特的性质，如：

• n 个结点的完全二叉树的深度为 ⌊log2n⌋+1 。
• 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
• 如果 2*i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2*i 。
• 如果 2*i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2*i+1 。

小结

本篇的内容就先到这里了，通过本篇的内容，应该对数和二叉树有一个初步的认知，能够清楚的了解树和二叉树的结构以及一些二叉树的基础的特性。

从下篇内容开始，我们介绍二叉树的一个关键知识点：实现与遍历。

您的扫码关注，是对小编坚持原创的最大鼓励：）
转载：https://blog.csdn.net/meteor_93/article/details/105900508