NOIP普及讲座5-树的基础知识ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,*,树的基础知识,江苏省华罗庚中学 杨志军,树的基本概念,01,二叉树的基本知识,02,二叉树的应用,03,特殊二叉树,04,Table of Contents,内容大纲,树的基本概念,（,1,）树的定义,树是,n,（,n0,）个结点的有穷集合，满足：,有且仅有一个称为根的结点；,其余结点分为,m,（,m0,）个互不相交的非空集合,T1,，,T2,，,，,Tm,，这些集合中的每一个都是一棵树，称为根的子树。,树的基本概念,（,2,）树的表示方法,图示表示：,广义表表示：,=,（,T,）,=,（,1,（,T1,，,T2,，,T3,）,=,（,1,（,2,（,T11,，,T12,），,3,，,4,（,T31,）,=,（,1,（,2,（,5,，,6,），,3,，,4,（,7,（,T311,，,T312,）,=,（,1,（,2,（,5,，,6,），,3,，,4,（,7,（,8,，,9,）,树的基本概念,（,3,）树的基本术语,结点的度和树的度,结点的度：每个结点具有的子树的个数或者说其后继结点的个数被定义为该结点的度。,树的度：所有结点的度的最大值定义为该树的度。,树的基本概念,（,3,）树的基本术语,分支结点和叶子结点,度大于,0,的结点称为分支结点或非终端结点，度为,0,的结点称为叶子结点。,树的基本概念,（,3,）树的基本术语,孩子结点、双亲结点和兄弟结点,每个结点的后继结点被称为该结点的孩子结点，相应的该结点被称为双亲结点或父亲结点。具有同一双亲结点的孩子结点互称为兄弟结点。,树的基本概念,（,3,）树的基本术语,树的深度和宽度,树中的结点的最大层数称为树的深度或高度。,整棵树中某一层中最多的结点数称为树的宽度。,二叉树的基本知识,（,1,）二叉树的基本概念,二叉树是一种特殊的树型结构，它是度数最多为,2,的树，即二叉树的每个结点最多有两个子结点。,二叉树的基本知识,（,2,）二叉树的性质,性质,1,：在二叉树的第,i,层上至多有,2,i-1,个结点（,i1,）。,性质,2,：深度为,h,的二叉树至多有,2,h,-1,个结点（,h1,）。,一棵深度为,k,且有,2,k,-1,个结点的二叉树称为满二叉树。,二叉树的基本知识,（,2,）二叉树的性质,性质,3,：对任何一棵二叉树，如果其叶结点数,n0,，度为,2,的结点数为,n2,，则一定满足：,n0=n2+1,。,性质,4,：具有,n,个结点的完全二叉树的深度为,trunc(log,2,n)+1,。,完全二叉树的定义：深度为,k,，有,n,个结点的二叉树当且仅当其每一个结点都与深度为,k,的满二叉树中编号从,1,到,n,的结点一一对应时，称为完全二叉树。,二叉树的基本知识,（,2,）二叉树的性质,性质,5,：对于一棵,n,个结点的完全二叉树，对任一个结点（编号为,i,）,如果,i=1,，则结点,i,为根，无父结点；如果,i1,，则其父结点编号为,trunc(i/2),。,如果,2in,，则结点,i,无左孩子，即结点,i,为叶结点；否则左孩子编号为,2i,。,如果,2i+1n,，则结点,i,无右孩子，否则右孩子编号为,2i+1,。,二叉树的基本知识,（,3,）二叉树的存储结构,顺序存储,对一个完全二叉树的所有结点按层编号，将编号为,i,的结点存入一维数组的第,i,个单元。,1,2,3,4,5,6,7,8,9,10,11,12,A,B,I,C,F,J,L,D,E,G,H,K,二叉树的基本知识,（,3,）二叉树的存储结构,顺序存储,对一个完全二叉树的所有结点按层编号，将编号为,i,的结点存入一维数组的第,i,个单元。,L,D,C,P,F,E,H,N,M,1,2,3,4,5,6,7,8,9,10,11,12,13,L,D,P,C,F,M,#,#,#,E,H,#,N,二叉树的基本知识,（,3,）二叉树的存储结构,链式存储,type node=record,data:char;,left,right:longint;,end;,var,a:array1.n of node;,二叉树的基本知识,（,3,）二叉树的存储结构,链式存储,struct node,char data;,int left,right;,;,node a1001;,二叉树的基本知识,（,3,）二叉树的存储结构,L,D,C,P,F,E,H,N,M,1,2,3,4,5,6,7,8,9,data,L,D,P,C,F,M,E,H,N,left,2,4,6,0,7,0,0,0,0,right,3,5,0,0,8,9,0,0,0,二叉树的基本知识,（,4,）二叉树的建立（顺序存储）,s:string;,s:=,“,LDPCFM#EH#N,”,L,D,C,P,F,E,H,N,M,1,2,3,4,5,6,7,8,9,10,11,12,13,L,D,P,C,F,M,#,#,#,E,H,#,N,二叉树的基本知识,（,4,）二叉树的建立（顺序存储）,string s;,s=,“,LDPCFM#EH#N,”,L,D,C,P,F,E,H,N,M,0,1,2,3,4,5,6,7,8,9,10,11,12,L,D,P,C,F,M,#,#,#,E,H,#,N,二叉树的基本知识,（,4,）二叉树的建立（链式存储）,L 2 3,D 4 5,P 6 0,C 0 0,F 7 8,M 0 9,E 0 0,H 0 0,N 0 0,L,D,C,P,F,E,H,N,M,1,2,3,4,5,6,7,8,9,data,L,D,P,C,F,M,E,H,N,left,2,4,6,0,7,0,0,0,0,right,3,5,0,0,8,9,0,0,0,二叉树的基本知识,（,5,）二叉树的基本运算,1,、二叉树的输出运算（采用广义表）：,设标记,flag=0,如果当前结点不为空，则输出该结点；,如果当前结点的左子树不为空，则输出,“,（,”,，,flag=1,，递归其左子树；,如果当前结点的右子树不为空，若,flag=0,，则输出,“,（,”,，,flag=1,，否则输出,“,，,”,，递归其右子树；,如果,flag=1,，则输出,“,）,”,。,二叉树的基本知识,（,5,）二叉树的基本运算,2,、二叉树的遍历运算（先序、中序、后序）,先序遍历的操作定义如下：,若二叉树为空，则空操作，否则,访问根结点,先序遍历左子树,先序遍历右子树,A,，,B,，,C,，,D,，,E,，,F,，,G,，,H,二叉树的基本知识,（,5,）二叉树的基本运算,2,、二叉树的遍历运算（先序、中序、后序）,中序遍历的操作定义如下：,若二叉树为空，则空操作，否则,中序遍历左子树,访问根结点,中序遍历右子树,C,，,B,，,A,，,F,，,E,，,G,，,D,，,H,二叉树的基本知识,（,5,）二叉树的基本运算,2,、二叉树的遍历运算（先序、中序、后序）,后序遍历的操作定义如下：,若二叉树为空，则空操作，否则,后序遍历左子树,后序遍历右子树,访问根结点,C,，,B,，,F,，,G,，,E,，,H,，,D,，,A,二叉树的基本知识,（,5,）二叉树的基本运算,3,、求二叉树的深度,若二叉树为空，则深度为,0,否则，深度,=,左子树与右子树中最大深度,+1,二叉树的应用,【,例,1】,已知一棵二叉树的先序遍历和中序遍历的结果，请你编程输出这棵二叉树的后序遍历结果。,【,样例输入,】,ABDEGKHCFI,DBKGEHAFIC,【,样例输出,】,DKGHEBIFCA,二叉树的应用,【,分析,】,先序：,A B D E G K H C F I,中序：,D B K G E H A F I C,因为二叉树的先序遍历是先访问根结点,A,，再遍历左子树，最后遍历右子树。而中序遍历是先遍历左子树，再访问根结点,A,，最后遍历右子树，所以结点,A,把中序遍历的字符串分成了两个部分，,A,之前的是左子树上的结点，,A,之后的是右子树上的结点。依此类推，便可得到整个二叉树。,二叉树的应用,【,分析,】,先序：,A B D E G K H C F I,中序：,D B K G E H A F I C,A,B,D,E,G,K,H,C,F,I,二叉树的应用,【,分析,】,先序：,A B D E G K H C F I,中序：,D B K G E H A F I C,A,B,D,E,G,K,H,C,F,I,B,D,E,G,K,H,先序：,A B D E G K H C F I,中序：,D B K G E H A F I C,procedure try(l1,r1,l2,r2:longint);,var m:longint;,begin,m:=pos(s1l1,s2);,if ml2 then try(l1+1,l1+m-l2,l2,m-1);,if ml2)p(l1+1,l1+m-l2,l2,m-1);,if(mr2)p(l1+m-l2+1,r1,m+1,r2);,cout0),个结点的二叉树可以看成是由一个根结点、一棵具有,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.31B.32C.33D.16,（,noip2015,提高组问题求解第,2,题）,2,、结点数为,5,的不同形态的二叉树一