【初阶数据结构】详解树和二叉树（一） - 预备知识（我真的很想进步）

前言

初阶数据结构篇马上要迎来了一个新的成员，那就是"二叉树"。

但是我上来不可能直接带着大家立马实现二叉树这个数据结构的，因为这是一种对各位读者不负责的表现。俗话说得好，饭要一口一口地吃，路要一步一步地走！这样学的知识才真的是属于你自己。

为此，在本文我先会给大家介绍什么是“树”？什么又是“二叉树”？以及它们在编程中常用到的一些性质。在这里都会毫无保留地给大家详细地讲解，相信看完这篇文章，你对二叉树乃至树这个数据结构有更深地了解。

当然，我后期还会发布关于二叉树各种系列的博客，保证符合各位读者的胃口。同时也欢迎各位读者来看，大家一起进步！！！

好了，话不多说。让我们朝着二叉树的彼岸说一声:"Let’s go!"🚢💖💖

1. 树

在讲二叉树之前，我们肯定得先知道什么是"树"。

1.1 树的概念

树：由n(n>=0)个有限的结点组成的具有层次关系的集合。

树是一种非线性的数据结构！

这里就得说一下，什么叫做有层次关系？
你可以把数据结构中的“树”与日常生活我们所看见的“树”，做一个像形的融合。只不过数据结构中的"树"是倒着的(根朝上)。
我们在日常生活中看到的树，是有一定的高度的。相信大家可能有爬树的经历，如果没有的话，那也一定在某种场景下，看过别人爬树。看着他们一步一步的往上爬，直至爬到树顶，他们每往上爬一步，我们都可以认为这是"树的一层",这种关系一直持续到树顶。那"树"的每一层都是组成我们在日常生活的所看到的树的关键一环。这个就是层次关系（为了好区分，这里我就称它为“结构关系”）。

回到数据结构中的"树"，也是有一层一层的结点构成的。这些结点间还有一些有趣的关系(后面会介绍)，这里我们就可以认为层与层之间具备了一定关系。为此，层次关系这个抽象关系我们就给具象化了。希望大家能够理解。

树的一些专属名称：

• 有一个特殊的结点，称为根节点，根节点没有前驱结点（说白了，前面没有任何结点）。
• 除了根节点外，其余结点被分成M（M>0）个互不相交的集合T1、T2、…、Tm，其中每一个集合Ti（1 <= i <= m）又是一棵结构与树类似的子树。每个子树的根节点有且仅有一个前驱节点，可以有0个或多个后继结点。

如果没有理解上面这个枯燥的说法，可以看一下这幅图：

每个颜色的圈都可以看作是一棵子树。当然每一棵子树也可以分为根节点和子树！

• 树是递归定义的。 依据：每一棵树是由根节点及其子树构成的，而子树也是有一个根节点和其子树构成的。

那我们了解了树的一些定义，那我们在实际中该怎么判断题目给出的一幅图是否是一棵"树"呢？

现在我来教大家几招：

• 子树是不相交的；
• 除了根节点外，每一个结点有且只有一个父节点；（父节点，我们后面讲）
• 一棵N个结点数的树有N-1条边。（这里可以这么理解，我们从树的底层的结点看起，其每个节点都向上连接这一条边，按照这个思想，我们会发现只有根结点向上是没有边的，其余的结点向上都连接这一条边，为此N-1就是这么来的！）

这里给大家一些小练习，来判断下面的图是不是树。

可以看到，上面的三幅图都不是树，因为它们都不满足我上述提到的三点。

相信到这里大家对树已经有足够的了解了。

为了让“树”变得更加的科学化、专业化，我们必须得学习有关于"树"的一些相关的概念。（温馨提示：概念可能有点多，大家重点了解我标出颜色的即可，这些概念都是大家在以后做题或者与人讨论“树”的必不可少的工具）

1.2 树的相关概念

• 节点的度： 一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
• 非终端节点或分支节点： 度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
• 兄弟节点： 具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
• 树的度： 一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
• 节点的层次： 从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度： 树中节点的最大层次； 如上图：树的高度为4
• 堂兄弟节点： 双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
• 节点的祖先： 从根到该节点所经分支上的所有节点； 如上图：A是所有节点的祖先
• 子孙： 以某节点为根的子树中任一节点都称为该节点的子孙。 如上图：所有节点都是A的子孙
• 森林： 由m（m>0）棵互不相交的树的集合称为森林；

这里有个概念可能大家比较模糊，这里我就解释一下：

