树

树一种递归的数据结构，是$n(n \geq 0)$个结点的有限集。

任意一棵非空树应满足：

有且仅有一个根结点。
当$n>1$时，其余结点可以分为$m(m>0)$个互不相交的有限集$T_1,T_2,…T_m$，其中每个集合本身又是一棵树并称为根结点的子树。

树的特点：

根结点没有前驱，其余结点有且只有一个前驱。
所有结点都可以有零个或多个后继。

基本术语

结点的度：一个结点的孩子个数称为该结点的度。
树的度：树中结点的最大度数称为树的度。
分支结点（非终端结点）：度大于0的结点。
叶结点（终端结点）：度为0的结点。
结点的层次：从根结点开始定义，根结点为第1层，它的孩子为第2层，以此类推。
结点的深度：结点所在层次。
树的深度：树中结点的最大层次。
有序树和无序树：树中结点的各子树从左到右是有次序的，即左右子树不能交换，称为有序树。
分支：相邻结点之间的关系。
路径：树中两个结点之间的分支。
路径部分有疑惑
路径长度：路径上所经过的边的数量（分支数目）。
森林：$m(m \geq 0)$棵互不相交的树的集合。
树的性质
树的结点数$n$等于所有结点的度数之和加1。
度为$m$的树中第$i$层上至多有$m^{i-1}$个结点。

推导：假设所有结点的度均为$m$，第1层有$m^0$个结点，第2层有$m^1$个，以此类推，第$i$层有$m^{i-1}$个结点。

高度为$h$的$m$叉树至多有$(m^h-1)(m-1)$个结点。
度为$m$、具有$n$个结点的树的最小高度为$\log_m (n(m-1)+1)$。

推导：假设除了叶结点外结点的度均为$m$。可以列出式子，$m^0+m^1+…+m^{h-1}=n$，可以求出$h=\log_m (n(m-1)+1)$。

度为$m$，具有$n$个结点的树的最大高度$h$为$n-m+1$。

推导：假设只有一个结点的度为$m$。

树的存储

树需要保存的信息有：结点本身的数据信息$data$和结点之间的关系。\
和线性表的存储结构一样，树的存储也分为顺序存储结构和链式存储结构。

多重链表结构

定长结点的多重链表结构

设$k$为树的度，每个链结点的构造：
| 结点数据信息 | 后继结点1 | 后继结点2 |… …|后继结点k|
|————|———|———|———|———|
| $data$ | $child_1$ | $child_2$ |… …|$child_k$ |

缺点：不一定每一个结点的度都是$k$，所以浪费存储空间。

不定长结点的多重链表结构

每个链结点的构造：
| 结点数据信息 | 结点的度 |后继结点1 | 后继结点2 |… …|后继结点k|
|————|———|———|———|———|———|
| $data$ |$k$| $child_1$ | $child_2$ |… …|$child_k$ |

缺点：对树的操作不方便。

三重链表结构

二叉树

二叉树在树的基础上，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的树有左右之分，即是有序树。

注意：如果二叉树的某个结点只有一棵子树，也要区分子树是左子树还是右子树。

二叉树和度为2的有序树的区别：

度为2的树至少有3个结点，而二叉树可以为空。
度为2的有序树的孩子的左右次序是相对另一个孩子而言的，如果某个结点只有一棵子树，无需分辨是左子树还是右子树，但是二叉树需要区分单一后继结点是左子树还是右子树。

特殊的二叉树

满二叉树

一棵高度为$h$的二叉树，且有$2^h-1$个结点的二叉树，即二叉树每层都含有最多的结点，除了叶结点外，所有结点的度均为2。

完全二叉树

高度为$h$，有$n$个结点的二叉树，当且仅当每个结点都与高度为$h$的满二叉树中编号$1$~$n$的结点一一对应。可以理解为：满二叉树删去最底层最右边的一些结点。

完全二叉树的特点：

若$i \leq \lfloor n/2 \rfloor$，则结点$i$为分支节点，否则为叶结点。
叶结点只可能在最下面两层出现，对于最大层次的叶结点，都依次排列在该层最左边的位置上。
若有度为$1$的结点最多只有$1$个，且该结点只有左孩子而无右孩子。
若$n$为奇数，则每个分支结点都有左孩子和右孩子，否则编号最大的分支结点（编号为$n/2$）只有左孩子，没有右孩子。

平衡二叉树

树中任意一个结点的左子树和右子树的高度差的绝对值不超过1。

二叉树的性质

非空二叉树的叶结点数等于度为2的结点数加1，即$n_0=n_2+1$。

二叉树的存储结构

二叉树的顺序存储结构

对于一个高度为$h$的二叉树，存储在一个大小为$2^h-1$的一维数组里。结点的存储顺序是假设二叉树是满二叉树按层存储，如果位置上没有结点，则存储0元素。

缺点：非满二叉树浪费存储空间。

二叉树的链式存储结构

可以通过添加父结点的指针变成三叉链表。

二叉树的遍历

按照一定的顺序对二叉树中每一个结点都访问一次(仅访问一次), 得到一个由该二叉树的所有结点组成的序列。\
常见的遍历次序有先序(PreOrder)，中序(InOrder)和后序(PostOrder)遍历，其中的“序”指的是根结点在何时被访问。三种遍历算法的时间复杂度均为$O(n)$。

先序遍历

顺序：访问根结点，先序遍历左子树，先序遍历右子树。

中序遍历

顺序：中序遍历左子树，访问根结点，中序遍历右子树。

后序遍历

顺序：后序遍历左子树，后序遍历右子树，访问根结点。

递归算法和非递归算法的转换

使用逻辑结构栈。为什么使用栈呢？因为递归的本质也是用栈保存每一层递归函数的结果。

中序遍历：

沿着根的左孩子，依次入栈，直到左孩子为空
栈顶元素出栈并访问：若其右孩子为空，继续执行2
若其右孩子不空，将右子树转执行1

前序遍历：

从根结点开始，访问元素，将其入栈，并沿着根的左孩子，依次入栈，直到左孩子为空
栈顶元素出栈：若其右孩子为空，继续执行2
若其右孩子不空，将右子树转执行1

后序遍历：
<!—

从根结点开始，将其入栈，并沿着根的左孩子，依次入栈，直到左孩子为空
—>
手敲代码实现对二叉树的前序/中序/后序遍历的递归和非递归算法，并计算时间和空间复杂度。
层次遍历
使用逻辑结构队列实现树的层次遍历。
由遍历序列构造二叉树
已知前序序列和中序序列：在前序序列中确定根; 到中序序列中分左右。\
已知中序序列和后序序列：在后序序列中确定根; 到中序序列中分左右。
线索二叉树
线索二叉树是基于二叉树遍历得到的序列的升级后的二叉树。二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。前驱和后继是二叉树遍历得到的序列中的直接前驱和直接后继。

引入线索二叉树的目的：加速查找结点前驱和后继的速度。

线索二叉树的构造：利用链结点的空的左指针域存放该结点的直接前驱的地址，空的右指针域存放该结点直接后继的地址；而非空的指针域仍然存放结点的左孩子或右孩子的地址。

手敲代码实现前序/中序/后序线索二叉树的构造

树、森林与二叉树的转换

树转换为二叉树：每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟。“左孩子右兄弟”。

森林转换为二叉树：将森林里的每棵树转换成二叉树；在每棵树的原始根之间连线；以第一棵树的根为轴心顺时针旋转$45^。$。

树的基础

树的基础知识。

树