树与二叉树

树是一种非线性数据结构，由 n（n≥0） 个有限节点构成具有层次关系的集合。

一些概念

结点：树中的一个独立单元。
结点的度：结点拥有的子树数称为结点的度。
树的度：树内各结点度的最大值。
叶子：度为 0 的结点或终端结点。
非终端结点：度不为 0 的结点。
双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
层次：结点的层次从根开始定义，
根为第一层，根的孩子为第二层，
以此类推。

树的一些普遍性质

$$
\text{性质一：树中所有结点数等于所有结点的度数之和加 1。}
$$

$$
\text{性质二:对于度为 m 的树,第i层上最多有 m}^{i-1}\text{个结点。}
$$

$$
性质三：对于高度为 h，度为 m 的树，最多有(\mathrm{m^h-1})/(\mathrm{m-1})个节点
$$

树的类型

二叉树

二叉树（Binary Tree）是 n（ n>=0）个结点
所构成的集合，它或为空树（n=0），或为非
空树。对于非空树 T：
（1）有且仅有一个称为根的结点
（2）除根结点以外的其余结点分为两个互
不相交的子集 T1 和 T2 ，分别称为 T 的左
子树和右子树，且 T1 和 T2 本身又都是二叉
树。
（3）二叉树每个结点至多只有两棵子树。
（4）二叉树的子树有左右之分，其次序不能任意颠倒。

$$
\text{性质一:二叉树的第i层最多有2}^{\mathrm{i-1}}(i\geqslant1)\text{ 个结点。}
$$

$$
性质二:深度为k的二叉树最多有2^{\mathrm{k-1}}(k\geqslant1)个节点
$$

$$
\begin{aligned}&\text{性质三:对于任何非空的二叉树T,如果叶子结点的个数为n}_0,\text{而度为2的结点数为n}_2,\text{则}\&\mathrm{n_0=n_2+1}\end{aligned}
$$

满二叉树

$$
满二叉树：深度为 k 且含有 2^{\mathrm{k}}-1 个结点的二叉树
$$

所有的叶子结点只能出现在最后一层
对于同样深度的二叉树，满二叉树的结点个数最多，
叶子结点的数量也是最多的。
如果对满二叉树进行编号，根结点从1开始，从上到，
下从左到右，对于编号为i的结点，若存在左孩子，
则左孩子的编号为2i，右孩子为2i+1

完全二叉树

$$
完全二叉树：深度为 k 的、有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k
的满二叉树中编号从 1 至 n 的结点一一对应时，称之为完全二叉树
$$

完全二叉树的定义可能很模糊，我们举个例子。

比如满二叉树

可以发现深度为3，有7个节点。

如果有其子树

可见没有7号节点，但是剩余节点和上面的满二叉树是一一对应的上的，这就是完全二叉树。

但是我们如果删除4号节点，你就会发现，节点相对于满二叉树1-7少了4，所以，这不符合与深度为 k
的满二叉树中编号从 1 至 n 的结点一一对应的定义，所以这不是完全二叉树。

所以，完全二叉树的定义需要配合满二叉树来理解，下面是完全二叉树的性质。

$$
性质一:叶子结点只可能在层次最大的两层上出现；
$$

$$
性质二:对任一结点，若其右分支下的子孙的最大层次为 l，则其左分支下的子孙的最大层次必为 l 或 l+1。
$$

$$
性质三:没有左子树，不能有右子树，上一层没有铺满，不能有下一层
$$

$$
\text{性质四:具有n 个结点的完全二叉树的深度为 log}_2\text{n+1}
$$

实现

typedef char ElemType;

typedef struct TreeNode
{
  ElemType data;
  TreeNode *lchild;
  TreeNode *rchild;
  }TreeNode;
typedef TreeNode* BiTree;//给TreeNode类型的指针起了别名为BiTree

类似于用指向表头的指针来代表链表，我们使用指向根结点的指针来代表整个树。

树的遍历

对于树的遍历，我们需要使用递归。这一块可能很难理解，可以辅助代码可视化。

前序遍历

先访问根结点，然后访问左分支上遇到的每一个结点，持续这一过程，直到遇到空结点为止。这时，返回到最近的有右孩子的祖先结点，并从该结点的右孩子开始继续遍历。

void preOrder(BiTree T) //前序遍历
{
if (T == NULL)
{
	return;
}
	printf("%c ", T->data);
	preOrder(T->lchild);   //先遍历左子节点再遍历右节点
	preOrder(T->rchild);
}

遍历顺序：**A B D H K E C F I G J **

中序遍历

先访问根结点，向树的左下方移动，直到遇到空结点为止，然后访问空结点的父结点。接着继续遍历该结点的右子树，如果右子树没的子树可以遍历，那么继续遍历上一层最后一个未被访问的结点。

void inOrder(BiTree T)
{
	if (T == NULL)
{
return;
}
	inOrder(T->lchild);   //顺序不一样了
	printf("%c ", T->data);
	inOrder(T->rchild);
}

遍历顺序：**H K D B E A I F C G J **

后序遍历

从根结点开始先访问结点的左右儿子，再对该结点进行访问。这就意味着结点的儿子
将在该结点之前输出。

void postOrder(BiTree T)
{
if (T == NULL)
{
return;
}
postOrder(T->lchild);
postOrder(T->rchild);
printf("%c ", T->data);
}

遍历顺序：**K H D E B I F J G C A **

二叉树遍历性质

已知前序遍历和中序遍历，可以唯一确定一棵二叉树。
已知中序遍历和后序遍历，可以唯一确定一棵二叉树。
已知前序遍历和后序遍历，是不能确定一棵二叉树的。

线索二叉树

我们只有通过遍历才能得到二叉树的顺序，但是如果每次遍历都需要直接使用前序/中序/后序遍历的话会有很高的时间复杂度，所以我们考虑使用叶子结点未利用的指针来指向某一种遍历的先后次序，构造时间复杂度为O(n)的链式遍历。

尽管使用一棵树的空余指针只够满足一种遍历方式的链式访问，但是实际上已经足够了。

在使用的过程中不会出现空指针不够用的情况。

实现

typedef char ElemType;
typedef struct ThreadNode
{
	ElemType data;
	struct ThreadNode *lchild;
	struct ThreadNode *rchild;
	int ltag;   //tag等于1时，指向前驱或者后驱，等于0时，指向左节点或者右节点
	int rtag;
}ThreadNode;
	typedef ThreadNode* ThreadTree;

初始化

我们在这里称最后的遍历顺序为一个“链表”

在使用过程中，我们创造一个头节点，他的左指针指向二叉树的根。

右节点指向链表的最后一个节点。

链表的第一个节点的左指针指向头节点

链表的最后一个节点的右指针指向头节点

这么一来，我们构成了一个双向循环链表

如果这个树不再需要修改，使用链表的使用方式去使用可以得到较低的时间复杂度和更高的空间利用效率。

哈夫曼树

路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
路径长度：路径上的分支数目
树的路径长度：从树根到每一个结点的路径长度之和

权：统计学上个体在总体中的权重

结点的权：在实际应用中，给树中的结点赋予代表某种含义的数值
结点的带权路径长度：从该节点到树根之间的路径长度与该结点权的乘积
树的带权路径长度（WPL）：树中所有叶节点的带权路径长度之和

带权路径长度（WPL）最小的树称作哈夫曼树

构造哈夫曼树

将权重从小到大排列

将两个最小权值的点连接同一个新节点。

将新取得的父节点取代原来两个最小节点，加入到原来的有序队列中

重复以上操作直到组成一个树

原理：权重大的距离树根近，权重小的距离树根远，所以乘起来就比较少