【数据结构入坑指南（七.1）】--《附带图解，深入解析孩子兄弟表示法：处理复杂树结构的终极方案》

一、初识：“树”为何物？

1.1 为何取名“树”

--树是一种非线性的数据结构，它是由n(n>=0)个有限的节点组成的一个具有关系层次的集合。

--为什么叫做树呢？

：形象的来看，因为它看起来像一颗倒挂的树，它的树根朝上，叶子朝下。

1.2 三张图秒懂“倒挂”结构

• 存在一个特殊的节点，即“根节点”，该节点是“树”最顶部的节点，上面没有前驱节点。
• 除根节点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每一个集合 Ti (1 <= i <= m) 又是⼀棵结构与树类似的子树。每棵子树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

注意：树形结构，子树之间不能有交集。

--那么非树形结构是什么样的？

• 子树是不相交的，相交就是图；
• 除根节点，每个节点仅有一个父结点；
• 一颗N个结点的树又N-1条边。

二、掌握核心术语：与树沟通的“语言库”（附说明）

--说明：

• 父节点/双亲节点：一个节点含有子节点，则结点称为其子节点的父节点； 如图：A是B...的父节点；
• 子节点/孩子节点：一个节点（A）含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点；
• 节点的度：一个节点有几个孩子，它的度就是多少；比如A的度为6，F的度为2，K的度为0；
• 树的度：⼀棵树中，最大的节点的度称为树的度； 如上图：树的度为 6；
• 叶子节点/终端节点：度为 0 的节点称为叶结点； 如上图： B、C、H、I... 等节点为叶结点；
• 分支节点/非终端节点：度不为 0 的节点； 如上图： D、E、F、G... 等节点为分支节点；
• 兄弟节点：具有相同父节点的节点互称为兄弟节点(亲兄弟)； 如上图： B、C 是兄弟节点；
• 节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推；
• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为 4；
• 节点的祖先：从根到该节点所经分支上的所有节点；如上图： A 是所有节点的祖先；
• 路径：一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；比如A到Q的路径为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q；
• 子孙：以某节点为根的子树中任一结点都称为该节点的子孙。如上图：所有节点都是A的子孙；
• 森林：由 m（m>0） 棵互不相交的树的集合称为森林；

概念比较多，但是对照图理解比较容易。

三、树的表示与应用：从理论到实践的桥梁

3.1 结构表示

--从上面的图片可以看出：树的结构很复杂，它存储表示就很麻烦。

--实际使用的表示方法有多种，比如：

• 双亲表示法：每个节点都存储一个指向其父节点的指针；
• 孩子表示法：每个节点都存储一个指向其所有子节点的指针列表；

--但是最常用的是——>孩子兄弟表示法

//树的结构--孩子兄弟表示法
struct TreeNode
{
    struct TreeNode* child; // 左边开始的第⼀个孩⼦节点
    struct TreeNode* brother; // 指向其右边的下⼀个兄弟节点
    int data; //节点中的数据域
};

--图解：

--顺着节点的孩子节点、兄弟节点就可以将所有的子节点找到。

3.3 应用场景

--文件系统是计算机存储和管理文件的一种方式，利用树形结构组织和管理文件及文件夹。在文件系统中，树结构的运用十分广泛，通过父节点和子节点之间的关系来表示不同层次文件之间的关联

四、聚焦二叉树：高效数据结构的设计典范

4.1 什么是“二叉树”结构？

--在树形结构中，如果直接使用太复杂。比较常用的一般是二叉树，一颗二叉树是节点的一个有效集合，该集合由一个根节点以及两颗分别称为“左子树”和“右子树”的二叉树组成或者组成为空。

根据图来理解这段话：

--由图知，二叉树有几个特点：

• 二叉树不存在度 >2 的节点（某节点的子节点不超过两个）；
• 二叉树的子树由明确的左右之分，不能颠倒，即二叉树是有序树；

--注意：二叉树的组成情况，有以下几种：

4.2 二叉树的“特殊群体”

4.2.1 满二叉树

--“满”联系二叉树的特点，即每个节点的子节点都达到最大值（2个节点）。

图示：

其中得到： --每层的节点个数的通式 --> 2^(k - 1)； --树的高度k，节点总和 --> 2^(k) - 1；

4.2.2 完全二叉树

--完全二叉树是由满二叉树引出的，完全二叉树最后一层可以不满，但节点必须从左到右连续填充的二叉树。

图示：

--根据满二叉树的结构，说明满二叉树是一种特殊的完全二叉树。

4.3 二叉树的特性

--由满二叉树得；

• 若规定根节点的层数为 1 ，则⼀棵非空二叉树的第 n 层上最多有 2 ^(n−1) 个节点;
• 若规定根节点的层数为 1 ，则深度为 h 的二叉树的总节点数是 2 ^(h) − 1;
• 若规定根结点的层数为 1 ，具有 n 个节点的满二叉树的深度 h = log(n + 1) ( log以2为底， n+1 为对数)

(2、3条，公式互相转换)

--由完全二叉树得：

• 最后一层（第n层）的节点个数 <= 2^( n - 1)。

五、抉择顺序与链式存储的艺术

--二叉树一般使用两种结构进行存储，一种是顺序结构，另一种是链式结构。

5.1 顺序结构

--顺序结构存储是使用数组来存储，一般数组只适合表示完全二叉树。不是完全二叉树会有空间浪费。

--为什么只有完全二叉树适合顺序结构？

请看图：

--为什么非完全二叉树的顺序结构填充不是紧凑的？

：可以说，数组的填充是为了再现二叉树的结构（或者二叉树是根据数组画出的），所以尽管有的节点为空（图中红色节点），但在数组中也要留出位置，说明在二叉树中这个节点是空的。

5.2 链式结构

--是用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

--链式结构又分为二叉链和三叉链，当前学习的二叉树一班是二叉链。

图示：

回顾： 【面试高频数据结构（五）】--《手把手实现栈结构：附带完整代码与注释，深度揭秘数组实现香在哪？》 【面试高频数据结构（六）】--《从初始化到销毁：手把手教你打造健壮的队列实现》

结语：至此，我们已经打下了坚实的“树”形基础。从根到叶的每一部分，都是我们探索更复杂结构的起点。接下来，当我们深入二叉树、堆等森林深处的宝藏时，你会发现，这里定义的每一个术语，理解的每一种特性，都将成为我们手中的利剑。