noip普及讲座5-树基础知识.pptVIP

先序：A B D E G K H C F I 中序：D B K G E H A F I C void p(int l1,int r1,int l2,int r2) { int m; m=s2.find(s1[l1]); if (ml2) p(l1+1,l1+m-l2,l2,m-1); if (mr2) p(l1+m-l2+1,r1,m+1,r2); couts1[l1]; } l1 r1 l2 r2 m 二叉树的应用 【例2】具有n个结点的不同形态的二叉树有多少棵？ 【样例输入】 3 【样例输出】 5 二叉树的应用 【分析】 一般情况，一棵具有n(n0)个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树、和一棵具有n-1-i个结点的右子树组成，其中0=i=n-1,i=0表示无左子树，i=n-1表示无右子树，根据乘法原理可以得出具有n个结点的不同形态的二叉树有Fn棵。 i个结点 n-1-i个结点 二叉树的应用 【分析】 F0=1 F1=1 F2=F0*F1+F1*F0=1*1+1*1=2 F3=F0*F2+F1*F1+F2*F0=1*2+1*1+2*1=5 …… Fn=F0*Fn-1+F1*Fn-2……+Fn-2*F1+Fn-1*F0 特殊二叉树 （1）二叉排序树 1、定义 二叉排序树具有这样的性质：任何结点的值都大于它左子树上结点的值，小于右子树上结点的值，然后采用中序遍历就可以生成一个有序序列。 3 1 4 2 6 5 特殊二叉树 （1）二叉排序树 2、建立二叉排序树 先生成一个结点，加入到树中，如果不是根结点，再根据大小决定这个结点是插在某个节点的左子树上还是右子树上，如此重复。 例：3 1 2 4 6 5 3 1 4 2 6 5 特殊二叉树 （1）二叉排序树 3、二叉排序树的查找 从根结点开始，如果要查找的数与该结点不相等，则根据与该结点的值比较，选择查找左子树，还是右子树，直到没有结点。 例：查找2 例：查找7 3 1 4 2 6 5 P P P P P P P 特殊二叉树 （2）哈夫曼树 1、定义 树的带权路径长度为树中所有叶子结点的带权路径长度之和，也称WPL。 哈夫曼树又称为最优二叉树，它是n个带权叶子结点构成的二叉树中WPL最小的二叉树。 4 2 5 9 9 5 2 4 5 9 2 4 WPL=5*2+4*2+2*3+9*3=51 WPL=9*1+5*2+2*3+4*3=37 WPL=2*2+4*2+5*2+9*2=40 特殊二叉树 （2）哈夫曼树 2、构造哈夫曼树 ①根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树； ②在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和； ③从F中删去这两棵树，同时加入刚生成的新树； ④重复②和③ 两步，直到F中只含一棵树为止。 特殊二叉树 （2）哈夫曼树 例：对权值分别是3,1,4,5,1,3的结点构造哈夫曼树。 2 1 1 3 1 4 5 1 3 5 3 2 1 1 7 4 3 5 3 2 1 1 5 10 5 3 2 1 1 5 10 7 4 3 17 初赛试题 （noip2014普及组选择题第16题） 1、一棵具有5层的满二叉树中结点数为（ ）。 A. 31 B. 32 C. 33 D. 16 （noip2015提高组问题求解第2题） 2、结点数为5的不同形态的二叉树一共有 种。（结点数为2的二叉树一共有2种：一种是根结点和左儿子，另一种是根结点和右儿子。） 初赛试题 （noip2016普及组选择题第11题） 3、一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标(2i+1)处），则图中所有结点的最大下标为（ ）。 A. 6 B. 10 C. 12 D. 15 初赛试题 （noip2015普及组选择题第17题、提高组选择题第8题） 4、如果根的高度为1，具有61个结点的完全二叉树的高度为（ ）。 A. 5 B. 6 C. 7 D. 8 (noip2016普及组问题求解第2题） 5、约定二叉树的根节点高度为1。一棵结点数为2016的二叉树最少有 个叶子结点；一棵结点数为2016的二叉树最小的高度值是 。 初赛试题