第6章(树和二叉树).ppt
《第6章(树和二叉树).ppt》由会员分享,可在线阅读,更多相关《第6章(树和二叉树).ppt(106页珍藏版)》请在三一办公上搜索。
1、第6章 树和二叉树,6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用,树型结构是一类重要的非线性结构。树结构在客观世界里是大量存在的,树在计算机领域中也有着广泛的应用。,6.1 树的定义和基本术语,1、定义 树是n(n=0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:,(1)有且仅有一个特定的称为根的结点;,(2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,T3,Tm,其中每个子集又是一棵树,并称其为根的子树。,A,只有根结点的树,有子树的树,根,子树,结点表示树中的元素,包括数据项及若干
2、指向其子树的分支,2、基本术语,结点的度(degree)结点拥有的子树数,叶子(leaf)度为0的结点,孩子(child)结点的子树的根称为该结点的孩子,双亲(parents)孩子结点的上层结点叫该结点的双亲,兄弟(sibling)同一双亲的孩子,树的度一棵树中各结点的度的最大值,结点的层次(level)从根结点算起,根为第一层,它的孩子为第二层,深度(depth)树中结点的最大层次数,森林(forest)m(m0)棵互不相交的树的集合,结点A的度:3结点B的度:2结点M的度:0,叶子:K,L,F,G,M,I,J,结点A的孩子:B,C,D结点B的孩子:E,F,结点I 的双亲:D结点L的双亲:E
3、,结点B,C,D为兄弟结点K,L为兄弟,树的度:3,结点A的层次:1结点M的层次:4,树的深度:4,结点F,G为堂兄弟结点A是结点F、G的祖先,2、基本术语,6.2 二叉树,二叉树在树结构的应用中起着非常重要的作用,因为针对二叉树的许多操作算法简单,而任何树都可以与二叉树相互转换,这样就解决了树的存储结构及其运算中存在的复杂性。,二叉树是由n(n=0)个结点的有限集合构成,此集合或者为空集,或者由一个根结点及两棵互不相交的左右子树组成,并且左右子树也都是二叉树。,这也是一个递归定义。二叉树可以是空集合,根也可以有空的左子树或空的右子树。,(a)空二叉树,A,A,B,A,B,A,C,B,(b)根
4、和空的左右子树,(c)根和左子树,(d)根和右子树,(e)根和左右子树,二叉树的5种基本形态,二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也要进行区分,说明它是左子树,还是右子树。这是二叉树与树的最主要的差别。,6.2.1 二叉树的定义,6.2.2 二叉树的性质,二叉树具有下列重要性质:,性质1:在二叉树的第 i 层上至多有2i-1个结点(i1)。,采用归纳法证明此性质。当i=1时,只有一个根结点,2i-1=21-1=20=1,命题成立。,现在假定对所有的j,1ji,命题成立,即第j层上至多有2j-1个结点,那么需要证明当ji时命题也成立。由归纳假设可知,第i-1层上至多有2i-2个
5、结点。,由于二叉树每个结点的度最大为2,故在第i层上最大结点数为第i-1层上最大结点数的2倍,,即22i-22i-1。命题得到证明。,性质2:深度为k的二叉树至多有2k-1个结点(k1)。,深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和,由性质1得到每层上的最大结点数,,性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的 结点数为n2,则n0n21。,设二叉树中度为1的结点数为n1,二叉树中总结点数为N,因为二叉树中所有结点的度均小于或等于2,所以有:Nn0n1n2(6-1),再看二叉树中的分支数,除根结点外,其余结点都有一个进入分支,设B为二叉树中的分支总数,则有:
6、NB1,由于这些分支都是由度为1和2的结点射出的,所以有:Bn1+2n2 因此,NB1n12n21(6-2),由式(6-1)和(6-2)得到:,n0+n1+n2=n1+2n2+1,可得 n0n21,性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的 结点数为n2,则n0n21。,满二叉树,一棵深度为k且有2k-1个结点的二叉树称为满二叉树。下面就是一棵满二叉树,并对结点进行了顺序编号。,下面介绍两种特殊形态的二叉树:满二叉树和完全二叉树。,(a)完全二叉树,(b)非完全二叉树,(c)非完全二叉树,如果深度为k、有n个结点的二叉树中的每个结点能够与深度为k的顺序编号的满二叉树从1到n编
7、号的结点相对应,则称这样的二叉树为完全二叉树。满二叉树是完全二叉树的特例。,完全二叉树的特点,(1)所有的叶结点都出现在第 k 层或第 k-1 层。,(2)对任一结点,若其右分支下的子孙的最大层次为l,则其左分支下的子孙的最大层次必为l或l1。,性质4:具有n个结点的完全二叉树的深度为log2n1。符号 x表示不大于x的最大整数。,假设此二叉树的深度为k,则根据性质2及完全二叉树的定义得:2k-1-1n2k-1 或 2k-1n2k,取对数得到:k-1 log2n k,又因为k是整数,所以有:k log2n 1,性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第log2n+1
8、层,每层从左到右),则对任一结点i(1in),有:,(1)如果i=1,则结点i无双亲,是二叉树的根;如果i1,则其双亲是结点i/2。,(2)如果2in,则结点i为叶子结点,无左孩子;否则,其左孩子是结点2i。,(3)如果2i1n,则结点i无右孩子;否则,其右孩子是结点2i1。,图6.6 完全二叉树中结点i和i+1,只要先证明(2)和(3),便可以从(2)和(3)推出(1)。,对于i1,由完全二叉树的定义,其左孩子是结点2,若2n,即不存在结点2,此时,结点i无孩子。结点i的右孩子也只能是结点3,若结点3不存在,即3n,此时结点i无右孩子。,图6.6 完全二叉树中结点i和i+1,i+1,2(i+
9、1),2i+3,i,2i,2i+1,(b)i和i+1结点不在同一层,对于i1,可分为两种情况:,(1)设第j(1jlog2n)层的第一个结点的编号为i(由二叉树的定义和性质2可知i2j-1),则其左孩子必定为j1层的第一个结点,其编号为2j22j-12i。如果2in,则无左孩子;,其右孩子必定为第j1层的第二个结点,编号为2i1。若2i+1n,则无右孩子。,图6.6 完全二叉树中结点i和i+1,i+1,2(i+1),2i+3,i,2i,2i+1,(b)i和i+1结点不在同一层,(2)假设第j(1jlog2n)层上的某个结点编号为i(2 j-1i2j-1),且2i1n,则其左孩子为2i,右孩子为
10、2i1.又编号为i1的结点是编号为i的结点的右兄弟或堂兄弟。若它有左孩子,则其编号必定为2i22(i1);若它有右孩子,则其编号必定为2i32(i1)1。,图6.6 完全二叉树中结点i和i+1,当i1时,就是根,因此无双亲。,当i1时,如果i为左孩子,即2(i/2)=i,则i/2是i的双亲;如果i为右孩子,i2p+1,i的双亲应为p,p(i1)/2=i/2。证毕。,1、顺序存储结构,6.2.3 二叉树的存储结构,#define MAX_TREE_SIZE 100 typedef TElemType SqBiTree MAX_TREE_SIZE;SqBitree bt;,按照顺序存储结构的定义,
11、在此约定,用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为i的的结点元素存储在如上定义的一维数组中下标为i-1的分量中。,1 2 3 4 5 6 7 8 9 10 11 12,a,b,c,d,e,f,g,h,i,j,k,l,1、顺序存储结构,完全二叉树,从树根起,自上层至下层、每层自左至右的给所有结点编号。,一般二叉树,缺点是有可能对存储空间造成极大的浪费,在最坏的情况下,一个深度为h且只有h个结点的右单支树,却需要2h-1个结点存储空间;而且,若经常需要插入与删除树中结点时,顺序存储方式不是很好!,typedef struct BiTNode
12、TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,在n个结点的二叉链表中,有n+1个空指针域,二叉树的每一个结点最多有左、右两棵子树,故链表的结点结构除数据域外可设两个链域:左孩子(lchild)、右孩子(rchild)分别指向左、右孩子。称结点由两个链域组成的链表为二叉链表。,2、链式存储结构,typedef struct nodedatatype data;struct node*lchild,*rchild,*parent;JD;,三叉链表:有时为了便于找到双亲结点,另设一个指向双亲的链域,结点由三个链域组成的链表
13、称为三叉链表。,在n个结点的三叉链表中,有n+2个空指针域,用链表表示的二叉树中也会存在许多空链域。例如在含有n个结点的二叉链表中,共有2n个链域,实际用n-1链域(仅有n-1个分支),还有n+1个空链域。可以利用这些空链域存储其它有用信息,从而得到另一种链式存储结构线索链表。,6.3 遍历二叉树和线索二叉树,6.3.1 遍历二叉树 1、定义及递归算法,遍历二叉树:是指按一定的次序系统地访问二叉树中所有结点,而且每个结点仅被访问一次。,访问:所谓“访问”可以是对结点作各种处理,如输出结点的数据 域的值。,二叉树是由三个基本单元组成:根结点、左子树和右子树。因此,若能依次遍历这三部分,便是遍历了
14、整个二叉树。,假如以L、D、R分别表示遍历左子树、访问根结点和遍历右子树,则可能有:DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。,若限定先左后右,则只有前三种情况,分别称之为先(根)序遍历,中(根)序遍历和后(根)序遍历。,1、定义及递归算法,先序遍历算法,若二叉树为空树,则空操作;否则,,(1)访问根结点;,(2)先序遍历左子树;,(3)先序遍历右子树。,void PreOrder(BiTree bt)if(bt=NULL)return;/*递归调用的结束条件*/,Visit(bt-data);/*访问结点的数据域*/,PreOrder(bt-lchild);/*先
15、序递归遍历bt的左子树*/,PreOrder(bt-rchild);/*先序递归遍历bt的右子树*/,D L R,先序遍历序列:A B D C,先序遍历:,先序遍历,若二叉树为空树,则空操作;否则,,中序遍历算法,(1)中序遍历左子树;,(2)访问根结点;,(3)中序遍历右子树。,void InOrder(BiTree bt)if(bt=NULL)return;,InOrder(bt-lchild);,Visit(bt-data);,InOrder(bt-rchild);,L D R,中序遍历序列:B D A C,中序遍历,中序遍历,后序遍历算法,若二叉树为空树,则空操作;否则,,(1)后序遍
16、历左子树;,(2)后序遍历右子树;,(3)访问根结点。,void PostOrder(BiTree bt)if(bt=NULL)return;,PostOrder(bt-lchild);,PostOrder(bt-rchild);,Visit(bt-data);,L R D,后序遍历序列:D B C A,后序遍历:,后序遍历,所谓二叉树的层序遍历,是指从二叉树的第一层(根结点)开始,从上至下逐层遍历,在同一层中则按从左到右的顺序对结点逐个访问。,层序遍历,练习:,先序序列:,中序序列:,后序序列:,A B C D E F G H K,B D C A E H G K F,D C B H K G
17、F E A,层次序列:,A B E C F D G H K,例如下图所示的二叉树表示下述表达式,按中序遍历,其中序序列为:a+b*c d e/f,a+b*(c-d)-e/f,若先序遍历此二叉树,按访问结点的先后次序将结点排列 起来,其先序序列为:-+a*b c d/e f,按后序遍历,其后序序列为:a b c d-*+e f/-,人们喜欢中缀形式的算术表达式;但对于计算机,使用后缀易于求值。,(1)查询二叉树中某个结点,2、二叉树其它操作的算法,(1)查询二叉树中某个结点,在二叉树不空的前提下,和根结点的元素进行比较。若相等,则找到并返回 OK;,否则在左子树中进行查找,若找到,则返回OK;,
18、否则继续在右子树中进行查找,若找到,则返回 OK;再否则,返回 FALSE。,(2)计算二叉树中叶子结点的个数,(3)求二叉树的深度(后序遍历),(4)按先序遍历序列建立二叉树,Status Preorder(BiTree T,TElemType x,BiTree&p),if(T)if(T-data=x)p=T;return OK;else return FALSE;,else if(Preorder(T-lchild,x,p)return OK;else return(Preorder(T-rchild,x,p);,(1)查询二叉树中某个结点,算法基本思想:先序(或中序或后序)遍历二叉树,在
19、遍历过程中查找叶子结点,并计数。,(2)计算二叉树中叶子结点的个数,由此,需在遍历算法中增添一个“计数”的参数,并将算法中“访问结点”的操作改为:若是叶子,则计数器增1。,void CountLeaf(BiTree T,int,第一种方法,int CountLeaf(BiTree T)if(!T)return 0;if(!T-lchild,第二种方法,int Count(BiTree T)/返回指针T所指二叉树中所有结点个数 if(!T)return 0;if(!T-lchild,类似地求结点的个数,算法基本思想:首先分析二叉树的深度和它的左、右子树深度之间的关系,(3)求二叉树的深度(后序遍
20、历),从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加1。由此,需先分别求得左、右子树的深度,算法中“访问结点”的操作为:求得左、右子树深度的最大值,然后加 1。,int Depth(BiTree T)/*返回二叉树的深度*/if(!T)depthval=0;else,depthLeft=Depth(T-lchild);,return depthval;,depthRight=Depth(T-rchild);,depthval=1+(depthLeft depthRight?depthLeft:depthRight);,(3)求二叉树的深度(后序遍历),(4)按先序遍历序列建
21、立二叉树,建立二叉树的方法很多,这里介绍一个基于先序遍历的构造方法。算法中输入的是二叉树的先序序列,但必须在其中加入空指针。若用“”表示空指针,要建立下图中所示的二叉树,其输入序列为:,A B C D E G F,Status CreateBiTree(BiTree&T)/*按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,构造二叉链表表示的二叉树T*/,scanf(,if(ch=)T=NULL;else,if(!T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);,T-data=ch;/生成根结点 CreateBiTree(T-lch
22、ild);/构造左子树 CreateBiTree(T-rchild);/构造右子树,return OK;,3、遍历二叉树的非递归算法,(1)先序遍历的非递归算法,当找到没有左孩子的结点时,从栈顶退出某结点的右孩子,此时该结点的左子树已遍历完。,再按上述过程遍历该结点的右子树。,使用栈实现先序遍历二叉树的基本思想是:,从二叉树的根结点开始,沿左支一直走到没有左孩子的结点为止,在走的过程中访问所遇到的结点,并把非空右孩子进栈。,void preorder(JD*r)/*先序遍历二叉树的非递归算法*/int i=0;JD*p,*sM;p=r;,do while(p!=NULL),printf(%dt
23、,p-data);,si+=p-rchild;,if(i 0)p=s-i;,while(i0|p!=NULL);,if(p-rchild!=NULL),p=p-lchild;,(1)先序遍历二叉树的非递归算法,(2)中序遍历二叉树的非递归算法,使用栈实现中序遍历的二叉树的基本思想与先序遍历类同,只是在沿左支向前走的过程中将所遇到的结点进栈,待到遍历完左子树时,从栈顶退出结点并访问,然后再遍历右子树。,非递归算法,(3)后序遍历二叉树的非递归算法,使用栈实现后序遍历的二叉树要比先序和中序遍历复杂一些。每个结点要等到遍历左、右子树之后才得以访问,所以在去遍历左、右子树之前,结点都需要进栈。,因此设
24、两个栈,分别称为结点栈(S1M)和标志栈S2M)。标志栈中存放进S1栈结点的标记,标记“0”表明结点在遍历左子树时进栈,标记“1”表明结点在遍历右子树时进栈。,当它出栈时,需要判断是从遍历左子树后的返回(即遍历完左子树,需要继续遍历右子树),还是从遍历右子树后的返回(即遍历完右子树,需要访问这个结点)。,仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树,,如果同时已知二叉树的中序序列“cbdaegf”,则会如何?,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,4、由结点的先序序列和中序序列构造对应的二叉树,根据先序遍历的定义,先序序列中的第一个元素一定
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉
链接地址:https://www.31ppt.com/p-4999485.html