NOIP普及讲座5-树的基础知识（课堂PPT）

1、1树的基础知识201020304Table of Contents内容大纲内容大纲3树的基本概念（1 1）树的定义）树的定义树是树是n n（n0n0）个结点的有穷集合，满足：）个结点的有穷集合，满足： 有且仅有一个称为根的结点；有且仅有一个称为根的结点； 其余结点分为其余结点分为m m（m0m0）个互不相交的非空集合）个互不相交的非空集合T1T1，T2T2，TmTm，这些集合中的每一个都是一棵树，称为根的，这些集合中的每一个都是一棵树，称为根的子树。子树。4树的基本概念（2 2）树的表示方法）树的表示方法 图示表示：图示表示： 广义表表示：广义表表示：= =（T T）= =（1 1（T1T1，

2、T2 T2 ，T3 T3 ）= =（1 1（2 2（T11T11，T12T12），），3 3，4 4（T31T31）= =（1 1（2 2（5 5，6 6），），3 3，4 4（7 7（T311T311，T312T312）= =（1 1（2 2（5 5，6 6），），3 3，4 4（7 7（8 8，9 9）5树的基本概念（3 3）树的基本术语）树的基本术语 结点的度和树的度结点的度和树的度结点的度：每个结点具有的子树的个数或者说其后继结点结点的度：每个结点具有的子树的个数或者说其后继结点的个数被定义为该结点的度。的个数被定义为该结点的度。树的度：所有结点的度的最大值定义为该树的度。树的度：所有

3、结点的度的最大值定义为该树的度。6树的基本概念（3 3）树的基本术语）树的基本术语 分支结点和叶子结点分支结点和叶子结点度大于度大于0 0的结点称为分支结点或非终端结点，度为的结点称为分支结点或非终端结点，度为0 0的结点的结点称为叶子结点。称为叶子结点。7树的基本概念（3 3）树的基本术语）树的基本术语 孩子结点、双亲结点和兄弟结点孩子结点、双亲结点和兄弟结点每个结点的后继结点被称为该结点的孩子结点，相应的该每个结点的后继结点被称为该结点的孩子结点，相应的该结点被称为双亲结点或父亲结点。具有同一双亲结点的孩结点被称为双亲结点或父亲结点。具有同一双亲结点的孩子结点互称为兄弟结点。子结点互称为兄

4、弟结点。8树的基本概念（3 3）树的基本术语）树的基本术语 树的深度和宽度树的深度和宽度树中的结点的最大层数称为树的深度或高度。树中的结点的最大层数称为树的深度或高度。整棵树中某一层中最多的结点数称为树的宽度。整棵树中某一层中最多的结点数称为树的宽度。9二叉树的基本知识（1 1）二叉树的基本概念）二叉树的基本概念二叉树是一种特殊的树型结构，它是度数最多为二叉树是一种特殊的树型结构，它是度数最多为2 2的树，的树，即二叉树的每个结点最多有两个子结点。即二叉树的每个结点最多有两个子结点。10二叉树的基本知识（2 2）二叉树的性质）二叉树的性质 性质性质1 1：在二叉树的第：在二叉树的第i i层上至

5、多有层上至多有2 2i-1i-1个结点（个结点（i1i1）。）。 性质性质2 2：深度为：深度为h h的二叉树至多有的二叉树至多有2 2h h-1-1个结点（个结点（h1h1）。）。一棵深度为一棵深度为k k且有且有2 2k k-1-1个结点的二叉树称为满二叉树。个结点的二叉树称为满二叉树。 11二叉树的基本知识（2 2）二叉树的性质）二叉树的性质 性质性质3 3：对任何一棵二叉树，如果其叶结点数：对任何一棵二叉树，如果其叶结点数n0n0，度为，度为2 2的结的结点数为点数为n2n2，则一定满足：，则一定满足：n0=n2+1n0=n2+1。 性质性质4 4：具有：具有n n个结点的完全二叉树的

6、深度为个结点的完全二叉树的深度为trunc(logtrunc(log2 2n)+1n)+1。完全二叉树的定义：深度为完全二叉树的定义：深度为k k，有，有n n个结点的二叉树当且仅当其每个结点的二叉树当且仅当其每一个结点都与深度为一个结点都与深度为k k的满二叉树中编号从的满二叉树中编号从1 1到到n n的结点一一对应的结点一一对应时，称为完全二叉树。时，称为完全二叉树。 12二叉树的基本知识（2 2）二叉树的性质）二叉树的性质 性质性质5 5：对于一棵：对于一棵n n个结点的完全二叉树，对任一个结点（编号为个结点的完全二叉树，对任一个结点（编号为i i）如果如果i=1i=1，则结点，则结点i

