403
二叉树的性质和应用
二叉树的性质
二叉树是图的一种特殊情形。
二叉树与有序树：在只有一个孩子结点的情况下，二叉树有左右之分、有序树无左右之分。
非空二叉树中，共有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.输出后，将最后一个结点放到堆顶，再自上而下调整，直至叶结点。
最后更新：2017-04-03 12:55:50