293
树 总述
树
树是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中剩下最后一棵树为止。
平衡二叉树
平衡树——树中任意一个结点的平衡因子的绝对值不大于1。
二叉树的遍历
字典树
树种一个节点的所有子孙都有相同的前缀，故常用于搜索提示。
最后更新：2017-04-03 05:40:09