《数据结构课件、代码》第4章树和二叉树

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第4章 树和二叉树,张成文,北京邮电大学计算机学院,树的定义与基本术语,1.定义:,树,是n(n0)个结点的有限集合T。当n=0时,称为空树;当n0时,该集合满足如下条件:,(1)其中必有一个称为根(root)的特定结点,它没有直接前驱,但有零个或多个直接后继。,(2)其余n-1个结点可以划分成m(m0)个互不相交的有限集T,1,T,2,T,3,T,m,其中T,i,又是一棵树,称为根root的子树。每棵子树的根结点有且仅有一个直接前驱,但有零个或多个直接后继。,一、树,(tree),的基本概念:,A,B,C,D,E,F,G,H,I,J,M,K,L,A(,B(E,F(K,L),C(G),D(H,I,J(M),),T,1,T,3,T,2,树根,例如:,(1).树型图示 (2).嵌套集合 (3).凹入(书目),(4).广义表(用根作为表的名字写在表的左边),A,B,C,D,E,F,G,H,I,J,K,L,M,A,-,B,-,E,-,K,-,L,-,F,-,C,-,G,-,D,-,H,-,M,-,I,-,J,-,2.树的表示法:,线性结构,树型结构,第一个数据元素,(无前驱),根结点,(无前驱),最后,一个,数据元素,(无后继),多个,叶子结点,(无后继,),其它数据元素,(一个前驱、,一个,后继),其它数据元素,(一个前驱、,多个,后继),对比,树型结构,和,线性结构,的结构特点,结点,(node):,树的度:,叶子结点(leaf):,分支结点:,数据元素,+,若干指向子树的分支,树各结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,3.树的相关术语,结点的度(degree):,结点拥有的子树数,结点的层次:,(level),假设根结点的层次为,1,第,l,层的结点的子树根结点的层次为,l+1,树的深度(depth):,叶子结点所在的最大层次,分支,(branch),:,表示数据元素与它的子树的关系,路径(path):,常用家族树的术语表示结点关系,孩子(child),结点,双亲(parent),结点,兄弟,结点,由根到该结点所经的分支和结点构成,A,B,C,D,E,F,G,H,I,J,M,K,L,树的结点数,n,和分支数,b,的关系是:,b=n-1,任何一棵非空树是一个二元组,Tree=(root,F),其中:root 被称为根结点,F 被称为子树森林,森林,(forest):,是m(m0)棵互不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,二叉树,1 二叉树的定义与基本操作,定义,：,满足以下两个条件的树称做二叉树(Binary Tree):,（1）每个结点的度都不大于2；,（2）每个结点的孩子结点次序不能任意颠倒。,二叉树或为,空树,或是由一个,根结点,加上,两棵,分别称为,左子树,和,右子树,的、,互不交的,二叉树,组成。,注意:,二叉树是,有序树,它的子树有左右之分。,二叉树的度数不超过二,但度数不超过二的树未必是二叉树。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二叉树的五种基本形态:,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均非空树,用归纳法证明,:,归纳基,:,归纳假设:,归纳证明:,i,=,1,层时,只有一个根结点:,2,i-1,=,2,0,=,1,命题成立;,假设,i-1,命题成立,即:,第,i-1,层至多有结点=,2,i-1-1,=,2,i-2,个;,二叉树每个结点至多有两棵子树,则,第,i,层至多有结点=,2,i-2,2,=,2,i-1,个。,2,二叉树的重要特性,性质1:二叉树第,i,层上至多有,2,i-1,个结点。,证明:,基于性质1,深度为,k,的二叉树上的结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为,k,的二叉树上含 结点数至多为：,2,0,+2,1,+,+2,k-1,=2,k,-1,性质 2:,深度为,k,的二叉树上至多含,2,k,-1,个结点(k,1),。,证明:,设 二叉树上结点总数：,n=n,0,+n,1,+n,2,再根据树的性质：,b=n-1,=n,0,+n,1,+n,2,-1,由有二叉树分支总数：,b=n,1,+2n,2,两式右边相等得:,n,0,=n,2,+1,。,性质 3:,对任何一棵二叉树,若它含有,n,0,个叶子结点、,n,2,个度为,2,的结点,则必存在关系式:,n,0,=n,2,+1,。,也可以用归纳法证明,满二叉树,在一个二叉树中，若第i层的结点数为2,i-1,，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。,即如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。,完全二叉树,如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。,完全二叉树,:,树中所含的,n,个结点和满二叉树中,编号为,1,至,n,的结点,一一对应。,a,b,c,d,e,f,g,h,i,j,可用一维数组存储:btn,顺序:完全二叉树中将编号i的结点存在bti中。,一、二叉树的顺序存储,3,二叉树的存储结构,二叉树是非线性结构，结点最多有两个后继。,存储结构有两种：,顺序存储,结构和,链式存储,结构。,A,B,C,D,E,F,G,H,I,J,K,L,A,B,C,D,E,F,G,H,I,J,K,L,例如:,A B D C E F,1,2 3,4 5 6,7 8 9,10 11,12 13 14,A,B,C,D,E,F,2,5,1,14,3,7,一般二叉树，,按完全二叉树结点的编号存放,无结点的单元存放空元素。,会造成空间浪费,二、二叉树的链式存储表示,二叉链表,每个结点包括两个指针域：指向左孩子和右孩子,LChild,Data,RChild,D,A,B,C,E,F,G,A,B,C,D,E,F,G,二叉树T,二叉链表,结点结构:,l,child data,r,child,结点结构:,二叉链表结点的结构用C语言描述为：,typedef struct Node,DataType data;,strct Node*LChild;,struct Node*RChild;,BiTNode,*BiTree,;,一、问题的提出,二、先左后右的遍历算法,三、算法描述,二叉树的遍历,“遍历”:,沿某条搜索路径,巡访,二叉树的结点,使每个结点,均被访问一次,且,仅被访问一次,。,一、问题的提出,“访问”:,的含义很广,如:输出结点信息等。,“,遍历,”,是任何类型均有的操作,对线性结构而言,只有一条搜索路径(因为每个结点只有一个后继),故不需要另加讨论.,二叉树是非线性结构,每个结点有两个后继,则存在按什么样的,搜索路径,遍历的问题。,“二叉树”由三部分组成：,根结点、左子树和右子树,。若能依次遍历这三部分，就遍历了整个二叉树。用,L、,D,、R,表示,遍历左子树,、,访问根结点,、,遍历右子树,，则有8种遍历二叉树方案：,先左后右：,D,LR、L,D,R、LR,D、按层次,先右后左：,D,RL、R,D,L、RL,D、按层次,二、,先左后右,的遍历算法,先,序的遍历算法,D,LR,中,序的遍历算法,L,D,R,后,序的遍历算法,LR,D,D,L,R,若二叉树为空树,则空操作;否则,(1)访问根结点;,(2)先序遍历左子树;,(3)先序遍历右子树。,先序的遍历算法:,D,L,R,若二叉树为空树,则空操作;否则,(1)中序遍历左子树;,(2)访问根结点;,(3)中序遍历右子树。,中序的遍历算法:,D,L,R,若二叉树为空树,则空操作;否则,(1)后序遍历左子树;,(2)后序遍历右子树;,(3)访问根结点。,后序的遍历算法:,D,L,R,a,b,c,d,e,f,g,h,i,j,例如:,先序序列:,a b d h i e j c f g,中序序列:,h d i b j e a f c g,后序序列:,h i d j e b f g c a,三、算法描述,1)先序遍历,void,PreOrder,(BiTree bt),/*先序遍历,根指针为bt的二叉树*/,if(bt!=NULL),Visit(bt-data);,/访问根结点,PreOrder,(bt-LChild);,/遍历左子树,PreOrder,(bt-RChild);,/遍历右子树,2)中序遍历,void,InOrder,(BiTree bt),/*中序遍历根指针为bt的二叉树*/,if(bt!=NULL),InOrder,(bt-LChild);,/遍历左子树,Visit(bt-data);,/访问根结点,InOrder,(bt-RChild);,/遍历右子树,3)后序遍历,void,PostOrder,(BiTree bt),/*后序遍历根指针为bt的二叉树*/,if(bt!=NULL),PostOrder,(bt-LChild);,/遍历左子树,PostOrder,(bt-RChild);,/遍历右子树,Visit(bt-data);,/访问根结点,利用遍历结果确定二叉树问题,先序序列+中序序列,中序序列+后序序列,先序序列+后序序列(x),先序序列:,A,BCDE,FGH,中序序列:,BDCE,A,FHG,A,B,F,C,G,D,E,H,利用遍历结果确定二叉树问题,仅知二叉树的先序序列,abcdefg,不能唯一确定一棵二叉树,如果,同时,已知二叉树的中序序列,cbdaegf,则会如何？,由先序和中序序列确定,二叉,树,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列,中序序列,