(选讲)树和二叉树解析课件.ppt

1、树和二叉树树和二叉树 预习检查预习检查v什么是二叉树v树的遍历有哪几种方式v树有那些应用2022-12-53本章目标本章目标了解树的定义和基本术语了解树的定义和基本术语 了解二叉树的定义、性质、和存储结构了解二叉树的定义、性质、和存储结构掌握二叉树的遍历掌握二叉树的遍历本章结构本章结构树和二叉树树和二叉树二叉树遍历二叉树2022-12-55 祖父伯父 父亲 叔父堂兄 堂姐 本人 堂弟侄儿(a)家族树家族关系表示：R=,，,，,(b)家族谱系的关系表示2022-12-56数据结构线性表和广义表树图栈队列 树二叉树线性表 广义表栈和队列2022-12-57 1 1树的定义树的定义 树树(Tree)

2、Tree)是是n(nn(n0)0)个结点的有限集个结点的有限集(记为记为T)T)，T T为空时称为空树，为空时称为空树，否则它满足以下两个条件：否则它满足以下两个条件：(1)(1)有且仅有一个结点没有前驱，称该结点为根结点有且仅有一个结点没有前驱，称该结点为根结点(Root)Root)；(2)(2)除根结点以外，除根结点以外，其余结点可分为其余结点可分为m(mm(m0 0)个互不相交的有限集合个互不相交的有限集合T0T0，TlTl，Tm-1Tm-1。其中每个集合其中每个集合又构成一棵树，又构成一棵树，树树T0T0，Tl Tl，Tm-Tm-1 1被称为根结点的子树被称为根结点的子树(Subree

3、)Subree)。树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结明显的层次关系，是一种十分重要的非线性的数据结构。构。2022-12-58AT(a)只有根结点的树ABDCJEGFHKILT1T2T3(b)有12个结点的树定义定义2022-12-591.1.树的结点树的结点:包含一个包含一个DEDE和指向其子树的所有分支和指向其子树的所有分支;2.2.结点的度结点的度:一个结点拥有的子树个数一个结点拥有的子树个数,度为零的结点称为度为零的结点称为叶结

4、点叶结点;3.3.树的度树的度:树中所有结点的度的最大值树中所有结点的度的最大值 Max(D(I)Max(D(I)含义含义:树中最大分支数为树的度树中最大分支数为树的度;4.4.结点的层次及树的深度结点的层次及树的深度:根为第一层根为第一层,根的孩子为第二层根的孩子为第二层,若某结若某结点为第点为第k k层层,则其孩子为则其孩子为k+1k+1层层.树中结点的最大层次称为树中结点的最大层次称为树的深度树的深度或高度或高度5.5.森林森林:是是m(m=0)m(m=0)棵互不相的树的集合棵互不相的树的集合 森林与树概念相近森林与树概念相近,相互很容易转换相互很容易转换.6.有序树、无序树有序树、无序

5、树 如果树中每棵子树从左向右的排列拥有一定的如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。顺序，不得互换，则称为有序树，否则称为无序树。2022-12-5107.7.森林森林:是是m m（m0m0）棵互不相交的树的集合。棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：在树结构中，结点之间的关系又可以用家族关系描述，定义如下：8.8.孩子、双亲孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。被称为孩子的双亲。9.9.子孙子孙:以某结点为根的子树中的所有结点

6、都被称为是该结点的子以某结点为根的子树中的所有结点都被称为是该结点的子孙。孙。10.10.祖先祖先:从根结点到该结点路径上的所有结点。从根结点到该结点路径上的所有结点。11.11.兄弟兄弟:同一个双亲的孩子之间互为兄弟。同一个双亲的孩子之间互为兄弟。12.12.堂兄弟堂兄弟:双亲在同一层的结点互为堂兄弟。双亲在同一层的结点互为堂兄弟。2022-12-511树的基本运算主要有：树的基本运算主要有：初始化操作初始化操作INITIATE(T)INITIATE(T)：创建一棵空树。创建一棵空树。求根函数求根函数ROOT(T)ROOT(T)：求树求树T T的根；的根；ROOT(X)ROOT(X)：求结点

7、求结点x x所在树的所在树的根。根。求双亲函数求双亲函数PARENT(T,x)PARENT(T,x)：在树在树T T中求中求x x的双亲。的双亲。求第求第i i个孩子函数个孩子函数CHILD(T,x,i)CHILD(T,x,i)：在树在树T T中求结点中求结点x x的第的第i i个孩个孩子。子。建树函数建树函数CRT-TREE(x,F)CRT-TREE(x,F)：建立以结点建立以结点x x为根，森林为根，森林F F为子树为子树的树。的树。6.6.遍历树操作遍历树操作TRAVERSE(T)TRAVERSE(T)：按顺序访问树按顺序访问树T T中各个结点。中各个结点。2022-12-5122022

8、-12-5132022-12-514void Preorder(Btree*root)/先根遍历先根遍历k叉树叉树 if(root!=NULL)printf(“%cn”,root-data);/访问根结点访问根结点for(i=0;iti);/递归前序遍历每一个子结点递归前序遍历每一个子结点 2022-12-515 二叉树二叉树(Binary Tree)Binary Tree)是另一种重要的树型结构。是度为是另一种重要的树型结构。是度为2 2的的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。

9、类似，二叉树的定义也可以用递归形式给出。二叉树二叉树(BinaryTree)BinaryTree)是是n(nn(n0)0)个结点的有限集。它或者是空集个结点的有限集。它或者是空集(n=0)n=0)，或者同时满足以下两个条件：或者同时满足以下两个条件：(1)(1)有且仅有一个根结点；有且仅有一个根结点；(2)(2)其余的结点分成两棵互不相交的左子树和右子树。其余的结点分成两棵互不相交的左子树和右子树。2022-12-516 二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确