7、 i为根，无父结点；如果为根，无父结点；如果i1i1，则其父结点编号为，则其父结点编号为trunc(i/2)trunc(i/2)。如果如果2in2in，则结点，则结点i i无左孩子，即结点无左孩子，即结点i i为叶结点；否则左孩子编号为为叶结点；否则左孩子编号为2i2i。如果如果2i+1n2i+1n，则结点，则结点i i无右孩子，否则右孩子编号为无右孩子，否则右孩子编号为2i+12i+1。 13二叉树的基本知识（3 3）二叉树的存储结构）二叉树的存储结构 顺序存储顺序存储对一个完全二叉树的所有结点按层编号，将编号为对一个完全二叉树的所有结点按层编号，将编号为i i的结的结点存入一维数组的第点存

8、入一维数组的第i i个单元。个单元。123456789101112ABICFJLDEGHK14二叉树的基本知识（3 3）二叉树的存储结构）二叉树的存储结构 顺序存储顺序存储对一个完全二叉树的所有结点按层编号，将编号为对一个完全二叉树的所有结点按层编号，将编号为i i的结的结点存入一维数组的第点存入一维数组的第i i个单元。个单元。LDCPFEHNM12345678910111213LDPCFM#EH#N15二叉树的基本知识（3 3）二叉树的存储结构）二叉树的存储结构 链式存储链式存储type node=recordtype node=record data:char;data:char;lef

9、t,right:longint;left,right:longint; end; end;varvar a:array1.n of node; a:array1.n of node;16二叉树的基本知识（3 3）二叉树的存储结构）二叉树的存储结构 链式存储链式存储struct nodestruct node char data;char data;int left,right;int left,right;node a1001;node a1001;17二叉树的基本知识（3 3）二叉树的存储结构）二叉树的存储结构LDCPFEHNM123456789dataLDPCFMEHNleft246070

10、000right35008900018二叉树的基本知识（4 4）二叉树的建立（顺序存储）二叉树的建立（顺序存储）s:string;s:string;s:=“LDPCFM#EH#N”s:=“LDPCFM#EH#N”LDCPFEHNM12345678910111213LDPCFM#EH#N19二叉树的基本知识（4 4）二叉树的建立（顺序存储）二叉树的建立（顺序存储）string s;string s;s=“LDPCFM#EH#N”s=“LDPCFM#EH#N”LDCPFEHNM0123456789101112LDPCFM#EH#N20二叉树的基本知识（4 4）二叉树的建立（链式存储）二叉树的建立（

11、链式存储）L 2 3L 2 3D 4 5D 4 5P 6 0P 6 0C 0 0C 0 0F 7 8F 7 8M 0 9M 0 9E 0 0E 0 0H 0 0H 0 0N 0 0N 0 0LDCPFEHNM123456789dataLDPCFMEHNleft246070000right35008900021二叉树的基本知识（5 5）二叉树的基本运算）二叉树的基本运算 1 1、二叉树的输出运算（采用广义表）：、二叉树的输出运算（采用广义表）： 设标记设标记flag=0flag=0 如果当前结点不为空，则输出该结点；如果当前结点不为空，则输出该结点； 如果当前结点的左子树不为空，则输出如果当前结

12、点的左子树不为空，则输出“（”，flag=1flag=1，递归其左子树；，递归其左子树； 如果当前结点的右子树不为空，若如果当前结点的右子树不为空，若flag=0flag=0，则输出，则输出“（”，flag=1flag=1，否则输出，否则输出“，”，递归其右子树；，递归其右子树； 如果如果flag=1flag=1，则输出，则输出“）”。22二叉树的基本知识（5 5）二叉树的基本运算）二叉树的基本运算2 2、二叉树的遍历运算（先序、中序、后序）、二叉树的遍历运算（先序、中序、后序）先序遍历的操作定义如下：先序遍历的操作定义如下：若二叉树为空，则空操作，否则若二叉树为空，则空操作，否则 访问根结点

13、访问根结点 先序遍历左子树先序遍历左子树 先序遍历右子树先序遍历右子树A A，B B，C C，D D，E E，F F，G G，H H23二叉树的基本知识（5 5）二叉树的基本运算）二叉树的基本运算2 2、二叉树的遍历运算（先序、中序、后序）、二叉树的遍历运算（先序、中序、后序）中序遍历的操作定义如下：中序遍历的操作定义如下：若二叉树为空，则空操作，否则若二叉树为空，则空操作，否则 中序遍历左子树中序遍历左子树 访问根结点访问根结点 中序遍历右子树中序遍历右子树C C，B B，A A，F F，E E，G G，D D，H H24二叉树的基本知识（5 5）二叉树的基本运算）二叉树的基本运算2 2、二

