资源描述
单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,第,6,章 树,第六章 树,知 识 点,二叉树及二叉树的存储结构,二叉树的遍历,树的基本概念,二叉排序树,哈夫曼树,难 点,二叉树遍历算法的设计,修改二叉树遍历算法,进行二叉树其它相关的操作,解决实际应用问题,要 求,熟练掌握以下内容:,理解树形结构的基本概念和术语,二叉树定义和存储结构,二叉树的遍历次序及二叉树遍历算法,了解以下内容:,树和二叉树之间的相互转换方法,线索二叉树的建立及遍历算法,树的应用:二叉排序树和哈夫曼树,第6章 树,6.1 树的定义和基本术语,6.2 二叉树,6.3 二叉树的遍历,6.4 线索二叉树,6.5 树的应用,6.6 应用实例及分析,小结,习题与练习,6.1,树的定义,树的定义,树是n个结点的有限集合T,在一棵非空树中(n0)有且仅有一个称作,根,的结点;其余结点分为m个(m0)互不相交的集合T,1,,T,2,T,m,,其中,每一个集合本身又是一棵树,并称为根的,子树,。,当n=0时,称为,空树,。,有限集合T,1,,T,2,T,m,“互不相交”,即任意两个集合不能有相同的结点。,树的各个结点有不同层次关系,这种关系通常用图形表示,但与自然界的树木相反,习惯上将整棵树的根画在最上层,如图6.1所示。,图6.1 树的表示法,树的其它表示法,嵌套集合表示法,凹入表示法,-杜威(Deway)记数法,广义表表示法,6.,子孙,结点和,祖先,结点:一个结点的子树中所有结点均称之为该结点的子孙结点。反之,从根结点到达一个结点的路径上的所有结点,都叫做该结点的祖先结点。,7.树的深度:树是一种层次结构,树中结点的层次(Level)是从根结点算起的。根结点为第一层,其儿子结点为第二层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的,深度,或,高度,。,8.森林:n个树的集合叫森林(Forest)。,树形结构的逻辑特征,树形结构的逻辑特征可用树中结点之间的父子关系来描述:,树中任一结点都可以有零个或多个直接后继结点(即儿子结点),但至多只能有一个直接前趋结点(即父亲结点)。,树中只有根结点无前趋,它是开始结点;,叶结点无后继,它们是末端结点。,树形结构是非线性结构。,返回,树的基本操作,1.SETNULL(T),置T为空树,2.ROOT(T)或ROOT(x),求树T或求结点X所在树的根,3.PARENT(T,x),求树T中结点X的父亲,4.CHILD(T,x,i),求树T中结点X的第I个儿子,返回,5.TNULL(T),判断树T是否为空树,6.DEPTH(T),求树T的深度,7.INSERT(T,x),结点的插入,8.DELETE(T,x),结点的删除,9.VISIT(T),树的遍历,6.2,二叉树的定义及其性质,二叉树,的定义,一棵二叉树是n个结点的有限集合(n0),此集合或者是空集(n=0),或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。,由上述定义可知,二叉树可以是空集,其根可以有左子树或右子树,也可以没有左子树或右紫树.,二叉树的子树有左,右之分,左右不能颠倒.,一般地,二叉树有五种基本形态,如图6.2所示。,图6.2 二叉树的基本形态,(a)空二叉树,(b)仅有一个根结点的二叉树,(c)右子树为空的二叉树,(d)左子树为空的二叉树,(e)左、右子树均非空的二叉树,二叉树的基本术语.,二叉树的基本操作,二叉树的性质,性质1.在二叉树第 k 层上至多有2,k-1,个结,点。,性质2.深度为 k 的二叉树至多有2,k,-1个结,点。(k=1),.,性质3.对任一二叉树BT,若其末端结点数为,n,0,,度为2的结点数为,n,2,,则,n,0,=,n,2,+1,证:设二叉树有n个结点,度为1的结点数为,n,1,则,n,=,n,0,+,n,1,+,n,2;,另一方面,度为1的结点有1个儿子,度为2的结点有2个儿子,故二叉树中儿子总数(除根结点外)为,n,1,+2*,n,2,所以二叉树的结点总数又可表示成,n,=,n,1,+2*,n,2,+1,所以,n,0,=,n,2,+1,满二叉树,在一个二叉树中,若第 I 层的结点数为2,i-1,,则称该层的结点数是满的,当树中的每一层都是满的,则称此二叉树为,满二叉树。,例,如果一个二叉树中,除最下一层的各结点度数为0以外,其它各层结点的度数均等于2,则此二叉树为满二叉树。,满二叉树的第一层有一个结点(即根结点),第二层有两个结点,依此类推。每一层的结点数都是上一层结点数的二倍。所以,在满二叉树的第i层共有2,i-1,个结点(i1),一个深度为k的满二叉树的结点总数为,2,k,1.,图6.3 满二叉树,完全二叉树,如果一个二叉树各层都是“满”的,只是最下面一层从右边起连续缺若干个结点,这种二叉树叫做,完全二叉树,。,性质4,.一棵具有n个结点的完全二叉树的深度为,log,2,n,+1,证:由定义知:2,k-1,-1n 2,k,-1,即 2,k-1,n,2,k,取对数 k-1logn k,由 k-1logn 可知:klogn+1,即k,log,2,n,+1,有 logn 1,则其父结点编号为,i/2,。,2)如果2in,则其左儿子结点编号为2i;若2in,则无左儿子结点。,3)如果(2i+1)n,则其右儿子结点编号为(2i+1);反之,则无右儿子结点。,例:,二叉树的存储结构,1.二叉树的,顺序存储结构:,对于满二叉树和完全二叉树来说,可以采用“以编号为地址”的方法,将编号为i的结点存入一维数组的第i个单元。,图6.3所示的完全二叉树按此方法存入数组中如下图6.4所示。,图,6.4 二叉树的顺序存储结构,这种存储结构适用于完全二叉树和满二叉树。,如果某二叉树不是完全二叉树,中间有一些结点不存在,则采用顺序存储结构时,数组中必然要有一些空闲单元,浪费存储空间.,图6.5 非完全二叉树的顺序表示,图6.5中的二叉树,采用顺序存储结构时,一维数组的21单元中只用上了7个。,2.二叉树的,链式存储结构,:,由二叉树的定义可知:其结点由信息部分和指向其左右儿子的指针组成,因此可把二叉树的结点定义成:信息域,左指针域,右指针域。,也可以增加一个指向父亲的指针,如下:,图6。5可表示成:,Lchild,data,Rchild,Lchild,data,Parent,Rchild,结点定义,链式存储结构的结点定义如下:,typedef struct BTnode,elementtype data;,struct BTnode*Lchild;,struct BTnode*Rchild;,BTree;,这里的elemeenttype可以是任何相应的数据类型如int、float或char等。,6.3,二叉树的遍历,二叉树的遍历(Traversal)是指按一定的顺序访问二叉树的每个结点,且每个结点只被访问一次的过程。,对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。,对于用顺序法表示的二叉树,各结点在数组中的编号很有规律,其遍历较容易进行,但对于用链式存储结构表示的二叉树,进行遍历就复杂一些,故本节仅讨论链式存储形式的二叉树遍历过程。,一个非空的二叉树由根结点及左、右子树这三个基本部分组成,因此若能依次遍历这三部分,便是遍历了整个二叉树。,在任一给定结点上,可以按某种次序执行三个操作:访问结点本身,遍历该结点左子树,遍历该结点右子树,操作排列次序:,左、根、右;根、左、右;左、右、根;,右、根、左;根、右、左;右、左、根;,由于实际问题一般都是要求左子树较右子树先遍历,故只采用其中、三种遍历次序,分别称为中序遍历、先序遍历和后序遍历。,三种遍历次序以递归的形式定义:,(1)中序(Inorder)遍历,若遍历的二叉树为空,执行空操作;否则依次执行下列操作:,中序遍历左子树;,访问根结点;,中序遍历右子树。,(2)先序(Preorder)遍历,若遍历的二叉树为空,执行空操作;否则依次执行下列操作:,访问根结点;,先序遍历左子树;,先序遍历右子树。,(3)后序(Postorder)遍历,若遍历的二叉树为空,执行空操作;否则依次执行下列操作:,后序遍历左子树;,后序遍历右子树;,访问根结点。,图6.9 二叉树遍历,中序遍历序列:H,D,I,B,E,A,F,C,G。,先序遍历序列:A,B,D,H,I,E,C,F,G。,后序遍历序列:H,I,D,E,B,F,G,C,A。,先序遍历递归算法,void preorder(btree*BT),if(BT!=NULL),printf(%d,BT-data);,preorder(BT-lchild);,preorder(BT-Rchild);,先序遍历,非,递归算法,基本思想,:,先访问根结点,并进栈,再访问左儿子,并进栈,直到左儿子为空;,退栈,并访问其右儿子,;,重复以上过程,栈空为止。,先序遍历,非,递归算法,#define maxsize,void Nr-preorder(btree*BT),btree*Smaxsize,*p;/*定义栈S,中间变量P*/,int top=0;p=bt;,while(p!=null)|(top!=0),while(p!=null),stop=p;/*若P非空,则进栈*/,top+;,printf(“%d”,p-data);/*输出,p=p-lchild;/*取其左儿子*/,先序遍历,非,递归算法(续),if(top!=0),top-;,p=stop;/*退栈至P中*/,p=p-rchild;/*取其右儿子*/,中序遍历递归算法,void inorder(btree*BT),if(BT!=NULL),inorder(BT-lchild);,printf(%d,BT-data);,inorder(BT-Rchild);,中序遍历,非,递归算法,void Nr-inorder(btree*BT),btree*Smaxsize,*p;/*定义栈S,中间变量P*/,int top=0;p=bt;,while(p!=null)|(top!=0),while(p!=null),stop=p;/*若P非空,则进栈*/,top+;,p=p-lchild;/*取其左儿子*/,中序遍历,非,递归算法(续),if(top!=0),top-;,p=stop;/*退栈至P中*/,printf(“%d,p-data);,p=p-rchild;/*取其右儿子*/,后序遍历,方法1:,按照 先根、右子树、左子树的顺序遍历二叉树,得到的结果与后序遍历的结果相反。,根据这一事实,可以对二叉树按以上顺序遍历,之后颠倒过来即可。,方法2:,先序遍历、中需遍历时,每个结点只有1次进栈和1次出栈。,后序遍历时,每个结点要2次进栈,也就是说,每个结点要进2次,出2次。,所以,要设一个标志flag,以记住是第1次进栈还是第2次进栈。该标志与指针同时进出栈。,取左儿子时,flag=0,取右儿子时,flag=1,在第二次出栈时访问该结点。,例:求二叉树深度的,递归算法,int BTreeheight(Btree*BT),int hight1;hight2;,if(BT=null)return(0);,else hight1=BTreeheight(btree-lchild);,hight2=BTreeheight(btree-rchild);,if(hight1hight2)return(hight1+1);,else return(hight2+1);,求二叉树深度的,非递归,算法,Int depth(btree*BT),btree*S,*p;/*定义栈S,中间变量P*/,p=bt;/*L记录S中元素对应的层号,int L;top=0;max=0;level=0;,while(p!=null)|(top!=0),while(p!=null),level+;,stop=p;Ltop=level;/*进栈,top+;,p=p-lchild;/*取其左儿子*/,If(levelmax)max=level;,if(top!=0),top-;,p=stop;level=Ltop;/*退栈,p=p-rchild;/*取其右儿子*/,return(max);,求二叉树叶子结点的个数。,二叉链表存储的二叉树的层次遍历算法。,求二叉树中,每层结点的个数。,用一维数组存放一棵完全二叉树,写出先序遍历算法。,6.4,线索二叉树,从上节可知:遍历二叉树就是按一定规则将二叉树中的结点排列成一个线性序列,把一个非线性结构线性化。,以二叉链表作为存储结构时,只能找到其左右儿子,而不能直接找到它的前趋或后继;,另一方面,对有n个结点的二叉链表,有n+1个指针域是空的,能否利用这些空指针域来存储结点的前趋或后继呢?,艾.J.珀利斯(A.J.Perlis)和查.桑顿(C.Thorton)提出了巧妙地利用这些空链的方法。,6.4,线索二叉树(续),(以中序遍历为例),若结点的左指针为空,则存放其前驱结点;若结点的右指针为空,则存放其后继结点。用这种方法构造的二叉树叫,线索二叉树。,把一个二叉树变成一个线索二叉树的过程叫作二叉树的线索化。,以,中序遍历,为例介绍二叉树的线索化,基本思想:,若结点有左儿子,则其lchild指向其左儿子;否则,令lchild指向其前趋结点;,若结点有右儿子,则其rchild指向其右儿子;否则,令rchild指向其后继结点;,在每个结点中增加两个标志,即左线索标志ltag,右线索标志rtag,以区别是线索和儿子。,增加线索标志后的结点结构为:,其中,ltag=0,Lchild指向其左儿子,ltag=1,Lchild指向其前趋,rtag=0,rchild指向其右儿子,rtag=1,rchild指向其后继,注意,指针,和,线索,的区别,lchild,ltag,data,rtag,rchild,结点类型和相应结点的指针类型定义如下:,typedef struct bithrnode,int ltag;,int rtag;,elementtype data;,struct bithrnode*lchild;,struct bithrnode*rchild;,bithrtree;,图6.11 中序线索树,与图6.9所示二叉树对应的中序线索树如左图所示。图中的虚线箭头即为新加上的线索。,线索二叉树的构造,基本思想:,已知一棵二叉树,使其线索化。本质是:将二叉链表中的空指针改为前趋或后继,而前趋或后继只有在遍历过程中才能得到,因此线索化的过程就是在遍历的过程中修改空指针的过程。,为了记下遍历过程中访问结点的先后次序,附设两个指针:pre指向,刚访问过,的结点,p指向,正在访问的,结点。,(以中序遍历),在遍历算法的输出语句处加入下列语句即可。,if(p-lchild=,null),p,-lchild=pre;p-ltag=1,if(,pre,-rchild=,null),pre-rchild=p;pre-rtag=1,以中序为例,构造,线索二叉树算法,void Nr-inorder(bithrtree*BT),bithrtree*Smaxsize,*p,*pre,;/*定义栈S,中间变量P*/,int top=0;p=bt;pre=null;,while(p!=null)|(top!=0)),while(p!=null),stop=p;/*若P非空,则进栈*/,top+;,p=p-lchild;/*取其左儿子*/,if(top!=0),top-;,p=stop;/*退栈至P中*/,if(p-lchild=,null),p-lchild=pre;p-ltag=1,if(pre-rchild=,null),pre-rchild=p;pre-rtag=1,pre=p;,p=p-rchild;/*取其右儿子*/,中序线索树求,后继,结点,在中序遍历线索树过程中,按下述两条原则即可找到后继结点:,1)如果结点的 rtag=1,说明其右指针域是线索,这个线索所指的即是该结点的后继结点;,2)如果结点的 rtag=0,则其右指针指向的是右儿子,其后继是其右子树最左下方的结点.,中序线索二叉树求,后继,算法,tbtree*next(bithrtree*p),bithrtree*q;,if(p-rtag=1),return(p-rchild);,/*由后继线索得到*/,else,q=p-rchild;,while(q-ltag=0),q=q-lchild;,return(q);,在,中序线索树中求,前趋,结点,找前趋结点相应的原则如下:,1)如果某结点的 Ltag=1,说明其左指针域是线索,这个线索所指的即是该结点的前趋结点;,2)如果某结点的 Ltag=0,则其左指针指向左儿子,它的前趋是该结点的左子树最右下方的结点.,在中序线索二叉树中求前驱结点的算法,tbtree*pre(bithrtree*p),bithrtree*q;,if(p-Ltag=1),return(p-Lchild);,else,q=p-Lchild;,while(q-Rtag=0),q=q-Rchild;,return(q);,中序遍历线索树,从根结点起一直向左下方查找,找到左线索标志为1的结点(“最左下方”的结点),即为遍历的第一个结点。,由此结点开始,反复进行寻找后继结点的过程,并访问这些结点,直至结束。,中序遍历子线索二叉树非递归算法,void thinorder(bithrtree*p),if(p!=NULL),/*树非空*/,while(p-ltag=0),p=p-lchild;,/*找最左下方的结点*/,do,print(“%c”,p-date);,/*访问结点*/,p=next(p);,while(p!=NULL);,返回,在中序线索二叉树中插入结点,插入结点T,使其成为 S 的右儿子.,插入过程:,1.若S的右子树为空,则T为S的右儿子,,S的后继为T的后继,S成为T的前趋;,2.若S的右子树为非空,则当T插入后,S,的右子树成为T的右子树,S为T的前,趋,S原来的后继中的lchild指针改为T。,在中序线索二叉树中插入结点的算法,Bithrtree insert(bithrtree*thrt,*s,*t),bithrtree*p;,T-rtag=s-rtag;/*S的后继,T-rchild=s-rchild;/*成为T的后继,T-ltag=1;/*S成为T的前趋*/,T-lchild=s;,S-rtag=0;,/*T成为S的右子树*/,S-rchild=t;,在中序线索二叉树中插入结点的算法(续),P=t-rchild;,If(t-rtag=0),/*若T有右儿子,则找它右子树的,while(p-ltag=0),/*最左下方的结点,p=p-lchild;,p-lchild=t;,/*最左下方的结点的lchild,return(thrt);,/*指向其前趋T,插入结点T,使其成为 S 的左儿子,6.4 树 森林与二叉树的转换,普通树可用链式存储结构来表示,每个结点包括数据域以及指向它各个儿子结点的指针域。,由于同一树的各结点度数一般并不相同,如按结点的度数给每个结点设置不同数目的指针域,不同结点的数据结构不同,会给算法设计和程序编制造成困难。,如欲令同一树的各结点有相同数据结构,则只能按结点度数最大值(该树的度数)给每个结点设置指针。这样较浪费存储空间。,按照一定的原则将普通树用二叉树来表示,是较好的表示方法。,6.4 树 森林与二叉树的转换,1.树的存储结构,双亲表示法:,每个结点除了信息字段外,另设一个指向其父亲的字段。,Typedef struct node,elementtype data;,struct node*parent;,ptreeType;,孩子表示法:,每个结点除了信息字段外,还设若干个指针,每个指针指向一个儿子。,Typedef struct node,elementtype data;,struct node*sptrdegree;,CtreeType;,其中degree为树的度。,孩子兄弟表示法(二叉树法):,每个结点除了信息字段外,还有两个指针,分别指向第1个儿子和下一个兄弟。,Typedef struct node,elementtype data;,struct node*son;,struct node*next;,cbtreeType;,2.树转换成二叉树,具体方法如下:,1)在所有兄弟结点之间加一连线;,2)对每个结点,除了保留与其左儿子结点的连线外,去掉该结点与其它儿子结点的连线。,图6.8 树转化为二叉树,图6.8 树转化为二叉树,得到的已是一棵二叉树,若按顺时针方向将它旋转就更清楚地变为下面所示的二叉树。,由于树根没有兄弟,所以树转换为二叉树后,二叉树的根结点的右子树必为空。,森林转换成二叉树,森林:树的集合,转换方法:,1.先把森林中的每棵树转换成二树,F=T,1,T,2,T,m,2.若m=0,则森林F为空,那么对应的二叉,树为空树.,3.若m,0,则F对应的二叉树的根为T1的根,左子树为T1去掉根后剩余部分,右子树为,F=,T,2,T,m,转换而成的二叉树.,例:,二叉树转换成森林,例,树的遍历,先根遍历,:先访问根,然后依次先根遍历树的每一棵子树.,后根遍历,:先依次后根遍历树的每一棵子树,然后访问根.,例:,森林的遍历,先序遍历,:,访问森林的第一棵树的根结点,先序遍历第一棵树中根结点的子树,先序遍历去掉第一棵树之后的剩余部分,.,例,后序遍历,6.5,哈夫曼树及其应用,1.哈夫曼树基本术语:,路径,:从树中一个结点到另一个结点之,间的边构成的通路。,路径长度,:路径上边的数目。,树的路径长度,:从根到每一结点的路径,长度之和,一般记作pl。,pl=0+1+1+2+2+2+2=10,pl=0+1+1+2+2+2+3=11,结点的权,:在许多实际应用中,常常将树中结点赋予一个有某种意义的实数,称为该结点的权。,结点的带权路径长度,:从树的根结点到该结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度。,树的带权路径长度:,树中所有叶子结点的带权路径长度之和,通常记为:,其中n表示叶子结点个数,w,i,和l,i,分别表示叶子结点k,i,的权值和根到k,i,之间的路径长度。,给定n个实数,以它们作为n个叶子结点的权,可构成多个不同的有n个叶子结点的二叉树,这些二叉树的带权路径长度wpl可能不同。wpl最小的二叉树称为该二叉树的,哈夫曼树。,图6,.15,不同,wpl,的二叉树,给定四个数7,5,2,4,作为叶子结点的权,可构造多棵不同的二叉树。,wpl=36,图6,.15,不同,wpl,的二叉树,wpl=46,wpl=35,2.哈夫曼树的构造算法,将n个权值w,1,,w,2,,w,n,按递增次序排列,设其顺序为w,1,,w,2,,w,n,,取出最小的两个w,1,和w,2,,分别作为根结点的左、右儿子结点的权组成一个二叉树,并认为其根结点的权w,12,=w,1,+w,2,;,将w,12,按其数值大小插入到w,3,至w,n,之间,使数值仍保持为递增的次序;,再取出最小的两个作为根的左、右儿子的权组成二叉树,也令根的权等于此两数值之和,并同样将此根结点按权值大小插入到剩下的数据中,保持数值的递增次序。如此重复进行下去,直到构成一个二叉树为止,即得到哈夫曼树。,图6.16 哈夫曼算法过程,给定4个数:7,5,2,4。,3.哈夫曼编码,哈夫曼编码(Haffman coding)是一种应用广泛且非常有效的数据压缩技术,该技术一般可将数据压缩20%至90%,其压缩效率取决于被压缩数据的特征。,设有一段电文“CAST_TAT_A_AS”,统计电文中字母的频度f(C)=1,f(S)=2,f=(T)=3,f=(_)=3,f=(A)=4。用频度1,2,3,3,4为权生成哈夫曼树,并在每个叶结点上注明对应的字符。,图6.17 Huffman编码树,C S T _ A,000 001 01 10 11,从根结点起每输入一个数码即沿二叉树下移一层,数码为0时移向左分支,数码为1时移向右分支,待达到叶子结点时即译出一个字符,再输入的数码又从根结点开始重新做起。,将此二叉树与相应的编码方式对照可以发现,每个叶子结点至根的路径长度即等于该叶子结点所代表字符的编码位数。由于将每种字符出现的次数作为对应叶子结点的权,则计算出的带权路径长度wpl即为整个字符串的编码长度。,返回,可以看出:任一个字符的编码都不是另一个字符编码的前缀,这样的编码称作,前缀编码,。,下面讨论求哈夫曼编码的算法。,由于哈夫曼树中没有度为1的结点,所以若有n个叶子结点,则共有2n-1个结点(证明略)。,我们用大小为2n-1的向量作为哈夫曼树的存储结构,由于在构成哈夫曼树之后,为求编码需走一条从叶子结点到根结点的路径,而译码需走一条从根到叶子结点的路径,所一对每一结点而言,既要知道其父亲的信息,又要知道其儿子的信息,,因此结点定义如下:,#define n,#define m /*m=2n-1*/,Typedef struct nodetype,int weight,parent,lch,rch;,HuffmanTree;,Typedef struct codetype,char bitsn;,int start;,Hcode;,求哈夫曼树 哈夫曼编码算法,Void Huffman-code(int w,HuffmanTree ht,Hcode hcd),/*w存放n个字符的权,ht表示huffman树,,/*hcd存放n个字符的huffman编码,for(i=0;im;i+)/*初始化*/,hti.parent=-1;,hti.lch=-1;,hti.rch=-1;,for(i=0;in;i+)/*初始化*/,hti.weight=wi;,求哈夫曼树 哈夫曼编码算法(续),for(i=n;im;i+)/*构造哈夫曼树*/,select(i-1,s1,s2);/*在htk(0=k=i-1)中,选择两,hts1.parent=i;/*个其双亲域为空,且权值最小的,hts2.parent=i;/*结点,它们在ht中的序号为,hti.lch=s1;/*S1,S2。,hti.rch=s2;,hti.weight=hts1.weight+hts2.weight;,求哈夫曼树 哈夫曼编码算法(续),for(i=0;ileft;,例6.4算法续,if(top0),p=stacktop;/*p所指结点为无左子树的结点或其左子树已遍历过*/,top-;,printf(“%d”,p-data);,/*访问结点*/,p=p-right;/*扫描右子树*/,while(top!=0);,返回,小 结,树,二叉树,满二叉树,完全二叉树,树的存储结构,顺序存储结构,链接存储结构,二叉树的遍历,中序遍历,先序遍历,后序遍历,线索二叉树,树的应用,二叉排序树,哈夫曼树,返回,习题与练习,一、基础知识题,1.就如图5.21所示的树回答下面问题:,1)哪个是根结点?,2)哪些是叶子结点?,3)哪个是E的父结点?,4)哪些是E的子孙结点?,5)哪些是E的兄弟结点?哪些是C的兄弟结点?,6)结点B和结点I的层数分别是多少?,7)树的深度是多少?,8)以结点G为根的子树的深度是多少?,9)树的度是多少?,图6.21 树的例子,2.分别画出含3个结点的树与二叉树的所有不同形态。,3.高度为h的完全二叉树至少有多少个结点?最多有多少个结点?,4.采用顺序存储方法和链式存储方法分别画出图5.22所示二叉树的存储结构。,5.分别写出图5.22所示二叉树的前序、中序和后序遍历序列。,图6.22 二叉树例子,6.若二叉树中各结点值均不相同。,1)已知一个二叉树的中序和后序遍历序列分别为GDHBAECIF和GHDBEIFCA,请画出此二叉树。,2)已知一个二叉树的前序和中序分别为ABCDEFGH和BDCEAFHG,请画出此二叉树。,7.一个二叉树如图5.23所示,分别写出其前序、中序、后序的遍历序列。,8.输入一个正整数序列55,34,18,88,119,11,76,9,97,99,46,试构造一个二叉排序树。,9.有一份电文中共使用5个字符:a、b、c、d、e,它们的出现频率依次为5、2、1、6、4。试画出对应的哈夫曼树,并求出每个字符的哈夫曼编码。,图6.23 一个二叉树,二、算法设计题,1.一个二叉树以链式结构存储,分别给出求二叉树结点总数和叶子结点总数的算法。,2.一个二叉树以链式结构存储,写出在二叉树中查找值为x的结点的算法。,3.设计一个算法将一个以链式存储结构的二叉树,按顺序方式存储到一维数组中。,4.假设二叉排序树t的各元素值均不相同,设计一个算法按递增次序打印各元素值。,5.已知一个中序线索二叉树,试编写中序遍历的非递归算法。,返回,
展开阅读全文