树 总述

  1. 云栖社区>
  2. 博客>
  3. 正文

树 总述

yichudu 2014-08-31 10:40:00 浏览745
展开阅读全文

树是n个结点的有限集。

n等于0时,为空树。

n等于1时,为根结点。

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

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

 

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

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

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

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

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

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

 

二叉树

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

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

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

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

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

 

树中数学规律

最优二叉树

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

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

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

 

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

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

 

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

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

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

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

4. 重复步骤23,直至F中剩下最后一棵树为止。

 

平衡二叉树

节点的平衡因子——它的左子树的高度减去它的右子树的高度。
平衡树——树中任意一个结点的平衡因子的绝对值不大于1。

二叉树的遍历

先序:根左右。
中序:左根右。
后序:左右根。
根据先序(或后序)与中序遍历可以唯一地确定一棵二叉树。而只靠先序与后序是不行的。

字典树

又叫Trie树,可以看作是一个确定的有限状态自动机。
树种一个节点的所有子孙都有相同的前缀,故常用于搜索提示。

网友评论

登录后评论
0/500
评论