10、区分的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。叉树不是树的特例。它们是两种不同的数据结构。二叉树有二叉树有5 5种基本形态：种基本形态：(a)(b)(c)(d)(e)2022-12-517两种特殊形态的二叉树两种特殊形态的二叉树(1)(1)满二叉树满二叉树(FullBinaryTree)FullBinaryTree)深度为深度为k k，且有且有2 2k k-1-1个结点的个结点的二叉树二叉树。特点：（特点：（

11、1 1）每一层上结点数都达到最大）每一层上结点数都达到最大 （2 2）度为）度为1 1的结点的结点n n1 1=0=0，树叶都在最下一层上。树叶都在最下一层上。结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。结点进行连续编号。1237654K=3n=23-1=7 满二叉树2022-12-518 (2)(2)完全二叉树完全二叉树(Complete BinaryTree)Complete BinaryTree)深度为深度为k k，结点数为结点数为n n的二叉树，当且仅当每个结点的编号都与相同深的二

12、叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从度的满二叉树中从1 1到到n n的结点一一对应时，称为完全二叉树。的结点一一对应时，称为完全二叉树。图图5-8 5-8 完全二叉树完全二叉树完全二叉树的特点：完全二叉树的特点：（1 1）每个结点）每个结点i i的左子树的深度的左子树的深度LhLhi i-其结点其结点i i的右子树的深度的右子树的深度RhRhi i等等于于0 0或或1 1，即叶结点只可能出现在层次最大或次最大的两层上。，即叶结点只可能出现在层次最大或次最大的两层上。（2 2）完全二叉树结点数）完全二叉树结点数n n满足满足2 2k-1k-1-1-1n2n2k k-1-1（3

13、3）满二叉树一定是完全二叉树，反之不成立。满二叉树一定是完全二叉树，反之不成立。452132022-12-5191324653241LH1=3RH1=1LH1 -RH1=2 非完全二叉树非完全二叉树 非完全二叉树非完全二叉树LHLH2 2=0=0RHRH2 2=1=1LH2-RH2=0-1=-12022-12-520 性质性质1 1 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1 i-1 个结点个结点(i1)i1)。性质性质2 2 深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点(k1)k1)。（深度一定，二叉树的最大结点数也确定）深度一定，二叉树