14、叉树的遍历运算（先序、中序、后序）、二叉树的遍历运算（先序、中序、后序）后序遍历的操作定义如下：后序遍历的操作定义如下：若二叉树为空，则空操作，否则若二叉树为空，则空操作，否则 后序遍历左子树后序遍历左子树 后序遍历右子树后序遍历右子树 访问根结点访问根结点C C，B B，F F，G G，E E，H H，D D，A A25二叉树的基本知识（5 5）二叉树的基本运算）二叉树的基本运算3 3、求二叉树的深度、求二叉树的深度若二叉树为空，则深度为若二叉树为空，则深度为0 0否则，深度否则，深度= =左子树与右子树中最大深度左子树与右子树中最大深度+1+126二叉树的应用【例例1 1】已知一棵二叉树的

15、先序遍历和中序遍历的结果，请已知一棵二叉树的先序遍历和中序遍历的结果，请你编程输出这棵二叉树的后序遍历结果。你编程输出这棵二叉树的后序遍历结果。【样例输入样例输入】ABDEGKHCFIABDEGKHCFIDBKGEHAFICDBKGEHAFIC【样例输出样例输出】DKGHEBIFCADKGHEBIFCA27二叉树的应用【分析分析】先序：先序：A B D E G K H C F IA B D E G K H C F I中序：中序：D B K G E H A F I CD B K G E H A F I C因为二叉树的先序遍历是先访问根结点因为二叉树的先序遍历是先访问根结点A A，再遍历左子，再遍

16、历左子树，最后遍历右子树。而中序遍历是先遍历左子树，再访树，最后遍历右子树。而中序遍历是先遍历左子树，再访问根结点问根结点A A，最后遍历右子树，所以结点，最后遍历右子树，所以结点A A把中序遍历的字把中序遍历的字符串分成了两个部分，符串分成了两个部分，A A之前的是左子树上的结点，之前的是左子树上的结点，A A之后之后的是右子树上的结点。依此类推，便可得到整个二叉树。的是右子树上的结点。依此类推，便可得到整个二叉树。28二叉树的应用【分析分析】先序：先序：A B D E G K H C F IA B D E G K H C F I中序：中序：D B K G E H A F I CD B K

17、G E H A F I CABDEGKHCFI29二叉树的应用【分析分析】先序：先序：A B D E G K H C F IA B D E G K H C F I中序：中序：D B K G E H A F I CD B K G E H A F I CABDEGKHCFIBDEGKH30先序：先序：A B D E G K H C F IA B D E G K H C F I中序：中序：D B K G E H A F I CD B K G E H A F I Cprocedure try(l1,r1,l2,r2:longint);procedure try(l1,r1,l2,r2:longint)

18、;var m:longint;var m:longint;beginbegin m:=pos(s1l1,s2); m:=pos(s1l1,s2); if ml2 then try(l1+1,l1+m-l2,l2,m-1); if ml2 then try(l1+1,l1+m-l2,l2,m-1); if mr2 then try(l1+m-l2+1,r1,m+1,r2); if ml2)if (ml2)p(l1+1,l1+m-l2,l2,m-1);p(l1+1,l1+m-l2,l2,m-1);if (mr2)if (mr2)p(l1+m-l2+1,r1,m+1,r2);p(l1+m-l2+1,

19、r1,m+1,r2);couts1l1;cout0)n(n0)个结点的二叉树可以看成个结点的二叉树可以看成是由一个根结点、一棵具有是由一个根结点、一棵具有i i个结点的左子树、和一棵具个结点的左子树、和一棵具有有n-1-in-1-i个结点的右子树组成，其中个结点的右子树组成，其中0=i=n-1,i=00=i=n-1,i=0表示无表示无左子树，左子树，i=n-1i=n-1表示无右子树，根据乘法原理可以得出具表示无右子树，根据乘法原理可以得出具有有n n个结点的不同形态的二叉树有个结点的不同形态的二叉树有FnFn棵。棵。101*niiBnBi34二叉树的应用【分析分析】F0=1F0=1F1=1F1

