选讲树和二叉树解析.pptx

会计学1选讲树和二叉树解析选讲树和二叉树解析预习检查预习检查n n什么是二叉树n n树的遍历有哪几种方式n n树有那些应用第1页/共41页2023/3/133 本章目标了解树的定义和基本术语 了解二叉树的定义、性质、和存储结构掌握二叉树的遍历第2页/共41页本章结构本章结构树的逻辑结构和存储结构树的逻辑结构和存储结构树和二叉树二叉树遍历二叉树第3页/共41页2023/3/135 5 5.1.1.1.1树型结构实例树型结构实例 1 1家族树家族树 5 5-1-1 树的逻辑结构和存储结构树的逻辑结构和存储结构 图图5-15-1家族树家族树 第4页/共41页2023/3/1362 2书的目录结构书的目录结构 图图5-25-2书的目录书的目录 5 5-1-1 书的目录结构书的目录结构第5页/共41页2023/3/137 5 5.1.1.2 2 树的定义树的定义 1树的定义 树(Tree)是n(n0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件：(1)有且仅有一个结点没有前驱，称该结点为根结点(Root)；(2)除根结点以外，其余结点可分为m(m0)个互不相交的有限集合T0，Tl，Tm-1。其中每个集合又构成一棵树，树T0，Tl，Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个每棵子树的根结点有且仅有一个直接直接前驱，前驱，但可以有但可以有0 0个或多个后继。个或多个后继。树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。5 5-1-1 树的逻辑结构和存储结构树的逻辑结构和存储结构 第6页/共41页2023/3/138图图5-35-3树的示例树的示例 图图5-3(a)5-3(a)是一棵只有一个根结点的树；是一棵只有一个根结点的树；图图5-35-3(b)(b)是是一一棵棵有有1212个个结结点点的的树树，即即T=AT=A，B B，C C，K K，LL。A A是是棵棵根根，除除根根结结点点A A之之外外，其其余余的的1111个个结结点点分分为为三三个个互互不不相相交交的的集集合合。T1T1，T2T2和和T3T3是是根根A A的的三三棵棵子子树树，且且本本身身又又都都是是一一棵棵树。树。所以树的所以树的定义是递归的是递归的 。第7页/共41页2023/3/1392 2树的基本术语树的基本术语 树的结点包含一个数据元素及若干指向其子树的分支。树的结点包含一个数据元素及若干指向其子树的分支。1.树的结点:包含一个DE和指向其子树的所有分支;2.结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值 Max(D(I)含义:树中最大分支数为树的度;4.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度5.森林:是m(m=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换.6.有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。第8页/共41页2023/3/13107.森林:是m（m0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：8.孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。9.子孙:以某结点为根的子树中的所有结点都被称为是该结点的子孙。10.祖先:从根结点到该结点路径上的所有结点。11.兄弟:同一个双亲的孩子之间互为兄弟。12.堂兄弟:双亲在同一层的结点互为堂兄弟。第9页/共41页2023/3/13113.3.树的基本运算树的基本运算树的基本运算主要有：初始化操作INITIATE(T)：创建一棵空树。求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。求双亲函数PARENT(T,x)：在树T中求x的双亲。求第i个孩子函数CHILD(T,x,i)：在树T中求结点x的第i个孩子。建树函数CRT-TREE(x,F)：建立以结点x为根，森林F为子树的树。6.遍历树操作TRAVERSE(T)：按顺序访问树T中各个结点。第10页/共41页2023/3/13121 1树的遍历树的遍历 所所谓谓树树的的遍遍历历，就就是是按按照照某某种种顺顺序序依依次次访访问问树树中中各各个个结结点点，并并使使得得每每个个结结点点只只被被访访问问一一次次。也也就就是是把把非非线线性性结结构构的的树树结结点点变变成成线性序列的一种方式线性序列的一种方式 。树树的的遍遍历历可可以以按按深深度度优优先先遍遍历历，也也可可以以按按照照广广度度优优先先（按按层层次）遍历。深度优先遍历通常有两种方式：次）遍历。深度优先遍历通常有两种方式：前序前序遍历和遍历和后序后序遍历。遍历。(1)(1)前序遍历的递归定义：前序遍历的递归定义：若树若树T T非空，则：非空，则：访问根结点访问根结点R R；按按照照从从左左到到右右的的顺顺序序依依次次前前序序遍遍历历根根结结点点R R的的各各子子树树T T1 1，T T2 2，T Tk k。5 5-1-5-1-5 树的遍历树的遍历第11页/共41页2023/3/1313(2)(2)后序遍历的递归定义：后序遍历的递归定义：若树若树T T非空，则：非空，则：按照从左到右的顺序依次后序遍历根按照从左到右的顺序依次后序遍历根T T的各子树的各子树T Tl l，T T2 2，T Tk k；访问根结点访问根结点R R。(3)(3)广度优先（按层）遍历广度优先（按层）遍历广广度度优优先先（按按层层次次）遍遍历历定定义义为为：先先访访问问第第一一层层结结点点（即即树树根根结结点点），再再从从左左至至右右访访问问第第二二层层结结点点，依依次次按按层层访访问问，直直到到树树中中结结点点全全部部被被访访问问为为止止。对对图图6-66-6(a)a)中中的的树树进进行行按按层层次次遍遍历历得得到到树树的的广广度度优优先先遍遍历历序序列为：列为：ABCDEFGABCDEFG。说明：说明：前前序序遍遍历历一一棵棵树树恰恰好好等等价价于于前前序序遍遍历历该该树树所所对对应应的的二二叉叉树树。（6.26.2节节将介绍二叉树）将介绍二叉树）后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。第12页/共41页2023/3/1314树的先序遍历算法描述如下：树的先序遍历算法描述如下：voidPreorder(Btree*root)/先根遍历k叉树if(root!=NULL)printf(“%cn”,root-data);/访问根结点for(i=0;iti);/递归前序遍历每一个子结点第13页/共41页2023/3/1315 5 5.2.1.2.1二叉树的定义与性质二叉树的定义与性质 二叉树(Binary Tree)是另一种重要的树型结构。是度为2的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。1 1二叉树的递归定义二叉树的递归定义 二叉树(BinaryTree)是n(n0)个结点的有限集。它或者是空集(n=0)，或者同时满足以下两个条件：(1)有且仅有一个根结点；(2)其余的结点分成两棵互不相交的左子树和右子树。5 5-2 2 二叉树二叉树第14页/共41页2023/3/1316 二二叉叉树树与与树树有有区区别别：树树至至少少应应有有一一个个结结点点，而而二二叉叉树树可可以以为为空空；树树的的子子树树没没有有顺顺序序，但但如如果果二二叉叉树树的的根根结结点点只只有有一一棵棵子子树树，必必须须明明确确区区分分它它是是左左子子树树还还是是右右子子树树，因因为为两两者者将将构构成成不不同同形形态态的的二二叉叉树树。因因此此，二二叉树不是树的特例。它们是两种不同的数据结构。叉树不是树的特例。它们是两种不同的数据结构。二叉树有二叉树有5 5种基本形态：种基本形态：图图5-75-7二叉树的五种基本形态二叉树的五种基本形态(a)a)空二叉树空二叉树 (b)b)只有根结点的二叉树只有根结点的二叉树(c)c)右子树为空的二叉树右子树为空的二叉树 (d)d)左子树为空的二叉树左子树为空的二叉树(e)e)左右子树均不为空的二叉树左右子树均不为空的二叉树 第15页/共41页2023/3/1317两种特殊形态的二叉树：满二叉树和完全二叉树。满二叉树和完全二叉树。(1)满二叉树(FullBinaryTree)深度为k，且有2k-1个结点的二叉树。特点：（1）每一层上结点数都达到最大 （2）度为1的结点n1=0，树叶都在最下一层上。结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。1237654K=3n=23-1=7满二叉树第16页/共41页2023/3/1318 (2)(2)完全二叉树完全二叉树(Complete BinaryTree)Complete BinaryTree)深度为深度为k k，结点数为结点数为n n的二叉树，当且仅当每个结点的编号都与相同深的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从度的满二叉树中从1 1到到n n的结点一一对应时，称为完全二叉树。的结点一一对应时，称为完全二叉树。图5-8 完全二叉树完全二叉树的特点：（1）每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0或1，即叶结点只可能出现在层次最大或次最大的两层上。（2）完全二叉树结点数n满足2k-1-1n2k-1（3）满二叉树一定是完全二叉树，反之不成立。45213第17页/共41页2023/3/13191324653241LH1=3RH1=1LH1-RH1=2非完全二叉树非完全二叉树非完全二叉树非完全二叉树LHLH2 2=0=0RHRH2 2=1=1LH2-RH2=0-1=-1第18页/共41页2023/3/13202 2二叉树的性质二叉树的性质 性质1 在二叉树的第i层上至多有2i-1 个结点(i1)。性质2 深度为k的二叉树至多有2k-1个结点(k1)。（深度一定，二叉树的最大结点数也确定）性质3 二叉树中,终端结点数n0与度为2的结点数n2有如下关系:n0=n2+1 性质4 结点数为n的完全二叉树，其深度为 log2n+l 性质5 在按层序编号的n个结点的完全二叉树中，任意一结点i(1in)有：i=1时，结点i是树的根；否则，结点i的双亲为结点 i/2(i1)。2in时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。2i+1n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。第19页/共41页2023/3/1321链式存储结构链式存储结构 （二叉链表）设计不同的结点结构，可以构成不同的链式存储结构。常用的有：二叉链表 三叉链表 线索链表 用空链域存放指向前驱或后继的线索第20页/共41页2023/3/1322 由于二叉树每个结点至多只有2个孩子，分别为左孩子和右孩子。因此可以把每个结点分成三个域：一个域存放结点本身的信息，另外两个是指针域，分别存放左、右孩子的地址。每个结点的结构表示为：其中左链域lchild为指向左孩子的指针，右链域rchild为指向右孩子的指针，数据域data表示结点的值。若某结点没有左孩子或右孩子，其相应的链域为空指针。对应的结构类型定义如下：对应的结构类型定义如下：typedefstructnodetypedefstructnodeElemTypedata;ElemTypedata;structnode*lchild;structnode*lchild;structnode*rchild;structnode*rchild;BTree,*tree;BTree,*tree;其中，其中，treetree是指向根结点的指针。是指向根结点的指针。第21页/共41页2023/3/1323二叉链表的结点结构lchilddatarchildD二叉树二叉树CEBAACBDE二叉链表二叉链表说明：说明：一一个个二二叉叉链链表表由由根根指指针针rootroot唯唯一一确确定定。若若二二叉叉树树为为空空，则则root=NULLroot=NULL；若若结点的某个孩子不存在，则相应的指针为空。结点的某个孩子不存在，则相应的指针为空。具具有有n n个个结结点点的的二二叉叉链链表表中中，共共有有2 2n n个个指指针针域域。其其中中只只有有n-1n-1个个用用来来指指示示结点的左、右孩子，其余的结点的左、右孩子，其余的n+1n+1个指针域为空。个指针域为空。第22页/共41页2023/3/1324lchilddataparentrchildD二叉树二叉树CEBAACBDE三叉链表三叉链表3 3带双亲指针的二叉链表带双亲指针的二叉链表 由于经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。就是三叉链表。三叉链表的结点结构性质性质6 6 含有含有n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空链域个空链域。二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。第23页/共41页2023/3/13251 1二叉树的基本运算二叉树的基本运算（1 1）Inittree(&T)Inittree(&T)功能：初始化操作功能：初始化操作(建立一棵空的二叉树建立一棵空的二叉树)。（2 2）Root(T)Root(T)功能：求二叉树的根。功能：求二叉树的根。（3 3）Parent(T,x)Parent(T,x)功能：求二叉树功能：求二叉树T T中值为中值为x x的结点的双亲。的结点的双亲。（4 4）Lchild(T,x)Lchild(T,x)功能：求结点的左孩子。功能：求结点的左孩子。（5 5）Rchild(T,x)Rchild(T,x)功能：求结点的右孩子。功能：求结点的右孩子。（6 6）Traverse(T)Traverse(T)功能：遍历或访问二叉树功能：遍历或访问二叉树T T。（7 7）creatree(&T)creatree(&T)功能：创建二叉树功能：创建二叉树T T5 5-2-32-3 二叉树的基本运算节实现二叉树的基本运算节实现第24页/共41页2023/3/1326 2 2二叉树部分运算的算法描述二叉树部分运算的算法描述 (1)(1)创建二叉树创建二叉树creatree(&root,str)creatree(&root,str)：功能：创建二叉树T。算法描述如下：voidcreatree(BTree*b,char*str)BTree*stackMAXSIZE,p=NULL;inttop=-1,k,j=0;charch;*b=NULL;ch=strj;while(ch!=0)switch(ch)case(：top+;stacktop=p;k=1,break;/为左结点case)：top-;break;case,：k=2;break;/为右结点default：p=(BTree*)malloc(sizeof(BTree);p-data=ch;p-lchild=p-rchild=NULL;第25页/共41页2023/3/1327p-data=ch;p-lchild=p-rchild=NULL;if(*b=NULL)/为根结点*b=p;elseswitch(k)case1：stacktop-lchild=p;break;case2：stacktop-rchild=p;break;j+;ch=strj;第26页/共41页2023/3/1328(2)(2)查找给定的结点find(root(root，x)x)(3)(3)找左孩子结点找左孩子结点lchild(p)lchild(p)或右孩子结点或右孩子结点rchild(p)rchild(p)(4)(4)输出二叉树输出二叉树disptree(root)disptree(root)第27页/共41页2023/3/13295.3.15.3.1遍历二叉树遍历二叉树 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，使得每一个结点仅切仅被访问一次。遍历二叉树：指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。遍历对线性结构是容易解决的。而二叉树是非线性的，因而需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。5-35-3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 第28页/共41页2023/3/1330 访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。遍历的次序：假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右先左后右，则只有前三种情况，分别规定为：DLR先（根）序遍历，LDR中（根）序遍历，LRD后（根）序遍历。1 1遍历方案遍历方案 LDR 中序遍历中序遍历；LRD 后序遍历后序遍历；DLR 先序遍历先序遍历第29页/共41页2023/3/13311）中序遍历二叉树算法思想:若二叉树非空，则：1）中序遍历左子树2）访问根结点3）中序遍历右子树算法描述:voidInorder(BiTreebt)/bt为根结点指针if(bt)/根非空Inorder(bt-lchild);visit(bt-data)visit(bt-data)；Inorder(bt-rchild);2）后序遍历二叉树算法思想:若二叉树非空，则：1）后序遍历左子树2）后序遍历右子树3）访问根结点算法描述:voidPostorder(BiTreebt)/bt为根结点指针if(bt)Postorder(bt-lchild);Postorder(bt-rchild);visit(bt-data)visit(bt-data)；第30页/共41页2023/3/13323）先序遍历二叉树算法思想:若二叉树非空，则：1）访问根结点2）先序遍历左子树3）先序遍历右子树算法描述:voidPreorder(BiTreebt)/bt为根结点指针if(bt)/根非空visit(bt-data)visit(bt-data)；Preorder(bt-lchild);Preorder(bt-rchild);例：表达式a+b(c-d)-e/facdefb+遍历结果遍历结果:中序中序:a+bc-d-e/f后序后序:abcd-+ef/-先序先序:-+ab-cd/ef第31页/共41页2023/3/1333（1 1）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：#includestdio.hincludestdio.htypedefcharElemType;typedefcharElemType;typedefstructnode/typedefstructnode/定义链表结构定义链表结构ElemTypedata;/ElemTypedata;/定义结点值定义结点值structnode*lchild;/structnode*lchild;/定义左子结点指针定义左子结点指针structnode*rchild;/structnode*rchild;/定义右子结点指针定义右子结点指针 BTree;BTree;preorder(BTree*root)/preorder(BTree*root)/前序遍历前序遍历if(root!=NULL)/if(root!=NULL)/如果不是空结点如果不是空结点printf(printf(“%cncn”,root-data);/,root-data);/输出当前结点值输出当前结点值preorder(root-lchild);/preorder(root-lchild);/递归前序遍历左子结点递归前序遍历左子结点preorder(root-rchild);/preorder(root-rchild);/递归前序遍历右子结点递归前序遍历右子结点 return;/return;/结束结束 2 2遍历算法遍历算法第32页/共41页2023/3/1334voidinorder(BTree*root)/voidinorder(BTree*root)/中序遍历中序遍历if(root!=NULL)/if(root!=NULL)/如果不是空结点如果不是空结点inorder(root-lchild);/inorder(root-lchild);/递归中序遍历左子结点递归中序遍历左子结点printf(printf(“%cncn”,root-data);/,root-data);/输出当前结点值输出当前结点值inorder(root-rchild);/inorder(root-rchild);/递归中序遍历右子结点递归中序遍历右子结点 (3)(3)后序遍历的算法实现后序遍历的算法实现 voidpostorder(BTree*root)/voidpostorder(BTree*root)/后序遍历后序遍历if(root!=NULL)/if(root!=NULL)/如果不是空结点如果不是空结点postorder(root-lchild);/postorder(root-lchild);/递归后序遍历左子结点递归后序遍历左子结点postorder(root-rchild);/postorder(root-rchild);/递归后序遍历右子结点递归后序遍历右子结点printf(“printf(“%cn”,root-data);/cn”,root-data);/输出当前结点值输出当前结点值（2 2）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算法如下（假定结点的元素值为字符型）：第33页/共41页2023/3/1335void inorder(BiTree bt)InitStack(s)；Push(s,bt)；while(!StackEmpty(s)while(GetTop(s)Push(s,GetTop(s)-lchild)；p=POP(s)p=POP(s)；if(!StackEmpty(s)visit(GetTop(s)-data)；p=Pop(s)；Push(s,p-rchild);中序遍历非递归算法,s为存储二叉树结点指针栈：操作过程：根结点先进栈，左结点紧跟根后面进栈,右结点在根出栈后入栈；每个结点都要进一次和出一次栈，并且总是访问栈顶元素，因此，算法正确，时间复杂度为O(n)。第34页/共41页2023/3/1336 通通过过上上述述三三种种不不同同的的遍遍历历方方式式得得到到三三种种不不同同的的线线性性序序列列，它它们们的的共共同同的的特特点点是是有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，其其余余各各结点都有且仅有一个前驱结点和一个后继结点。结点都有且仅有一个前驱结点和一个后继结点。从二叉树的遍历定义可知，三种遍历算法的不同之处仅在于从二叉树的遍历定义可知，三种遍历算法的不同之处仅在于访问根结点和遍历左右子树的先后关系。访问根结点和遍历左右子树的先后关系。如果在算法中隐去和递如果在算法中隐去和递归无关的语句归无关的语句printf()，则三种遍历算法是完全相同的。遍历二叉则三种遍历算法是完全相同的。遍历二叉树的算法中的基本操作是访问结点，显然，不论按那种方式进行树的算法中的基本操作是访问结点，显然，不论按那种方式进行遍历，对含遍历，对含n个结点的二叉树，其时间复杂度均为个结点的二叉树，其时间复杂度均为O(n)O(n)。所含辅所含辅助空间为遍历过程中占的最大容量，即树的深度。最坏的情况下助空间为遍历过程中占的最大容量，即树的深度。最坏的情况下为为n n，则空间复杂度也为则空间复杂度也为O(n)O(n)。第35页/共41页2023/3/13373 3二叉链表的构造二叉链表的构造(1)基本思想 利用遍历可以实现对结点的一些操作，如求结点的双亲，求结点的孩子等。还可以在遍历过程中生成结点，建立二叉树的存储结构。前面介绍过用栈建立二叉树，此处介绍一种基于先序遍历的二叉树构造方式，即以二叉树的先序序列为输入构造二叉链表。先序序列中必须加入虚结点以示空指针的位置。(2)构造算法（举例说明）第36页/共41页2023/3/1338【例5-4】建立图5-8(a)所示二叉树，其输入的先序序列是：ABDGCEF。【解】假设虚结点输入时以空格字符表示，相应的构造算法为：voidCreateBinTree(BTree*T)/构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身charch;if(ch=getchar()=)*T=NULL;/读入空格，将相应指针置空else/读入非空格*T=(BTree*)malloc(sizeof(BTree);/生成结点(*T)-data=ch；CreateBinTree(&(*T)-lchild)；/构造左子树CreateBinTree(&(*T)-rchild)；/构造右子树调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。第37页/共41页阶段总结阶段总结二叉树的性质有哪些遍历二叉树的三种方式之间的主要不同点树的遍历除了使用递归方式还可以使用什么方式第38页/共41页本章总结本章总结主要讲解树的逻辑结构和存储结构讲解二叉树的定义性质和存储结构重点讲解如何遍历二叉树树的逻辑结构和存储结构树的逻辑结构和存储结构树和二叉树二叉树遍历二叉树第39页/共41页实验实验1n n实验内容实验内容实验内容实验内容nn题目：创建一棵二叉树，加入题目：创建一棵二叉树，加入n n个节点，对此二叉树进行遍历。个节点，对此二叉树进行遍历。n n实验目的实验目的实验目的实验目的 n n熟悉树的存储结构、掌握树的创建、遍历操作。熟悉树的存储结构、掌握树的创建、遍历操作。n n实验分析实验分析实验分析实验分析n n定义树的结构体定义树的结构体n n创建树，生成新的树节点并插入二叉树中创建树，生成新的树节点并插入二叉树中n n对树进行遍历，遍历可以考虑使用递归对树进行遍历，遍历可以考虑使用递归第40页/共41页