14、的最大结点数也确定）性质性质3 3 二叉树中二叉树中,终端结点数终端结点数n n0 0与度为与度为2 2的结点数的结点数n n2 2有如下关系有如下关系:n n0=0=n n2 2+1+1 性质性质4 4 结点数为结点数为n n的完全二叉树，其深度为的完全二叉树，其深度为 loglog2 2n n +l+l 性质性质5 5 在按层序编号的在按层序编号的n n个结点的完全二叉树中，任意一结点个结点的完全二叉树中，任意一结点i(1in)i(1in)有：有：i=1i=1时，结点时，结点i i是树的根；否则是树的根；否则，结点结点i i的双亲为结点的双亲为结点 i/2i/2 (i1)i1)。2i 2i

15、n n时，结点时，结点i i无左孩子，为叶结点；否则，结点无左孩子，为叶结点；否则，结点i i的左孩子为结的左孩子为结点点2 2i i。2i+1 2i+1n n时，结点时，结点i i无右孩子；否则，结点无右孩子；否则，结点i i的右孩子为结点的右孩子为结点2 2i+1i+1。2022-12-521二叉链表）二叉链表）设计不同的结点结构，可以构成不同的链式存储结构。常用的有：设计不同的结点结构，可以构成不同的链式存储结构。常用的有：二叉链表二叉链表 三叉链表三叉链表 线索链表线索链表 用空链域存放指向前驱或后继的线索用空链域存放指向前驱或后继的线索2022-12-522 由于二叉树每个结点至多只

16、有由于二叉树每个结点至多只有2个孩子，分别为左孩子和右孩子。因个孩子，分别为左孩子和右孩子。因此可以把每个结点分成三个域：一个域存放结点本身的信息，另外两个此可以把每个结点分成三个域：一个域存放结点本身的信息，另外两个是指针域，分别存放左、右孩子的地址。每个结点的结构表示为：是指针域，分别存放左、右孩子的地址。每个结点的结构表示为：其中左链域其中左链域lchildlchild为指向左孩子的指针，右链域为指向左孩子的指针，右链域rchildrchild为指向右孩子为指向右孩子的指针，数据域的指针，数据域datadata表示结点的值。若某结点没有左孩子或右孩子，其表示结点的值。若某结点没有左孩子或

17、右孩子，其相应的链域为空指针。相应的链域为空指针。Lchild data rchild2022-12-523二叉链表的结点结构二叉链表的结点结构 lchild data rchildD 二叉树二叉树CEBAACBDE二叉链表二叉链表2022-12-524 lchild data parent rchildD 二叉树二叉树CEBAACBDE三叉链表三叉链表 由于经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向由于经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针其双亲的指针parent，形成一个带双亲指针的二叉链表。就是形成一个带双亲指针的二叉链表。就是三叉