祖先：就是该结点到根节点所经过的结点，这些结点就称为"祖先"。需要注意的是，经过的路线只能是孩子结点到父节点这条路线。
举个栗子：比如我要找“ Q”结点的祖先

讲完了树相关的概念，相信大家对树是怎么用代码实现的探索兴趣又多了几分。
但是在这里，我不会带着大家真正去实现一棵树。这里会提供树的实现思路。

1.3 树的表示

我们首先得知道一个点，树的实现是要比我们之前学到过的线性表（顺序表、链表、栈、队列）难得多。原因是，树不仅仅是要保存数据，同时还要维护数据之间(结点和结点)的关系。而我们之前学的线性表只是在如何正确保存数据的层面，而树增加了一个层面——数据之间的关系。

实际中树有很多种表示方法，比如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。在这里我给大家简单的介绍最常用的孩子兄弟表示法。(你看，这里就涉及到了有关于树的一些专有名词，如果我们都不去了解，那根本就不知道它在说什么。可见前期的铺垫有多重要。)

typedef int DataType;
struct TreeNode
{
	struct TreeNode* _firstChild1; //第一个孩子结点
	struct TreeNode* _pNextBrother; //指向其下一个兄弟结点
	DataType _data;					//结点中的数据域
}

这个方法是不是很巧妙！其可以完美的避开每个结点下有多少棵子树的问题，我们就解决一个结构体里设计多少个指针数量的问题。

1.4 树在实际中的运用

要说树在实际中的应用，文件系统中的目录树就是经典中的经典！

那至于文件系统更深层次的相关知识，大家可以去看我往后会更新的Linux的文件系统管理！

2. 二叉树

2.1 二叉树的概念

二叉树，大家可以理解为是一种特殊的"树"！

那怎么个特殊法呢？

• 二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

所以看到这里我们就知道了，二叉树无非就是在树的基础上，加上这俩个条件罢了。

这里给大家做一下二叉树的思维拓展：
对于任意的二叉树都是有以下的情况复合而成的：

如果看到这里，你还是对二叉树的概念有点懵懂的话，那你可以听听趣味讲解一下二叉树。

二叉树的双亲结点最多只能拥有两个孩子结点。这就好似"计划生育"政策，每一对夫妻最多只能生两个小baby，当然也可以选择不生或者是只生一个。
这个不就是二叉树双亲节点最多只有两个孩子结点的最好的描述了。

2.2 现实中的二叉树

为了，强化大家对二叉树的印象，给大家看一下现实生活中存在的二叉树！

2.3 特殊的二叉树

普通的二叉树讲完了。现在给大家讲一讲特殊的二叉树，这些二叉树在我们后期的编程扮演着重要的角色，希望大家能够认真理解这些特殊二叉树的性质。

特殊的二叉树：

1. 满二叉树：一个二叉树，如果每一层的结点数都达到了最大值，则这个二叉树就是满二叉树。用数学思想思考的话，如果一个二叉树的层数为K，且结点总数为2^k - 1,则它就是满二叉树。
   
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，由n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1~n的结点——对应时称之为完全二叉树。要注意的是满二叉树是完全二叉树的一种特殊的情况。

如果，你不理解上述的这段话，没有关系。我给出两幅图，你肯定就会明白了。

判断一棵二叉树是否是完全二叉树的方法：

前提条件是该二叉树的深度为K。
条件1：前K-1层的结点必须是满的；
条件2：最后一层的结点必须在肉眼上是紧密挨着的。

2.4 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 $2^h$ - 1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为$n_0$ , 度为2的分支结点个数为$n_2$ ,则有 $n_0$＝$n_2$ ＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h = ${\log }_2(n+1)$. (ps： ${\log }_2(n+1)$.是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

这里的每一条性质都比较重要，希望大家都能理解性记忆！

2.5 二叉树概念和性质的一些习题

1.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199

2.下列数据结构中，不适合采用顺序存储结构的是（ ）
A 非完全二叉树
B 堆
C 队列
D 栈

3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2

4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386

答案：
1.B
2.A
3.A
4.B
5.B

好了到此，有关于树和二叉树的相关概念和性质，我们都已经学习完了。相信在今后当谈论到有关于树和二叉树的话题，你都能清楚的知道。更重要的是，在编程时能够有个清晰的认知！

如果觉得本文还不错的话，麻烦给偶点个赞吧。有关于二叉树的系列我会尽快给大家更新的！😊