【数据结构指南】树结构
前言：
在接触树结构之前，我们学习的数据结构都是基于线性存储的，包括顺序表、链表、队列和栈等线性数据结构，而树结构是我们认识的首个非线性数据结构，它由n(n≥0)个有限节点组成，具有明显的层次关系。之所以称为"树"，是因为它的形态像一棵倒置的树，根在上而叶在下。
一、树的结构特征
现实生活中的树木通常呈现底部生根、顶部生叶的形态，如下图所示：
在数据结构中，树的结构呈现出根在上方、叶在下方的特点，如下图所示：
二、树的基本概念
2.1树的定义
树是由n（n>=0）个有限结点组成一个具有层次关系的集合，应该满足如下特征：
①有一个特殊的结点，称为根结点，根结点没有前驱结点
②除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合又是一棵结构与树类似的子树。
③每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
如下图所示：
2.2树的术语
通过如下示意图，来讲解树的相关概念和术语表述：
(1)树的节点：如上图所示:A、B、C等字母代表树的各个节点，特别地，A是树的根节点。
(2)节点的度：一个结点含有的子树的个数称为该结点的度，如上图所示:对于节点A而言，有B、C、D为根节点的子树，故A的度为3。
(3)叶子结点或终端结点:不含有子树的节点被称为叶节点或者终端节点（即度为0的结点），如上图所示:J、F、K、L、H、I。
(4)双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点，如上图所示:A是B、C、D的父节点
(5)孩子结点或子结点:与父节点相对应，如上图所示：B、C、D是A的子节点。
(6)树的度：树的度是树内所有结点中，度数值最大的那个结点的度，用数学表达式表示为：树的度 = max ( 所有结点的度 )。
(7)结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
(8)树的高度或深度：树中结点的最大层次。
(9)森林：由m（m>0）棵互不相交的树的集合称为森林；
2.3树的存储
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存其值，又要表示结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
这里介绍一种最为常用的表示方法：孩子兄弟表示法。
typedef int DataType; struct Node { struct Node* firstChild1; // 第一个孩子结点 struct Node* pNextBrother; // 指向其下一个兄弟结点 DataType data; // 结点中的数据域 };如下图所示：
三、二叉树
3.1二叉树的概念
二叉树是一棵特殊的树，是一个n(n>=0)个节点的有限集合，其有如下特征：
①每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点)
②由一个根结点加上两棵别称为左子树和右子树的二叉树组成
③二叉树的子树有左右之分，其次序不能任意颠倒
3.2二叉树的图示
从上图可以看出：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的：
3.3特殊的二叉树
3.3.1、满二叉树
满二叉树：指每一层的节点数量均达到最大值的二叉树。具体而言，若某二叉树的深度为h，且其节点总数为2^h-1，则该树即为满二叉树。
对于一棵满二叉树而言：假设其高度为h，节点总数为N
第一层有：2^0个节点
第二层有：2^1个节点
第三层有：2^2个节点
......
第h-1层有:2^(h-1)个节点
第h层有：2^h个节点
用N表示这棵二叉树的总节点数，则有N=2^0+2^1+2^2+......+ 2^(h-1)+ 2^h =2^h-1。
所以也可得出h=logN+1，对于一棵二叉树而言其深度可以被近似为h ≈ logN
3.3.2、完全二叉树
完全二叉树：除最后一层外，每一层的节点数均达到最大值，最后一层的节点从左到右连续排列，缺失的节点只能在右侧。
对于完全二叉树，满足如下特征：
①叶子节点仅可能出现在最下两层，且最下层叶子一定靠左集中。
② 适合用数组存储，无需额外空间记录指针，通过索引即可计算父子节点位置。
③不存在只有右子节点而无左子节点的节点，右子节点存在的前提是左子节点已存在。
注：满二叉树也被视为特殊的完全二叉树。
3.4二叉树的性质
二叉树的性质围绕节点数、深度、子树关系及特殊类型展开，核心是 “每个节点最多 2 个子节点” 的结构约束，以下是系统总结：
3.4.1、所有二叉树的性质
①节点数与度数关系：若总节点数为 N，度为 0（叶子）、1、2 的节点数分别为 n₀、n₁、n₂，则 N = n₀ + n₁ + n₂，且 n₀ = n₂ + 1（叶子节点数比度为 2 的节点数多 1）。
推导过程：假设二叉树有N个结点
从总结点数角度考虑：N = n0 + n1 + n2 ①
从边的角度考虑：N个结点的任意二叉树，总共有N-1条边，因为二叉树中每个结点都有父节点，根结点没有父节点，每个节点向上与其父节点之间存在一条边因此N个结点的二叉树总共有N-1条边。
因为度为0的结点没有孩子，故度为0的结点不产生边;
度为1的结点只有一个孩子，故每个度为1的结点产生一条边;
度为2的结点有2个孩子，故每个度为2的结点产生两条边，所以总边数为： n1+2*n2
故从边的角度考虑：N-1 = n1 + 2*n2 ②
结合① 和 ②得：n0 + n1 + n2 - 1 = n1 + 2*n2 即：n0 = n2 + 1
②深度与节点数上限：若深度为 k（根节点深度为 1），则该二叉树最多有 2ᵏ - 1 个节点（满二叉树的情况），最少有 k 个节点。
二叉树最多节点的情况：
第 1 层： 最多有2^0 个节点。
第 2 层：最多有2^1个节点。
第 3 层：最多有2^2个节点。
......
第 k 层：最多有 2^(k-1) 个节点。
最多节点的总数为:N= 2^0 + 2^1 + 2^2 + ... + 2^(k-2) + 2^(k-1) = 2^k - 1个节点。
二叉树最少节点的情况：
每层只有一个节点，则k层有k个节点。
③层数与节点分布：第 k 层（根为第 1 层）最多有 2^(k-1) 个节点，最少有 1 个节点。
3.4.2、满二叉树的性质
①所有层的节点数均达到最大值，即第 k 层有 2^(k-1) 个节点，总节点数 n = 2ᵏ - 1（k 为深度）。
②叶子节点全部在最底层，且不存在度为 1 的节点（n₁ = 0），叶子节点数 n₀ = 2ᵏ⁻¹。
③假设树的深度 k ，则总节点数 n = 2ᵏ - 1，深度 k ≈ log₂n。
3.4.3、完全二叉树的性质
①节点总数 n 满足( 2ᵏ⁻¹ - 1 ) + 1 <= n <=2ᵏ-1（k 为深度），深度 k ≈ log₂n。
②数组存储索引规则：
Ⅰ. 父节点 i 的左子节点为 2*i、右子节点为 2*i+1；
Ⅱ. 子节点 j 的父节点为 j / 2（索引从 1 开始）。
③叶子节点索引范围为 n/2 + 1 到 n，非叶子节点为 1 到 n/2，无 “只有右子节点” 的情况。
④对于完全二叉树，度为1的节点：只有1个或者0个。
四、树与二叉树的转换
4.1 普通树转换为二叉树
4.1.1核心方法
①加线（连兄弟）：在所有兄弟节点之间加一条连线。
②抹线（断父子）：保留最左边的孩子（长子），抹掉其他孩子
③旋转（理层次）：以树的根节点为轴心，将整棵树顺时针旋转45度，使其看起来像一棵标准的二叉树。
简记：兄弟相连留长子
4.1.2 图解演示
如图所示一棵普通树：
操作一：兄弟间加线
操作二：保留长子
③以根为轴心顺时针旋转45°
4.2 二叉树转换为普通树
4.2.1核心方法
①加线（认父亲）：对于某个节点（比如 P），如果它有左孩子（L），那么把 L 的所有右链上的节点（即 L 的兄弟们），都与 P 用线连起来。
②抹线（断兄弟）：抹掉二叉树中所有节点与它右孩子之间的连线。
③旋转（理层次）：整理结构，使其恢复为普通树的层次。
简记为：左孩右右连双亲，去掉原来右孩线
4.2.2图解演示
如图所示有一棵二叉树：
操作一：加线（认父亲）
操作二：抹线（断兄弟）
③旋转（理层次）
4.3 森林转换为二叉树
4.3.1核心方法
①各树自转：先把森林中的每一棵树，各自转换为二叉树
②根根相连：将每棵树的根节点用线连起来
③唯一树根：第一棵树的根节点，就是转换后整棵二叉树的根节点。
简记：树变二叉，根相连
4.3.2图解演示
如图所示有如下森林：
操作一：各树自转
操作二：根根相连
操作三：唯一树根
4.4二叉树转换为森林
4.4.1核心方法
①抹线（断开树与树的联系）：沿着二叉树根节点的右链一直走下去，把这根链上的所有连线全部剪断。
②提取（确定每棵树的根）：断开后，右链上的每一个节点，现在都成为了独立的二叉树的根节点。
③还原（各自变回普通树）：对这散落出来的每一棵小二叉树，分别执行 “二叉树转普通树” 的操作
简记：去掉根部右孩线，孤立二叉再还原
4.4.2图解演示
如图所示一棵二叉树：
操作一：抹线（断开树与树的联系）
操作二：提取（确定每棵树的根）
操作三：还原（各自变回普通树）
五、小试牛刀
5.1试题一
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199
解析：
对于任何一棵二叉树，都满足这样一个性质：
n0（度为0的节点） = n2（度为2的节点） + 1
故而叶子节点（即度为0的节点） 个数为：199+1=200 ， B选项符合题意。
5.2试题二
2.下列数据结构中，不适合采用顺序存储结构的是（ ）
A 非完全二叉树
B 堆
C 队列
D 栈
解析：
B、 堆：基于完全二叉树连续排列的特性，故而可以采用顺序结构存储
C、队列：对于循环队列采用顺序存储结构
D、栈：一般基于数组实现，采用顺序结构
答案为：A
5.3试题三
3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
解析：
对于任何一棵二叉树而言其节点总数N，由度为0的节点、度为1的节点、度为2的节点所组成
N=n0+n1+n2
任意一棵二叉树满足如下性质：
n0=n2+1
故而2n = n0 + n1 + n0-1 , 当且仅当 n1=1 时左边为偶数，且右边为偶数 , 所以n0=n。
答案为:A
5.4试题四
4.一棵完全二叉树的结点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
解析：
对于一棵完全二叉树而言，假设这棵树的高度为k，则其节点的范围：
2ᵏ⁻¹ ~ 2ᵏ - 1
答案为：B
5.5试题五
5.一个具有767个结点的完全二叉树，其叶子结点个数为（）
A 383
B 384
C 385
D 386
解析：
对于任何一棵二叉树而言其节点总数N，由度为0的节点、度为1的节点、度为2的节点所组成
N=n0+n1+n2
任意一棵二叉树满足如下性质：
n0=n2+1
对于N=767， 则有767=n0+n1+n0-1 当且仅当n1等于0时，才满足左右两边为奇数，所以n1=0
答案为：B: n0=384
既然看到这里了，不妨关注+点赞+收藏，感谢大家，若有问题请指正。
