树的概述
树是一种递归定义的数据结构
树的相关术语
- 节点的度：某一个节点的分支个数
- 树的度：树中所有节点的度的最大值
- 叶子结点：度为零的结点
- 分支结点：度大于零的结点
树的重要性质
- 性质1：二叉树的第i层上至多有2^i-1个节点
- 性质2：深度为k的二叉树上至多含2^i-1个节点
- 性质3：具有n个结点的完全二叉树的深度为[log2n]+1
- 性质4：对完全二叉树而言，2i > n，则该结点没有左孩子；若2i < n,则该结点没有右孩子。
两类特殊的二叉树：
- 满二叉树，每一层都满了
- 完全二叉树，树中所含的n个结点和满二叉树中编号为1至n的结点一一对应
树的存储
顺序存储
即用数组存储，虽然线性结构简单，但是很容易造成大量空间浪费
链式存储
二叉链表
在基础链表的基础上，增加了一个指针域，即两个指针域，一个指向左孩子（左子树的根结点），另一个指向右孩子（柚子树的根结点）
三叉链表
在二叉链表基础上，增加了一个指针域（指向其父结点parent）
双亲链表
每一个结点由三部分组成，data（存放数据）、parent（指向父节点）、LRTag（表示该结点是左孩子还是右孩子）
二叉树的遍历
就二叉树而言，可以有三条搜索路径：
- 先序遍历
- 中序遍历
- 后序遍历
- 按层次遍历
二叉树的遍历算法的应用：
- 统计二叉树中叶子节点的个数
每一次遍历一个结点时，判断其是否为叶子即可，另设一个计数器变量，存储当前叶子数量。 - 求二叉树的深度
某个根结点的二叉树的深度等于左子树和柚子树深度较大者加一，以此递归即可。需要用到后序遍历。 - 复制二叉树
基本操作就是不断生成新的结点，但是结点数据和原来一样。需要用到后序遍历（先生成两个分支结点，最后生成根结点）。 - 建立二叉树的存储结构
需要用到先序遍历。先创建根结点，然后在根结点的两边不断地添加分支结点（即构建左子树和柚子树）。
由二叉树的先序序列和中序序列建树
先序序列得到根结点，代入中序序列得到左子树和柚子树，不断重复这个过程（递归）可以还原整个二叉树。
- 二叉树的层次遍历
即自上而下依次遍历结点；
用到【队列】，使用队列存储每一次将要访问的结点，如果其有左孩子，就让其左孩子入队；如有右孩子，就让右孩子入队。
本质上，这就是图的深度优先算法（BFS）。
线索二叉树
概念
在原二叉树的基础上，给结点增加指向某种遍历下的前驱和后续指针作为线索，行成一棵新的二叉树。
当左子树为空时，就存储某种遍历下的前驱；
当柚子树为空时，就存储某种遍历下的后继。
typedef struct BiThrNode {
TElemType data;
struct BiThrNode *lchild, *rchild;
PointerThr LTag, RTag;
} BiThrNode, *BiThrTree;当当前结点没有孩子时，对应的Tag设为1，并将指针域设为前驱（左孩子）或后继（右孩子）；
有孩子时，对应的Tag设为0，存储的就是正常的左右孩子。
树的表示方法
双亲表示法
每一个结点存储的不仅有数据data，还有其父节点parent的位置
孩子链表表示法
每一个结点存放数据data，父节点下标，和一条由其孩子组成的链表
typedef struct CTNode {
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct {
Elem data;
ChildPtr firstChild;
} CTBox;
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n,r;
} CTree;左孩子右兄弟表示法
对每一个结点，左结点存放原树形结构的左孩子结点，右结点存放原树形结构的同一层的兄弟结点。
森林的遍历
森林的遍历有两种：
- 先序遍历（从左向右依次对森林中的每一棵树进行先序遍历）
- 中序遍历（从左向右依次对森林中的每一棵树进行后序遍历）
哈夫曼树
最优树
- 结点的路径长度：从根结点到该结点的路径上分支的数目
- 树的路径长度：树中每一个结点的路径长度之和
- 树的帶权路径长度：树中所有叶子结点的帶权路径长度之和
最优树的构造————哈夫曼算法
算法思想：
- 根据给定的n个权值，构造n棵二叉树的集合，其中每一棵二叉树左右子树均为空树；
- 在F中选取其根结点的权值为最小的两棵二叉树，分别作为左右子树构造一棵新的二叉树，并将根结点的权值置为左右子树根结点权值之和；
- 从集合F中删去这两棵树，加入新树；
- 重复2、3两步，直至F中只含有一棵树。
