前言

“树与二叉树”学习提纲。

树的基本概念

树的关键概念

结点的度：分支数
树的度：各结点度的最大值
结点的层次：根结点为第1层，根结点的孩子结点为第2层，依次类推
结点的深度：从根结点到当前结点的层数
结点的高度：从当前结点到叶子结点的层数的最大值
树的深度/高度：各结点层次的最大值
结点间的路径：结点间的点数
结点间的路径长度：结点间的边数
树的路径长度：根结点到每个结点的路径长度的和

树的存储结构

顺序存储：

双亲表示法

双亲表示法

整型一维数组：下标为当前结点，值为当前结点的双亲
结构体一维数组：结点结构可灵活设计：当前结点，当前结点的双亲，当前结点的孩子，当前结点的兄弟等

链式存储：

多重链表表示法
孩子表示法（改进：双亲孩子表示法）
孩子兄弟表示法/二叉树表示法

多重链表表示法：

指针域数量=树的度。结点结构：数据域，孩子指针域
指针域数量=结点的度：结点结构：数据域，度域，孩子指针域

孩子表示法：

一维数组+单链表
一维数组，存储单链表的头指针。结点结构：数据域，头指针域
单链表，存储孩子结点。结点结构：数据域，孩子指针域

孩子兄弟表示法：

多重链表/二叉链表。结点结构：数据域，第一个孩子指针域，右兄弟指针域

树的常用性质

结点数-1=分支数/边=所有结点的度数和

二叉树的概念

二叉树的基本形态

空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根节点有左子树和右子树

特殊的二叉树

斜二叉树：左斜二叉树，右斜二叉树
满二叉树
完全二叉树
二叉排序/搜索树
平衡二叉树（AVL）
线索二叉树：前序线索二叉树，中序线索二叉树，后序线索二叉树
最优二叉树：带权路径长度最短
正则/严格二叉树：无度为1的结点

二叉树的性质

叶子结点数/度为0的结点数=度为2的结点数+1：n0=n2+1
第k（k>=1）层，该层最多有2的k-1次方个结点
深度/高度为h，该树（满二叉树）最多有2的h次方-1个结点。->结点数为n，满二叉树的深度/高度：[log以2为底的n]下取整+1或[log以2为底的(n+1)]上取整
完全二叉树依据从上到下，从左到右编号为1到n。当前结点的编号为i：
函数Catalan()/卡特兰数：结点数为n，能构成的不同二叉树数：[C右上n右下2×n]组合÷(n+1)

完全二叉树依据从上到下，从左到右编号为1到n。当前结点的编号为i：

i=1，当前结点为根节点，无双亲结点
i不等于或>1时，双亲结点的编号：[i÷2]下取整
i不等于或>1时，若i为偶数，双亲结点的编号：i÷2，当前结点是双亲结点的左孩子
i不等于或>1时，若i为奇数，双亲结点的编号：(i-1)÷2，当前结点是双亲结点的右孩子
2×i<=n时，当前结点有左孩子结点，左孩子结点的编号：2×i
2×i>n时，当前结点无左孩子结点
2×i+1<=n时，当前结点有右孩子结点，右孩子结点的编号：2×i+1
2×i+1>n时，当前结点无右孩子结点
当前结点的层次/深度：[log以2为底的i]下取整+1
树的深度/高度：[log以2为底的n]下取整+1或[log以2为底的(n+1)]上取整
最后一个非叶子结点的编号：[n/2]下取整

完全二叉树依据从上到下，从左到右编号为0到n。当前结点的编号为i：

双亲结点的编号：[i÷2]上取整-1
左孩子结点的编号：2×i+1
右孩子结点的编号：2×i+2

二叉树的存储结构

顺序存储：一维数组（依据完全二叉树）
链式存储：多重链表（灵活设计：二叉链表，三叉链表等）

重要性质：二叉链表的结点数为n，空指针域数：n+1

注意：树的顺序存储结构：数组下标反映结点的编号；二叉树的顺序存储结构依据完全二叉树编号、设计：数组下标反映结点的编号和结点间关系；

二叉树的遍历和线索二叉树

