树 总述

树

树是n个结点的有限集。

当n等于0时，为空树。

当n等于1时，为根结点。

当n大于1时，其余节点可以分为m个互不相交的有限集T1、T2、...、Tm。每个集合本身又是一棵树，并且称为一根结点的子树。

显然，树是一种递归的数据结构。

树中某结点的孩子个数称为该结点的度。树的度=max{结点的度}。

树中结点数等于所有结点的度数和加1。

结点编号通常从1起，从上到下、从左到右递增。

通常认为树高从1算起，根结点第一层，最后一个叶结点层数最大。

节点间关系有父、祖先、兄弟、孩子、子孙。

两个结点A、B之间的路径就是从A到B所经过的结点的序列。路径长度就是所经过的边的个数。

二叉树

二叉树是度不大于2的 且 单个孩子结点分左右的 有序树。在一棵有序树中，只有一个结点做孩子时不分左右。

二叉树的存储——数组、链表。

满二叉树：除叶节点外每个结点度都为2。

完全二叉树：对一棵满二叉树，从后往前连续删除若干个结点，就成了完全二叉树。

完全二叉树两个特点：(1)叶子节点只出现在最高两层上；(2)度为1的结点最多只能有1个，且它只有左孩子。

树中数学规律

最优二叉树

树中结点的值代表该结点权重。从根到任意结点的路径长度（即经过的边数）与该结点权重之积为该结点的带权路径长度。

树的带权路径长度，WPL，Weighted Path Length of Tree。表示树中所有叶结点的带权路径长度之和。

最优二叉树也称为哈夫曼树。表示带权路径长度最小的二叉树。

对于一个待处理的字符序列，如果对不同字符采用同样的编码长度，这种编码方式叫固定长度编码。如果采用不等长度的二进制位表示，叫可变长度编码。

哈夫曼编码可以对高频字符赋以短编码，达到压缩数据的目的。

给定n个权值分别为w1,w2,、、、,wn的结点，最优二叉树的构造算法如下：

1. 将这n个结点看作n棵二叉树组成的森林F；

2. 构造一个新节点，从森林F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将新结点的权值置为两个选中树根的权值之和。

3. 从F中删除选中的两棵树，并将新构造的树加入F。

4. 重复步骤2和3，直至F中剩下最后一棵树为止。

平衡二叉树

二叉树的遍历

字典树