# 树

# 树的介绍

1. 树（Tree）是 n 个节点的有限集
2. 有且仅有一个特定的节点称为 == 根（Root）== 节点
3. 其余节点可分为 m 个互不相交的有限集，其中每一个集合有事一棵树，并称为根的子树
4. 树是递归定义的

# 树的基本术语

1. 根节点：非空树中无前驱节点的节点
2. 节点的度：节点拥有的子树数
3. 树的度：树内各节点的度的最大值
4. 内部节点：根节点以外的分支节点称为内部节点
5. 终端节点（叶子）：度为 0 的节点
6. 节点的子树的根称为该节点的孩子，该节点称为孩子的双亲
7. 兄弟节点：双亲在同一层节点上
8. 祖孙节点：从根到该节点所经分支上的所有节点
9. 子孙节点：一个节点的后代节点
10. 树的深度：树的层次数
11. 有序树：树中节点各子树从左到右有次序
12. 无序树：树中节点的各子树无次序
13. 森林：是 m 个互不相交的树

# 二叉树

# 二叉树定义

二叉树是 n 个节点的有限集，它或者是空集，或者由一个根节点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成

# 二叉树的数据类型定义

# 二叉树的抽象数据类型定义

ADT BinaryTree {

​ 数据对象：D 是具有相同特性的数据元素的集合

​ 数据关系：

​ 基本操作：

}

# 二叉树的性质和存储结构

# 二叉树的性质

1. 性质 1：二叉树的第 i 层上之多有$2^{n-1}$ 个节点
2. 性质 2：深度为 k 的二叉树之多有$2^k-1$ 个节点
3. 性质 3：队任何一棵二叉树 T，如果叶子数为$n_0$，度为 2 的节点数为$n_2$，则$n_0=n_2+1$
4. 性质 4：具有 n 个节点的完全二叉树的深度为$\log_2^{n}+1$
5. 性质 5：完全二叉树中双亲节点的编号为 n，左孩子节点编号为 2n，右孩子编号节点的 2n+1
6. 满二叉树：一棵树深度为 k 且有$2^k-1$ 个节点的二叉树称为满二叉树
7. 完全二叉树：深度为 k 的具有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中的编号一一对应时，称为完全二叉树

# 二叉树的存储结构

# 二叉树的顺序存储

实现：按满二叉树的节点层次编号，依次存放二叉树中的数据元素

# 二叉树的链式存储

实现：每个节点有两个指针域，分别指向左孩子和右孩子

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

# 遍历二叉树

# 遍历定义

顺着某一条搜索路径进行寻访二叉树当中的节点

# 先序遍历

1. 访问根节点
2. 先序访问左子树
3. 先序访问右子树

# 中序遍历

1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树

# 后序遍历

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根节点

# 中序遍历非递归算法

# 定义

二叉树的中序遍历的非递归算法的关键：在中序遍历过某节点的整个左子树后，如何找到节点的根以及右子树

# 基本思想

1. 建立一个栈
2. 根节点进栈，遍历左子树
3. 根节点出栈，输出根节点，遍历右子树

# 层次遍历

# 定义

对于一颗二叉树，从根节点开始，按从上到下、从左到右的顺序访问每一个节点

# 基本思想

1. 将根节点进队
2. 对不空时循环：从队列中出一个节点，访问它
   1. 若它有左孩子节点，将左孩子节点进队
   2. 若它有右孩子节点，将右孩子节点进队

# 线索二叉树（Threaded Binary Tree）

# 定义

1. 在二叉树的基础上进行优化，为了提高寻找其中一个节点的前驱和后继的效率
2. 如果某个节点的左孩子为空，则将空的左孩子指针域改为指向其前驱，如果某节点的右孩子为空，则将空的右孩子指针域改为指向其后继，这种改变指向的指针称为 “线索”
3. 添加标记：0 表示该指针域指向孩子节点，1 表示该指针域指向前驱或者后继，如果是左指针域则指向前驱，右指针域指向后继
4. 增加一个头节点：
   1. ltag=0：lchild 指向根节点
   2. ratg=1：rchild 指向遍历序列中的最后一个节点
   3. 遍历序列中第一个节点的 lchild 域和最后一个节点的 rchild 域都指向头节点

# 树和森林

# 树和森林的定义

1. 树：是 n 个节点的有限集
2. 森林：是 m 个互不相交的树的集合

# 树

# 树的存储结构 1（双亲表示）

1. 实现：定义结构数组，存放树的节点，每个节点含两个域
2. 数据域：存放节点本身信息
3. 双亲域：指示本节点的双亲节点在数组中的位置

# 树的存储结构 2（孩子链表）

1. 定义：把每个节点的孩子节点排列起来，看成一个线性表，用单链表存放，则 n 个节点有 n 个孩子链表，而 n 个头指针又组成一个线性表，用顺序表存储

# 树的存储结构 3（孩子兄弟表示法）

1. 实现：用二叉链表作树的存储结构，链表中每个节点的两个指针域分别指向其第一个孩子节点和下一个兄弟节点

# 树和二叉树的转换

1. 定义：左孩子，右兄弟

# 树转换为二叉树

# 二叉树转换为树

# 森林和二叉树的转换

# 森林转换为二叉树

# 二叉树转换成森林

# 树的遍历

# 先根遍历

若树不空，则先访问根节点，然后依次先根遍历各棵子树

# 后根遍历

若树不空，则先依次后根遍历各棵子树，然后访问根节点

# 层次遍历

若树不空，则自上而下自左到右访问树中每个节点

# 哈夫曼树

# 哈夫曼树的基本概念

1. 路径：从树的一个节点到另一个节点之间的分支构成这连个节点间的路径
2. 节点的路径长度：两节点间路径上的分支数
3. 数的路径长度：从树根到每一个节点的路径长度之和（节点数相同的二叉树，完全二叉树是路径长度最短的二叉树）
4. 权（weight）：将树中节点赋给一个有着某些含义的数值，则这个数值称为该节点的权
5. 节点的带权长度：从根节点到该节点之间的路径长度于该节点的权的乘积
6. 数的带权路径长度：树中所有叶子节点的带权路径长度之和
7. 哈夫曼树：带权路径长度最短的树

# 哈夫曼树构造算法

1. 构造森林全是根
2. 选用两小造新树
3. 删除两小添新人
4. 重复 2、3 剩单根

# 哈夫曼编码