二叉树的遍历方式

深度优先遍历：

先序遍历（NLR）（递归法，迭代法）
中序遍历（LNR）（递归法，迭代法）
后序遍历（LRN）（递归法，迭代法）

广度优先遍历：

层次遍历（递归法，迭代法）

二叉树遍历的性质

已知二叉树的前序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
已知二叉树的后序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
已知二叉树的前序遍历序列和后序遍历序列，不可以唯一确定一颗二叉树，可以唯一确定结点的祖先和子孙关系
已知二叉树的中序遍历序列和层序遍历序列，可以唯一确定一颗二叉树

二叉树遍历的应用

查找
线索化二叉树
求深度/高度：前序遍历，后序遍历，层序遍历
表达式求值：后序遍历
求路径：后序遍历
交换左右子树：后序遍历
求宽度：层序遍历
…

注意：一般求深度（从上到下）用前序遍历，求高度（从下到上）用后序遍历

二叉树线索化的方式

前序遍历
中序遍历
后序遍历

二叉树、树和森林

树转换为二叉树的方式

依据：孩子兄弟表示法

过程：

连接兄弟结点——兄弟表示
只保留每结点和第一个孩子结点的连接，断开和其他孩子结点的连接——孩子表示
调整层次结构（以根结点为轴心，顺时针旋转45°：孩子结点为左孩子，兄弟结点为右孩子）——二叉树层次结构表示

二叉树转换为树的方式

依据：孩子兄弟表示法

过程：

调整层次结构（以根结点为轴心，逆时针旋转45°：左孩子结点为第一个孩子，右孩子结点为其他孩子）——树层次结构表示
连接每结点和其他孩子结点（每结点的第一个孩子结点和其他孩子结点在同一层）——逆孩子表示
断开兄弟结点的连接——逆兄弟表示

森林转换为二叉树的方式

依据：孩子兄弟表示法

过程：

树转换为二叉树——孩子兄弟表示
连接树根结点（第二颗树根结点为第一颗树根结点的右孩子，第三颗树根结点为第二颗树根结点的右孩子，以此类推）——森林/多颗树->一颗二叉树

二叉树转换为森林的方式

依据：孩子兄弟表示法

过程：

断开树根结点和右孩子结点的连接——一颗二叉树->森林/多颗二叉树
二叉树转换为树——逆孩子兄弟表示

注意：

若二叉树根结点的右孩子不存在，转换为树；若存在，转换为森林
二叉树转换为的树和森林是唯一的，树和森林转换为的二叉树是不唯一的

树遍历的方式

先序遍历——与相应二叉树的先序遍历同
后序遍历——与相应二叉树的中序遍历同
层次遍历

森林的遍历方式

先序遍历——与相应二叉树的先序遍历同
中/后序遍历——与相应二叉树的中序遍历同

树与二叉树的应用

哈/赫夫曼树（Huffman）
并查集

哈夫曼树的相关概念

结点间的路径：结点间的点数
结点间的路径长度：结点间的边数
树的路径长度：根结点到每个结点的路径长度的和
结点的带权路径长度：结点的权值×结点到根结点的路径长度
树的带权路径长度（WPL）：所有叶子结点的带权路径长度的和
哈夫曼树的构造
哈夫曼编码：最短前缀码

哈夫曼树的构造：

n个原结点，n-1个新结点，共2n-1个结点
哈夫曼树可能不唯一，树的带权路径长度（WPL）唯一

注意：

存在哈夫曼多叉树
常称哈夫曼二叉树为哈夫曼树
哈夫曼二叉树是最优二叉树、正则/严格二叉树

并查集顺序存储的双亲表示法

一维数组
数组下标：结点名，唯一
数组值：结点的双亲结点名，不唯一，负数，绝对值为树中结点数

总结

“树与二叉树”学习提纲。

参考资料

《2023版数据结构高分笔记》主编：率辉
《2023年计算机组成原理考研复习指导》组编：王道论坛
《大话数据结构》作者：程杰

作者的话

感谢参考资料的作者/博主
作者：夜悊
如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
文章在认识上有错误的地方, 敬请批评指正
望读者们都能有所收获