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

1、树的基础知识,江苏省华罗庚中学 杨志军,树的基本概念,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），

2、3，4（7（8，9）,树的基本概念,（3）树的基本术语 结点的度和树的度 结点的度：每个结点具有的子树的个数或者说其后继结点的个数被定义为该结点的度。 树的度：所有结点的度的最大值定义为该树的度。,树的基本概念,（3）树的基本术语 分支结点和叶子结点 度大于0的结点称为分支结点或非终端结点，度为0的结点称为叶子结点。,树的基本概念,（3）树的基本术语 孩子结点、双亲结点和兄弟结点 每个结点的后继结点被称为该结点的孩子结点，相应的该结点被称为双亲结点或父亲结点。具有同一双亲结点的孩子结点互称为兄弟结点。,树的基本概念,（3）树的基本术语 树的深度和宽度 树中的结点的最大层数称为树的深度或高度。

3、整棵树中某一层中最多的结点数称为树的宽度。,二叉树的基本知识,（1）二叉树的基本概念 二叉树是一种特殊的树型结构，它是度数最多为2的树，即二叉树的每个结点最多有两个子结点。,二叉树的基本知识,（2）二叉树的性质 性质1：在二叉树的第i层上至多有2i-1个结点（i1）。 性质2：深度为h的二叉树至多有2h-1个结点（h1）。 一棵深度为k且有2k-1个结点的二叉树称为满二叉树。,二叉树的基本知识,（2）二叉树的性质 性质3：对任何一棵二叉树，如果其叶结点数n0，度为2的结点数为n2，则一定满足：n0=n2+1。 性质4：具有n个结点的完全二叉树的深度为trunc(log2n)+1。 完全二叉树的

4、定义：深度为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个单元。,二叉树的基本知识,（

5、3）二叉树的存储结构 顺序存储 对一个完全二叉树的所有结点按层编号，将编号为i的结点存入一维数组的第i个单元。,二叉树的基本知识,（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）二叉树的存储结构,二叉树的基本知识,（4）二叉树的建立（顺序存储） s:string; s:=“LD

6、PCFM#EH#N”,二叉树的基本知识,（4）二叉树的建立（顺序存储） string s; s=“LDPCFM#EH#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,二叉树的基本知识,（5）二叉树的基本运算 1、二叉树的输出运算（采用广义表）： 设标记flag=0 如果当前结点不为空，则输出该结点； 如果当前结点的左子树不为空，则输出“（”，flag=1，递归其左子树； 如果当前结点的右子树不为空，若flag=0，则输出“（”，flag=1，否则输出“，”，递归其右子树； 如果f

7、lag=1，则输出“）”。,二叉树的基本知识,（5）二叉树的基本运算 2、二叉树的遍历运算（先序、中序、后序） 先序遍历的操作定义如下： 若二叉树为空，则空操作，否则 访问根结点 先序遍历左子树 先序遍历右子树 A，B，C，D，E，F，G，H,二叉树的基本知识,（5）二叉树的基本运算 2、二叉树的遍历运算（先序、中序、后序） 中序遍历的操作定义如下： 若二叉树为空，则空操作，否则 中序遍历左子树 访问根结点 中序遍历右子树 C，B，A，F，E，G，D，H,二叉树的基本知识,（5）二叉树的基本运算 2、二叉树的遍历运算（先序、中序、后序） 后序遍历的操作定义如下： 若二叉树为空，则空操作，否则

8、后序遍历左子树 后序遍历右子树 访问根结点 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，再遍历左子树，最后遍历右子树。而中序遍历是

9、先遍历左子树，再访问根结点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

10、 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 mr2 then try(l1+m-l2+1,r1,m+1,r2); write(s1l1); end；,先序：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(s1l1); if (ml2)p(l1+1,l1+m-l2,l2

11、,m-1); if (mr2)p(l1+m-l2+1,r1,m+1,r2); couts1l1; ,二叉树的应用,【例2】具有n个结点的不同形态的二叉树有多少棵？ 【样例输入】 3 【样例输出】 5,二叉树的应用,【分析】 一般情况，一棵具有n(n0)个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树、和一棵具有n-1-i个结点的右子树组成，其中0=i=n-1,i=0表示无左子树，i=n-1表示无右子树，根据乘法原理可以得出具有n个结点的不同形态的二叉树有Fn棵。,二叉树的应用,【分析】 F0=1 F1=1 F2=F0*F1+F1*F0=1*1+1*1=2 F3=F0*F2+F1*

12、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、定义 二叉排序树具有这样的性质：任何结点的值都大于它左子树上结点的值，小于右子树上结点的值，然后采用中序遍历就可以生成一个有序序列。,特殊二叉树,（1）二叉排序树 2、建立二叉排序树 先生成一个结点，加入到树中，如果不是根结点，再根据大小决定这个结点是插在某个节点的左子树上还是右子树上，如此重复。 例：3 1 2 4 6 5,3,1,4,2,6,5,特殊二叉树,（1）二叉排序树 3、二叉排序树的查找 从根结点开始，如果要查找的数与该结点不相等，则

13、根据与该结点的值比较，选择查找左子树，还是右子树，直到没有结点。 例：查找2 例：查找7,特殊二叉树,（2）哈夫曼树 1、定义 树的带权路径长度为树中所有叶子结点的带权路径长度之和，也称WPL。 哈夫曼树又称为最优二叉树，它是n个带权叶子结点构成的二叉树中WPL最小的二叉树。,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的根结点，其左、右子树

14、为空树； 在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和； 从F中删去这两棵树，同时加入刚生成的新树； 重复和 两步，直到F中只含一棵树为止。,特殊二叉树,（2）哈夫曼树 例：对权值分别是3,1,4,5,1,3的结点构造哈夫曼树。,3,1,4,5,1,3,初赛试题,（noip2014普及组选择题第16题） 1、一棵具有5层的满二叉树中结点数为（ ）。 A. 31B. 32C. 33D. 16 （noip2015提高组问题求解第2题） 2、结点数为5的不同形态的二叉树一共有 种。（结点数为2的二叉树一共有2种：一种是根结点和左儿子，另一种是根结点和右儿子。）,初赛试题,（noip2016普及组选择题第11题） 3、一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标(2i+1)处），则图中所有结点的最大下标为（ ）。 A. 6B. 10C. 12D. 15,初赛试题,（noip2015普及组选择题第17题、提高组选择题第8题） 4、如果根的高度为1，具有61个结点的完全二叉树的高度为（ ）。 A. 5B