20、=1F2=F0F2=F0* *F1+F1F1+F1* *F0=1F0=1* *1+11+1* *1=21=2F3=F0F3=F0* *F2+F1F2+F1* *F1+F2F1+F2* *F0=1F0=1* *2+12+1* *1+21+2* *1=51=5Fn=F0Fn=F0* *Fn-1+F1Fn-1+F1* *Fn-2+Fn-2Fn-2+Fn-2* *F1+Fn-1F1+Fn-1* *F0F010*1niFnFi Fni 35特殊二叉树（1 1）二叉排序树）二叉排序树1 1、定义、定义二叉排序树具有这样的性质：任何结点的值都大于它二叉排序树具有这样的性质：任何结点的值都大于它左子树上结点的

21、值，小于右子树上结点的值，然后采用中左子树上结点的值，小于右子树上结点的值，然后采用中序遍历就可以生成一个有序序列。序遍历就可以生成一个有序序列。31426536特殊二叉树（1 1）二叉排序树）二叉排序树2 2、建立二叉排序树、建立二叉排序树先生成一个结点，加入到树中，如果不是根结点，再先生成一个结点，加入到树中，如果不是根结点，再根据大小决定这个结点是插在某个节点的左子树上还是右根据大小决定这个结点是插在某个节点的左子树上还是右子树上，如此重复。子树上，如此重复。例：例：3 1 2 4 6 53 1 2 4 6 531426537特殊二叉树（1 1）二叉排序树）二叉排序树3 3、二叉排序树的

22、查找、二叉排序树的查找从根结点开始，如果要查找的数与该结点不相等，则从根结点开始，如果要查找的数与该结点不相等，则根据与该结点的值比较，选择查找左子树，还是右子树，根据与该结点的值比较，选择查找左子树，还是右子树，直到没有结点。直到没有结点。例：查找例：查找2 2例：查找例：查找7 7314265P PP PP PP PP PP PP P38特殊二叉树（2 2）哈夫曼树）哈夫曼树1 1、定义、定义树的带权路径长度为树中所有叶子结点的带权路径长度树的带权路径长度为树中所有叶子结点的带权路径长度之和，也称之和，也称WPLWPL。哈夫曼树又称为最优二叉树，它是哈夫曼树又称为最优二叉树，它是n n个带

23、权叶子结点构成个带权叶子结点构成的二叉树中的二叉树中WPLWPL最小的二叉树。最小的二叉树。425995245924WPL=5WPL=5* *2+42+4* *2+22+2* *3+93+9* *3=513=51WPL=9WPL=9* *1+51+5* *2+22+2* *3+43+4* *3=373=37WPL=2WPL=2* *2+42+4* *2+52+5* *2+92+9* *2=402=4039特殊二叉树（2 2）哈夫曼树）哈夫曼树2 2、构造哈夫曼树、构造哈夫曼树根据给定的根据给定的n n个权值个权值w1,w2,wnw1,w2,wn，构造，构造n n棵二叉树的棵二叉树的集合集合F=

24、T1,T2,TnF=T1,T2,Tn，其中每棵二叉树中均只含一个带，其中每棵二叉树中均只含一个带权值为权值为wiwi的根结点，其左、右子树为空树；的根结点，其左、右子树为空树；在在F F中选取其根结点的权值为最小的两棵二叉树，分别中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；树根结点的权值为其左、右子树根结点的权值之和；从从F F中删去这两棵树，同时加入刚生成的新树；中删去这两棵树，同时加入刚生成的新树；重复重复和和 两步，直到两步，直到F F中只含一

25、棵树为止。中只含一棵树为止。40特殊二叉树（2 2）哈夫曼树）哈夫曼树例：对权值分别是例：对权值分别是3,1,4,5,1,33,1,4,5,1,3的结点构造哈夫曼树。的结点构造哈夫曼树。2113145135321174353211510532115107431741初赛试题（noip2014noip2014普及组选择题第普及组选择题第1616题）题）1 1、一棵具有、一棵具有5 5层的满二叉树中结点数为（层的满二叉树中结点数为（ ）。）。A. 31A. 31B. 32B. 32C. 33C. 33D. 16D. 16（noip2015noip2015提高组问题求解第提高组问题求解第2 2题）题）2 2、结点数为、结点数为5 5的不同形态的二叉树一共有的不同形态的二叉树一共有 种。种。（结点数为（结点数为2 2的二叉树一共有的二叉树一共有2 2种：一种是根结点和左儿种：一种是根结点和左儿子，另一种是根结点和右儿子。）子，另一种是根结点和右儿子。）42初赛试题（noip2016noip2016普及组选择题第普及组选择题第111