二叉树的性质和应用

二叉树的性质

二叉树是图的一种特殊情形。

二叉树与有序树：在只有一个孩子结点的情况下，二叉树有左右之分、有序树无左右之分。

非空二叉树中，共有n个结点，度为0的结点有n0个，度为1的结点有n1个，度为2的结点有n2个，则n0=n2+1;

推导：n=n0+n1+n2;

           n-1=n1+2*n2;  联立得解。（最爱考这个了...）

非空二叉树第i层上至多有2^(i-1)个结点；//pow(2,i-1)

高为h的二叉树最多有2^h-1个结点；//pow(2,h)-1

完全二叉树的性质：

对完全二叉树按从上到下。从左到右的次序标号1,2，...，n。有如下性质：

1.i>1时，i结点的父节点为int(i/2);

2.i结点的左孩子为2*i，右孩子为2*i+1;

3.i结点所在的层次为int (log(下标：2)(表达式：i))+1;  //floor(log(i)/log(2))+1

二叉排序树

二叉排序树（binary sort tree）又称二叉查找树，亦称二叉搜索树。 特点：左孩子结点值<=根结点值<=右孩子结点值。所以对其中序遍历可得到递增数列。

平衡二叉树（avl）

树中每个结点的左右子树高度差的绝对值<=1。

 最优二叉树

带权路径长度：根结点到x结点的路径长度*x结点的权值；

树的带权路径长度：所有叶子结点的带权路径长度之和；

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(huffman tree)。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

哈夫曼树的构造：

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

1.将每个结点作为一个树，构成森林f；

2.构造一个新结点，从森林f中挑选两个根结点权重最小的树t1与t2作为新结点的左右子树；

3.从f中删除t1、t2，将新构造的树加入f；

4.重复步骤2、3，知道森林中只有一棵树为止。

数据结构：堆——可以看作特殊的完全二叉树。

小根堆中，左孩子结点值与右孩子结点值均小于根结点值。同理有大根堆。用途之一：堆排序。

堆排序需要解决两个问题

1.如何由无序序列组成小根堆？

2.输出最大元素后，如何调整堆？

解答：

1.先将n个元素随意排列成完全二叉树。依次对n、n-1、...、1号结点进行调整。若其值小于父结点，进行对调。

2.输出后，将最后一个结点放到堆顶，再自上而下调整，直至叶结点。