18、链表。三叉链表。三叉链表的结点结构三叉链表的结点结构。二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。2022-12-5252022-12-526功能：创建二叉树功能：创建二叉树T T。算法描述如下：算法描述如下：void creatree(BTree*b,char*str)BTree*stackMAXSIZE,p=NULL;int top=-1,k,j=0;char ch;*b=NULL;ch=strj;while(ch!=0)switch(ch)case(：top+;stacktop=p;k=1,break;/为左结点为左

19、结点 case)：top-;break;case,：k=2;break;/为右结点为右结点 default：p=(BTree*)malloc(sizeof(BTree);p-data=ch;p-lchild=p-rchild=NULL;2022-12-527p-data=ch;p-lchild=p-rchild=NULL;if(*b=NULL)/为根结点为根结点 *b=p;else switch(k)case 1：stacktop-lchild=p;break;case 2：stacktop-rchild=p;break;j+;ch=strj;2022-12-528查找给定的结点查找给定的结点

20、find2022-12-529 在二叉树的一些应用中，常常要求在树中查找具有某种特征在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，使得每一个结点仅切仅被访问一次。使得每一个结点仅切仅被访问一次。遍历二叉树：遍历二叉树：指按一定的规律对二叉树的每个结点，指按一定的规律对二叉树的每个结点，访问访问且且仅访问一次的处理过程。仅访问一次的处理过程。遍历对线性结构是容易解决

21、的。而二叉树是非线性的，因而遍历对线性结构是容易解决的。而二叉树是非线性的，因而需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。从而便于遍历。2022-12-530 访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。度、或层次、打印结点的信息，或做其他任何工作。一次遍历后，使树中结点的一次遍历后，使树中结点的非线性非线性排列，按访问的先后顺序变为某种排列，按访问的先后顺序变为某种线性排列线性排列。遍历的

22、次序：遍历的次序：假如以假如以L L、D D、R R分别表示遍历左子树、遍历根结点和遍分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有历右子树，遍历整个二叉树则有DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL、RLDRLD六种遍六种遍历方案。若规定历方案。若规定，则只有前三种情况，分别规定为：，则只有前三种情况，分别规定为：DLRDLR先（根）序遍历，先（根）序遍历，LDRLDR中（根）序遍历，中（根）序遍历，LRDLRD后（根）序遍历。后（根）序遍历。LDR LDR；LRD LRD；DLR DLR 2022-12-5311 1）中序遍历二叉树）中序遍历二叉

23、树算法思想算法思想:若二叉树非空，则：若二叉树非空，则：1）中序遍历左子树）中序遍历左子树2）访问根结点）访问根结点3）中序遍历右子树）中序遍历右子树算法描述算法描述:void Inorder(BiTree bt)/bt为根结点指针为根结点指针 if(bt)/根非空根非空 Inorder(bt-lchild);Inorder(bt-rchild);2 2）后序遍历二叉树）后序遍历二叉树算法思想算法思想:若二叉树非空，则：若二叉树非空，则：1）后序遍历左子树）后序遍历左子树2）后序遍历右子树）后序遍历右子树3）访问根结点）访问根结点算法描述算法描述:void Postorder(BiTree b

24、t)/bt为根结点指针为根结点指针 if(bt)Postorder(bt-lchild);Postorder(bt-rchild);2022-12-5323 3）先序遍历二叉树）先序遍历二叉树算法思想算法思想:若二叉树非空，则：若二叉树非空，则：1）访问根结点）访问根结点2）先序遍历左子树）先序遍历左子树3）先序遍历右子树）先序遍历右子树算法描述算法描述:void Preorder(BiTree bt)/bt为根结点指针为根结点指针 if(bt)/根非空根非空 Preorder(bt-lchild);Preorder(bt-rchild);例：表达式例：表达式a+b(c-d)-e/facdef

25、b+遍历结果遍历结果:中序中序:a+b c-d-e/f后序后序:abcd-+ef/-先序先序:-+a b-cd/ef2022-12-5332022-12-5342022-12-535void inorder(BiTree bt)void inorder(BiTree bt)InitStack(s)InitStack(s)；Push(s,bt)Push(s,bt)；while(!StackEmpty(s)while(!StackEmpty(s)while(GetTop(s)while(GetTop(s)Push(s,GetTop(s)-lchild)Push(s,GetTop(s)-lchild

26、)；if(!StackEmpty(s)if(!StackEmpty(s)visit(GetTop(s)-data)visit(GetTop(s)-data)；p=Pop(s)p=Pop(s)；Push(s,p-rchild);Push(s,p-rchild);中序遍历非递归算法中序遍历非递归算法,s s为存储二叉树结点指针栈：为存储二叉树结点指针栈：操作过程：操作过程：根结点先进栈，左结点根结点先进栈，左结点紧跟根后面进栈紧跟根后面进栈,右结右结点在根出栈后入栈；点在根出栈后入栈；每个结点都要进一次和每个结点都要进一次和出一次栈，并且总是访出一次栈，并且总是访问栈顶元素，问栈顶元素，因此，因此

27、，算法正确，时间复杂度算法正确，时间复杂度为为 O(n)。2022-12-536 通过上述三种不同的遍历方式得到三种不同的线性序列，它们通过上述三种不同的遍历方式得到三种不同的线性序列，它们的共同的特点是有且仅有一个开始结点和一个终端结点，其余各的共同的特点是有且仅有一个开始结点和一个终端结点，其余各结点都有且仅有一个前驱结点和一个后继结点。结点都有且仅有一个前驱结点和一个后继结点。从二叉树的遍历定义可知，三种遍历算法的不同之处仅在于从二叉树的遍历定义可知，三种遍历算法的不同之处仅在于访问根结点和遍历左右子树的先后关系。访问根结点和遍历左右子树的先后关系。如果在算法中隐去和递如果在算法中隐去和

28、递归无关的语句归无关的语句printf()，则三种遍历算法是完全相同的。遍历二叉则三种遍历算法是完全相同的。遍历二叉树的算法中的基本操作是访问结点，显然，不论按那种方式进行树的算法中的基本操作是访问结点，显然，不论按那种方式进行遍历，对含遍历，对含n个结点的二叉树，其时间复杂度均为个结点的二叉树，其时间复杂度均为O(n)O(n)。所含辅所含辅助空间为遍历过程中占的最大容量，即树的深度。最坏的情况下助空间为遍历过程中占的最大容量，即树的深度。最坏的情况下为为n n，则空间复杂度也为则空间复杂度也为O(n)O(n)。2022-12-537(1)基本思想基本思想 利用遍历可以实现对结点的一些操作，如

29、求结点的双亲，求利用遍历可以实现对结点的一些操作，如求结点的双亲，求结点的孩子等。还可以在遍历过程中生成结点，建立二叉树的存结点的孩子等。还可以在遍历过程中生成结点，建立二叉树的存储结构。前面介绍过用栈建立二叉树，此处介绍一种基于先序遍储结构。前面介绍过用栈建立二叉树，此处介绍一种基于先序遍历的二叉树构造方式，即以二叉树的先序序列为输入构造二叉链历的二叉树构造方式，即以二叉树的先序序列为输入构造二叉链表。先序序列中必须加入虚结点以示空指针的位置。表。先序序列中必须加入虚结点以示空指针的位置。(2)(2)构造算法（举例说明）构造算法（举例说明）2022-12-538【例例5-45-4】建立图建立

30、图5-8(a)5-8(a)所示二叉树，其输入的先序序列是：所示二叉树，其输入的先序序列是：ABDGCEFABDGCEF。【解】假设虚结点输入时以空格字符表示，相应的构造算法为：解】假设虚结点输入时以空格字符表示，相应的构造算法为：void CreateBinTree(BTree*T)/构造二叉链表。构造二叉链表。T是指向根指针的指针，故修改是指向根指针的指针，故修改*T就修改了实参就修改了实参(根指针根指针)本身本身 char ch;if(ch=getchar()=)*T=NULL;/读入空格，将相应指针置空读入空格，将相应指针置空 else /读入非空格读入非空格 *T=(BTree*)ma

31、lloc(sizeof(BTree);/生成结点生成结点 (*T)-data=ch；CreateBinTree(&(*T)-lchild)；/构造左子树构造左子树 CreateBinTree(&(*T)-rchild)；/构造右子树构造右子树 调用该算法时，应将待建立的二叉链表的根指针的地址作为实参调用该算法时，应将待建立的二叉链表的根指针的地址作为实参阶段总结阶段总结二叉树的性质有哪些遍历二叉树的三种方式之间的主要不同点树的遍历除了使用递归方式还可以使用什么方式本章总结本章总结主要讲解树的逻辑结构和存储结主要讲解树的逻辑结构和存储结构构讲解二叉树的定义性质和存储结讲解二叉树的定义性质和存储结构构重点讲解如何遍历二叉树重点讲解如何遍历二叉树树和二叉树树和二叉树二叉树遍历二叉树实验实验1v实验内容实验内容题目：创建一棵二叉树，加入n个节点，对此二叉树进行遍历。v实验目的实验目的 熟悉树的存储结构、掌握树的创建、遍历操作。v实验分析实验分析定义树的结构体创建树，生成新的树节点并插入二叉树中对树进行遍历，遍历可以考虑使用递归