数据结构-第6章-树.ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
- 资源描述:
-
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章,树和二叉树,6.1,树的定义和基本概念,6.2,二叉树,6.3,遍历二叉树和线索二叉树,6.4,树和森林,6.6,哈夫曼树及其应用,第六章 树和二叉树,6.1,树的类型定义,第六章 树,6.1,树的定义,定义,定义:树,(tree),是,n(n,=0,),个结点的,有限集,T,,,其中:,n=0,则称为,空树,。,当,n0,时,,有且仅有一个特定的结点,称为树的,根,(root),当,n1,时,,其余结点可分为,m(m,0),个互不相交的,有限集,T1,T2,Tm,,,其中每一个集合本身又是一棵,树,,称为根的,子树,(,subtree,),A,只有根结点的树,A,B,C,D,E,F,G,H,I,J,K,L,M,有子树的树,根,子树,数据对象,D,:,D,是具有相同特性的数据元素的集合。,若,D,为空集,则称为,空树,。否则,:,(1),在,D,中存在唯一的称为,根,的数据元素,root,;,(2),当,n1,时,其余结点可分为,m(m0),个互,不相交的有限集,T,1,T,2,T,m,,,其中每一,棵子集本身又是一棵符合本定义的树,,称为根,root,的,子树,。,数据关系,R,:,ADT Tree,基本操作:,查找类,;,插入类,;,删除类,;,ADT Tree,基本术语,结点,(node),表示树中的,元素,,包括,数据,元素及若干指向其子树的,分支,结点的度,(degree),结点拥有的,子树数,叶子,(leaf),度为,0,的结点,孩子,(child),结点子树的根称为该结点的,孩子,双亲,(parents),孩子结点的,上层结点,叫该结点的,兄弟,(sibling),同一双亲,的孩子,树的度,一棵树中,最大,的结点度数,结点的层次,(level),从根结点算起,,根为第一层,,它的孩子为第二层,深度,(depth),树中结点的,最大层次,数,森林,(forest)m(m,0),棵,互不相交,的树的集合,A,B,C,D,E,F,G,H,I,J,K,L,M,结点,A,的,度,:,3,结点,B,的,度,:,2,结点,M,的,度,:,0,叶子,:,K,,,L,,,F,,,G,,,M,,,I,,,J,结点,A,的,孩子,:,B,,,C,,,D,结点,B,的,孩子,:,E,,,F,结点,I,的,双亲,:,D,结点,L,的,双亲,:,E,结点,B,,,C,,,D,为,兄弟,结点,K,,,L,为,兄弟,树的度:,3,结点,A,的层次:,1,结点,M,的层次:,4,树的深度:,4,结点,F,,,G,为,堂兄弟,结点,A,是结点,F,,,G,的,祖先,结点,F,G,是结点,A,的子孙结点,任何一棵非空树是一个二元组,Tree=(root,,,F),其中:,root,被称为根结点,F,被称为子树森林,森林:,是,m(m,0),棵互,不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,赵老根,赵跃进,赵小康,赵改革,赵开放,赵解放,赵抗美,赵卫兵,赵永红,Root(T,)/,求树的根结点,查找类:,Value(T,cur_e,)/,求当前结点的元素值,Parent(T,cur_e,)/,求当前结点的双亲结点,LeftChild(T,cur_e,)/,求当前结点的最左孩子,RightSibling(T,cur_e,)/,求当前结点的右兄弟,TreeEmpty(T,)/,判定树是否为空树,TreeDepth(T,)/,求树的深度,TraverseTree,(T,Visit()/,遍历,InitTree(&T,)/,初始化置空树,插入类:,CreateTree(&T,definition),/,按定义构造树,Assign(T,cur_e,value),/,给当前结点赋值,InsertChild(&T,&p,i,c),/,将以,c,为根的树,插入为结点,p,的第,i,棵子树,ClearTree(&T,)/,将树清空,删除类:,DestroyTree(&T,)/,销毁树的结构,DeleteChild(&T,&p,i),/,删除结点,p,的第,i,棵子树,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,、广义表法,树的几种表示法,:,A,B,D,C,J,I,H,M,E,F,G,K,L,3,、树,的,嵌套集合表示法,(,),有确定的根;,(,),树根和子树根之间为有向关系。,有向树,:,有序树:,子树之间存在确定的次序关系。,无序树:,子树之间不存在确定的次序关系。,树的基本分类:,对比,树型结构,和,线性结构,的结构特点,线性结构,树型结构,(,非线性结构,),第一个数据元素,(,无前驱,),根结点,(,无前驱,),最后一个数据元素,(,无后继,),多个叶子结点,(,无后继,),其它数据元素,(,一个前驱、,一个后继,),其它数据元素,(,一个前驱、,多个后继,),6.1,树的定义和基本概念,6.2,二叉树,6.3,遍历二叉树和线索二叉树,6.4,树和森林,6.6,哈夫曼树及其应用,第六章 树和二叉树,6.2,二叉树,6.2.1,二叉树的定义,6.2.2,二叉树的性质,6.2.3,二叉树的存储结构,6.2,二叉树,6.2.1,二叉树的定义,定义:二叉树是,n(n,0),个结点的有限集,它或为,空树,(,n=0),,,或由一个根结点和两棵分别称为,左子树,和,右子树,的,互不相交的,二叉树构成,。,特点,每个结点至多有二棵子树,二叉树的子树有左、右之分,且其次序不能任意颠倒,基本形态,A,只有根结点,的二叉树,空二叉树,A,B,右子树为空,A,B,左子树为空,A,B,C,左、右子树,均非空,二叉树的主要基本操作,:,查 找 类,插 入 类,删 除 类,Root(T,);,Value(T,e);,Parent(T,e);,LeftChild(T,e);,RightChild(T,e);,LeftSibling(T,e);,RightSibling(T,e);,BiTreeEmpty(T,);,BiTreeDepth(T,);,PreOrderTraverse(T,Visit();,InOrderTraverse(T,Visit();,PostOrderTraverse(T,Visit();,LevelOrderTraverse(T,Visit();,查找类:,InitBiTree(&T,);,Assign(T,CreateBiTree(&T,definition);,InsertChild(T,p,LR,c);,插入类:,ClearBiTree(&T,);,DestroyBiTree(&T,);,DeleteChild(T,p,LR);,删除类:,6.2.2,二叉树的性质,性质,1,:在二叉树的第,i,层上至多有,2,i,-1,个节点,(i,1),证明:用归纳法证明之,i=1,时,只有一个根结点,是对的,。,假设对所有,j(1,ji),命题成立,即第,j,层上至,多有 个结点,那么,第,i-1,层至多有 个结点,又二叉树每个结点的度至多为2,第,i,层上最大结点数是第,i-1,层的2倍,即,故命题得证,6.2.2,二叉树的性质,性质,2,:深度为,k,的二叉树至多有 个结点(,k,1),证明:由性质,1,,可得深度为,k,的二叉树最大结点数是,性质,3,:对任何一棵二叉树,T,,,如果其终端结点数为,n0,,,度为2的结点数为,n2,,,则,n0=n2+1,证明:,n1,为二叉树,T,中度为1的结点数,因为:二叉树中所有结点的度均小于或等于2,所以:其结点总数,n=n0+n1+n2,又二叉树中,除根结点外,其余结点都只有一个,分支进入,设,B,为分支总数,则,n=B+1,又:分支由度为1和度为2的结点射出,,B=n1+2n2,于是,,n=B+1=,n1+2n2+1,=,n0+n1+n2,n0=n2+1,几种特殊形式的二叉树,满二叉树,定义:,特点:每一层上的结点数都是最大结点数,完全二叉树,定义:深度为,k,,,有,n,个结点的二叉树当且仅当其每一个结点都与深度为,k,的满二叉树中,编号从1至,n,的结点一一对应,时,称为,特点,叶子结点只可能在层次最大的两层上出现,对任一结点,若其右分支下子孙的最大层次为,l,,,则其左分支下子孙的最大层次必为,l,或,l,+1,1,2,3,11,4,5,8,9,12,13,6,7,10,14,15,1,2,3,11,4,5,8,9,12,6,7,10,1,2,3,4,5,6,7,1,2,3,4,5,6,性质,4,:,证明:假设深度为,k,,,则根据性质,2,和完全二叉树的定义有,2,k-1,-1n=2,k,-1,或,2,k-1,=n2,k,于是,k-1=log,2,n1,,,则其,双亲,是,i/2,(2),如果2,in,,,则结点,i,无左孩子;如果2,in,,,则其,左孩子是2,i,(3),如果2,i+1n,,,则结点,i,无右孩子;如果2,i+1n,,,则其,右孩子是2,i+1,i/2,i,i+1,2i,2i+1,2(i+1),2i+3,i+1,2(i+1),2i+3,i,2i,2i+1,图,6.11,完全二叉树中结点,i,和,i+1,(,a)i,和,i+1,结点在同一层,(,b)i,和,i+1,结点不在同一层,如图,6.11,所示为完全二叉树上结点及其,左右好在结点之间的关系。,证明:,可以从,(2),和,(3),推出,(1),,先证明,(2),和,(3),。,科学归纳法:,对于,i,1,,其左孩子是结点,2,,若,2n,,,即不存在结点,2,,此时,结点,i,无孩子。结点,i,的右孩子是结点,3,,若结点,3,不存在,即,3n,,,此时结点,i,无右孩子。,即,i=1,结论成立。,对于,i1,,,可分为两种情况:,(1),设第,j,层的,第一个结点,的编号为,i,,,由二叉树的性质,2,和定义知,i,2,j-1,结点,i,的左孩子,必定为的,j,1,层的第一个结点,其编号为,2,j,22,j-1,2i,。,如果,2,i,n,,,则无左孩子。,结点,i,右孩子,必定为第,j,1,层的第二个结点,编号为,2i,1,。若,2i+1n,,则无右孩子。,(2),假设第,j,层上的某个结点编号为,i,(2,j-1,=i=2,j,-1),且,2i,11,时,如果,i,为左孩子,即,2(i/2)=i,,则,i/2,是,i,的双亲;如果,i,为右孩子,,i,2p+1,,,i,的双亲应为,p,,,p,(i,1)/2=i/2.,证毕,。,6.2.3,二叉树的存储结构,二、二叉树的链式存储表示,一、二叉树的顺序存储表示,#define MAX_TREE_SIZE 100,/,二叉树的最大结点数,typedef,TElemType,SqBiTreeMAX_TREE_SIZE,;,/0,号单元存储根结点,SqBiTree,bt,;,一、二叉树的顺序存储表示,二叉树的存储结构,顺序存储结构,实现:按满二叉树的结点层次编号,依次存放二叉树中的数据元素,特点:,结点间关系蕴含在其存储位置中,浪费空间,适于存满二叉树和完全二叉树,(,比如深度为,k,的右单支树,需要,2,k,-1,个结点,有效结点为,k),a,b,c,d,e,f,g,a b c d e,0 0 0 0,f g,1 2 3 4 5 6 7 8 9 10 11,二、二叉树的链式存储表示,1.,二叉链表,2,三叉链表,3,双亲链表,4,线索链表,A,D,E,B,C,F,root,l,child,data,r,child,结点结构,:,1.,二叉链表,链式存储结构,二叉链表,typedef,struct,BiTNode,TElemType,data;,struct,BiTNode,*,lchild,*,rchild,;,BiTNode,*,BiTree,;,lchild,data,rchild,A,B,C,D,E,F,G,性质,6,:,在,n,个结点的二叉链表中,有,n+1,个空指针域,A,B,C,D,E,F,G,A,D,E,B,C,F,root,2,三叉链表,parent,lchild,data,rchild,结点结构,:,三叉链表,typedef,struct,BiTNode,TElemType,data;,struct,BiTNode,*,lchild,*,rchild,*parent;,BiTNode,*,BiTree,;,lchild,data parent,rchild,A,B,C,D,E,F,G,A,B,C,D,E,F,G,0,1,2,3,4,5,6,data parent,结点结构,:,3,双亲链表,LRTag,L,R,R,R,L,A,B,C,D,F,E,typedef,struct,BPTNode,/,结点结构,TElemType,data;,int,*parent;/,指向双亲的指针,char,LRTag,;/,左、右孩子标志域,BPTNode,typedef,struct,BPTree,/,树结构,BPTNode,nodesMAX_TREE_SIZE;,int,num_node,;/,结点数目,int,root;/,根结点的位置,BPTree,6.1,树的定义和基本概念,6.2,二叉树,6.3,遍历二叉树和线索二叉树,6.4,树和森林,6.6,哈夫曼树及其应用,第六章 树和二叉树,6.3.1,遍历二叉树,问题的提出,先序遍历,中序遍历,后序遍历,中序遍历的非递归算法,遍历算法的应用举例,6.3.2,线索二叉树,何谓线索二叉树?,线索链表的遍历算法,如何建立线索链表,6.3,遍历二叉树和线索二叉树,遍历二叉树是指按,一定的规律,对二叉树中的每个结点,均被访问一次,,而且,仅被访问一次,。,“,访问,”的含义可以很广,如:输出结点的信息或判定节点满足某些条件等。,“,遍历,”是任何类型均有的操作,对线性结构而言,只有一条搜索路径,(,因为每个结点均只有一个后继,),,故不需要另加讨论。而二叉树是树型结构,,每个结点有两个后继,,则,存在如何遍历,,即按什么样的,搜索路径,遍历的问题。,一、问题的提出(,寻找某个结点,),6.3,遍历二叉树和线索二叉树,对“二叉树”而言,可以有三条搜索路径:,1,先上后下,的按层次遍历;,2,先左,(子树),后右,(子树)的遍历;,3,先右,(子树),后左,(子树)的遍历。,先左后右的遍历算法,(,左子树总是先于右子树,),D,L,R,LDR,、,LRD,、,DLR,RDL、RLD、DRL,方法,先序,(,根,),遍历:,(1),访问,根结点,;,(2),先序遍历左子树;,(3),先序遍历右子树;,中序,(,根,),遍历:,(1),中序遍历左子树;,(2),访问,根结点,;,(3),中序遍历右子树;,后序,(,根,),遍历:,(1),后序遍历左子树,;(2),后序遍历右子树;,(3),访问,根结点,;,按层次遍历:从上到下、从左到右访问各结点,A,D,B,C,D L R,A,D L R,D L R,B,D,C,D L R,先序遍历序列:,A B D C,先序遍历,:,A,D,B,C,L D R,B,L D R,L D R,A,D,C,L D R,中序遍历序列:,B D A C,中序遍历,:,A,D,B,C,L R D,L R D,L R D,A,D,C,L R D,后序遍历序列:,D B C A,后序遍历,:,B,-,+,/,a,*,b,-,e,f,c,d,先序遍历:,中序遍历:,后序遍历:,层次遍历:,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,主程序,Pre(T),返回,返回,返回,返回,A,C,B,D,T,B,visit(B,);,pre(T,L);,B,T,A,visit(A,);,pre(T,L);,A,T,D,visit(D,);,pre(T,L);,D,T,C,visit(C,);,pre(T,L);,C,返回,T,左是空返回,pre(T,R);,T,左是空返回,T,右是空返回,T,左是空返回,T,右是空返回,pre(T,R);,先序序列:,A B D C,status,PreOrderTraversal(BiTree,T),if(T,),visit(T,-data);,PreOrderTraversal(T,-,lchild,);,PreOrderTraversal(T,-,rchild,);,return OK;,算法:递归算法,先序遍历,:,pre(T,R);,pre(T,R);,status,InOrderTraversal(BiTree,T),if(T,),InOrderTraversal(T,-,lchild,);,visit(T,-data);,InOrderTraversal(T,-,rchild,);,return OK;,status,PostOrderTraversal(BiTree,T),if(T,),PostOrderTraversal(T,-,lchild,);,PostOrderTraversal(T,-,rchild,);,visit(T,-data);,return OK;,中序遍历,:,后序遍历,:,非递归算法,(,中序,),A,B,C,D,E,F,G,p,i,P-A,(1),A,B,C,D,E,F,G,p,i,P-A,P-B,(2),A,B,C,D,E,F,G,p,i,P-A,P-B,P-C,(3),p=NULL,A,B,C,D,E,F,G,i,P-A,P-B,访问:,C,(4),p,A,B,C,D,E,F,G,i,P-A,访问:,C B,(5),A,B,C,D,E,F,G,i,P-A,P-D,访问:,C B,p,(6),A,B,C,D,E,F,G,i,P-A,P-D,P-E,访问:,C B,p,(7),A,B,C,D,E,F,G,i,P-A,P-D,访问:,C B E,p,(8),A,B,C,D,E,F,G,i,P-A,P-D,P-G,访问:,C B E,P=NULL,(9),A,B,C,D,E,F,G,i,P-A,访问:,C B E G D,p,(11),A,B,C,D,E,F,G,i,P-A,P-F,访问:,C B E G D,p,(12),A,B,C,D,E,F,G,i,P-A,P-D,访问:,C B E G,p,(10),A,B,C,D,E,F,G,i,P-A,访问:,C B E G D F,p=NULL,(13),A,B,C,D,E,F,G,i,访问:,C B E G D F A,p,(14),A,B,C,D,E,F,G,i,访问:,C B E G D F A,p=NULL,(15),思考:,访问的第一个结点的特点,前序,后序栈的操 作,层次遍历?,四、中序遍历算法的非递归描述,Status,InOrderTraverse(BiTree,T,Status(*,Visit)(TElemType,e),InitStack(S,);,Push(S,T,),/,根指针进栈,while(!,StackEmpt(S,),while(GetTop(S,p,)&p),Push(S,p,-,lchild,);,Pop(S,p,);,/,空指针退栈,if(!,StackEmpty(S,),Pop(S,p,);,if(!,Visit(p,-data,)return ERROR;,Push(S,p-,rchild,);,/if,/while,return OK;,/,InOrderTraverse,四、中序遍历算法的非递归描述,BiTNode,*,GoFarLeft(BiTree,T,Stack*S),/T,为树根结点的指针,if(!T)return NULL;,while(T-,lchild,),Push(S,T);,T=T-,lchild,;,return T;,/,得到树,T,最左,叶子结点的指针,void,InorderTree(BiTree,T,void(*visit)(,TelemType,&e),Stack*S;,BiTree,t,p,;p=T-,lchild,;,t=,GoFarLeft(p,S);,/,找到最左下的结点,while(t),visit(t-data);,if(t-,rchild,),t=,GoFarLeft(t,-,rchild,S);,else if(!,StackEmpty(S,),/,栈不空时退栈,t=Pop(S);,else t=NULL;,/,栈空表明遍历结束,/while,/,InorderTree,说明:,由一棵给定的二叉树可以获得三种遍历序列,同样,也可以由这些遍历序列来重新构造二叉树。,单用一个遍历序列是无法构造二叉树的,因为无法从遍历序列中区分二叉树的左、右子树。,利用中序遍历序列,并结合先序遍历序列或后序遍历序列就能重新构造二叉树,。,本章实验内容,编写一个程序,输入先序遍历序列和中序遍历序列,由先序遍历和中序遍历序列,构造出一棵二叉树,,然后用,后序遍历,输出该二叉树。,先序遍历序列和中序遍历序列的结点分布特点:,先序遍历序列:,中序遍历序列:,二叉树的构造步骤:,1,),从先序遍历序列中取出第一个结点,,该结点一定是二叉树的,根,。然后在,中序遍历序列,中找到根结点,根结点前面的结点序列就是,左子树,的中序遍历序列,根结点后面的结点序列就是,右子树,的中序遍历序列。,2,)对根的左子树先序遍历序列和中序遍历序列及右子树的先序遍历序列和中序遍历序列,再,执行第一步,,直到得出所有叶子结点为止。,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,先序序列,中序序列,main(),输入先序序列,=,preod,输入中序序列,=,inod,PreInOd(preod,1,n,inod,1,n,void,PreInOd(char,preod,int,i,int,j,char,inod,int,k,int,h,BiTree,*t),申请结点空间,=t;,t-data=,preodi,;,查找,t-data,在,inod,中的位置,=m,if(m=k)t-,lchild,=Null;,else,PreInOd(preod,i+1,i+m-k,inod,k,m-1,&(t-,lchild,);,/,递归建立左子树,if(m=h)t-,rchild,=NULL;,else PreInOd(preod,i+m-k+1,j inod,m+1,h&(t-,rchild,);,练习,如图所示二叉树的中序遍历序列是()。,A,abcdgef,B,dfebagc,C,dbaefcg,D,defbagc,练习,1),已知一棵二叉树的先根序列为,ABDGCFK,,中根序列为,DGBAFCK,,则结点的后根序列为()。,A,ACFKDBGB,GDBFKCAC,KCFAGDBD,ABCDFKG,2),已知某二叉树的后序遍历序列是,dabec,,中序遍历序列是,debac,,它的前序遍历序列是()。,A,acbed,B,decab,C,deabc,D,cedba,利用中序遍历序列,并结合先序遍历序列或后序遍历序列重新构造二叉树。,例一,先序:,ABCDEFGHIJ,中序:,CBDEAFHIGJ,例二,中序:,ABCDJEFHGI,后序:,BCJDAHIGFE,练习,五,、,遍历算法的应用举例,2,、统计二叉树中叶子结点的个数,(,先序遍历,),3,、求二叉树的深度,(,后序遍历,),1,、按先序遍历序列建立二叉树的二叉链表,以字符串的形式,根 左子树 右子树,定义一棵二叉树,例如,:,A,B,C,D,以空白字符,“,”,表示,A,(,B,(,C,(,),D,(,),空树,只含一个根结点的二叉树,A,以字符串,“,A,”,表示,以下列字符串表示,遍历算法应用,按先序遍历序列建立二叉树的二叉链表,已知先序序列为:,A B C,D E G F ,A,B,C,D,E,F,G,A ,B,C ,D,E,F ,G ,status,CreateBitree(BiTree&T,),scanf(&ch,);,if(ch,=|,ch,=n)T=NULL;,else,if(!(T,=(,BiTnode,*),malloc(sizeof(BiTnode,),exit(overflow,);,T-data=,ch,;,CreateBitree(T,-,lchild,);,CreateBitree(T,-,rchild,);,return OK;,A B C D,A,B,C,D,上页算法执行过程举例如下:,A,T,B,C,D,2,、统计二叉树中叶子结点的个数,算法基本思想,:,先序,(,或中序或后序,),遍历二叉树,在遍历过程中查找叶子结点,并计数。,需在遍历算法中增添一个,“,计数,”,的参数,并将算法中,“,访问结点,”,的操作改为:若是叶子,则计数器增,1,。,void,CountLeaf,(,BiTree,T,int,&count),if(T),if(!T-,lchild,)&(!T-,rchild,),count+;/,对叶子结点计数,CountLeaf,(T-,lchild,count),;,CountLeaf,(T-,rchild,count),;,/if,/,CountLeaf,统计二叉树中叶子结点个数算法,A,B,C,D,E,F,G,int,BitreeLeafCount(BiTree,T),if(T=NULL)return 0;,else if(T-,lchild,=NULL&T-,rchild,=NULL),return 1;,else return,BitreeLeafCount(T,-,lchild,)+,BitreeLeafCount(T,-,rchild,);,A,B,C,D,E,F,G,统计二叉树中结点个数算法,int,BitreeCount(BiTree,T),if(T=NULL)return 0;,else return,BitreeCount(T,-,lchild,)+,BitreeCount(T,-,rchild,)+1;,求二叉树深度算法,int,BitreeDepth(BiTree,T),if(T=NULL)depth=0;,else,ldepth,=,BitreeDepth(T,-,lchild,);,rdepth,=,BitreeDepth(T,-,rchild,);,depth=1+(ldepth,rdepth?ldepth:rdepth,);,return depth;,A,B,C,D,E,F,G,线索二叉树,何谓线索二叉树?,线索链表的遍历算法,如何建立线索链表?,一、,何谓线索二叉树?,遍历二叉树的结果是,求得结点的一个,线性序列,。,A,B,C,D,E,F,G,H,K,例如,:,先序序列,:,A B C D E F G H K,中序序列,:,B D C A H G K F E,后序序列,:,D C B H K G F E A,指向该线性序列中的“前驱”和 “后继”的指针,称作,“线索”,与其相应的二叉树,称作,“线索二叉树”,包含“线索”的存储结构,称作,“线索链表”,A B C D E F G H K,D,C,B,E,对,线索链表,中结点的约定:,在二叉链表的结点中,增加两个标志域,:,若该结点的左子树不空,,则,Lchild,域的指针指向其左子树,且左标志域的值为,“,指针,Link,”,;,否则,,Lchild,域的指针指向其“前驱”,且左标志的值为,“,线索,Thread,”,.,lchild,Ltag,data,Rtag,rchild,若该结点的右子树不空,,则,rchild,域的指针指向其右子树,且右标志域的值为,“,指针,Link,”,;,否则,,rchild,域的指针指向其“后继”,且右标志的值为,“,线索,Thread,”,。,如此定义的二叉树的存储结构称作,“,线索链表,”,。,typedef,struct,BiThrNod,TElemType,data;,struct,BiThrNode,*,lchild,*,rchild,;/,左右指针,PointerThr,LTag,RTag,;/,左右标志,BiThrNode,*,BiThrTree,;,线索链表,的类型描述:,typedef,enum,PointerTag,Link,Thread,;,/Link=0:,指针,,Thread=1:,线索,lchild,Ltag,data,Rtag,rchild,A,B,C,D,E,A,B,D,C,E,T,0,0,0,0,1,1,1,1,1,1,typedef,struct,BiThrNode,TElemType,data;,struct,BiThrNode,*,lchild,*,rchild,;,PointTag,Ltag,Rtag,;,BiThrNode,*,BiThrTree,;,lchild,Ltag,data,Rtag,rchild,结点定义:,Typedef,enum,PointerTag,Link,Thread;,先序序列:,ABCDE,先序线索二叉树,A,B,C,D,E,A,B,D,C,E,T,0,0,0,0,1,1,1,1,1,1,中序序列:,BCAED,中序线索二叉树,A,B,C,D,E,A,B,D,C,E,T,0,0,0,0,1,1,1,1,1,1,后序序列:,CBEDA,后序线索二叉树,二、线索链表的遍历算法,for(,p=,firstNode(T,),;,p;,p=,Succ(p,),),Visit(p);,由于在线索链表中添加了遍历中得到的,“,前驱,”,和,“,后继,”,的信息,从而简化了遍历的算法。,例如,:,对中序线索化链表的遍历算法,中序遍历的第一个结点?,在中序线索化链表中结点的后继?,左子树上处于,“,最左下,”,(没有左子树)的结点。,若,无右子树,,则为,后继线索所指结点;,否则为,对其右子树进行中序遍历时访问的第一个结点。,void,InOrderTraverse_Thr(BiThrTree,T,void(*,Visit)(TElemType,e),p=T-,lchild,;,/p,指向根结点,while(p!=T),/,空树或遍历结束时,,p=T,while(p-,LTag,=Link)p=p-,lchild,;,/,第,一个结点,while(p-,RTag,=Thread&p-,rchild,!=T),p=p-,rchild,;Visit(p-data);,/,访问后继结点,p=p-,rchild,;,/p,进至其右子树根,/,InOrderTraverse_Thr,在中序遍历过程中修改结点的左、右指针域,以保存当前访问结点的“,前驱,”和“,后继,”信息。,遍历过程中,附设指针,pre,并始终保持指针,pre,指向当前访问的、指针,p,所指结点的,前驱,。,三、如何建立线索链表?,void,InThreading(BiThrTree,p),if(p),/,对以,p,为根的非空二叉树进行线索化,InThreading(p,-,lchild,);,/,左子树线索化,if(!p-,lchild,),/,建前驱线索,p-,LTag,=Thread;p-,lchild,=pre;,if(!pre-,rchild,),/,建后继线索,pre-,RTag,=Thread;pre-,rchild,=p;,pre=p;,/,保持,pre,指向,p,的前驱,InThreading(p,-,rchild,);,/,右子树线索化,/if,/,InThreading,Status,InOrderThreading(BiThrTree,&,Thrt,BiThrTree,T),/,构建中序线索链表,if(!(,Thrt,=,(,BiThrTree)malloc,(,sizeof,(,BiThrNode,),exit(OVERFLOW);,Thrt,-,LTag,=Link;,Thrt,-,RTag,=Thread;,Thrt,-,rchild,=,Thrt,;,/,添加头结点,return OK;,/,InOrderThreading,if(!T),Thrt,-,lchild,=,Thrt,;,else,Thrt,-,lchild,=T,;,pre=,Thrt,;,InThreading(T,);,pre-,rchild,=,Thrt,;/,处理最后一个结点,pre-,RTag,=Thread;,Thrt,-,rchild,=pre,;,6.1,树的定义和基本概念,6.2,二叉树,6.3,遍历二叉树和线索二叉树,6.4,树和森林,6.6,哈夫曼树及其应用,第六章 树和二叉树,6.4,树和森林,6.4.1,树的存储结构,6.4.2,森林与二叉树的转换,6.4.3,树和森林的遍历,6.4.1,树的三种存储结构,一、,双亲表示法,二、,孩子链表表示法,三、,树的二叉链表,(,孩子,-,兄弟)存储表示法,A,B,C,D,E,F,G,0,A,-1,1,B,0,2,C,0,3,D,0,4,E,2,5,F,2,6,G,5,r=0,n=6,data parent,一、双亲表示法,typedef,struct,PTNode,Elem data;,int,parent;,/,双亲位置域,PTNode,;,data parent,#define,MAX_TREE_SIZE 100,结点结构,:,C,语言的类型描述:,typedef,struct,PTNode,nodes MAX_TREE_SIZE;,int,r,n;,/,根结点的位置和结点个数,PTree,;,树结构,:,a,b,c,d,e,f,h,g,i,6,0,1,2,3,4,5,7,8,9,a,c,d,e,f,g,h,i,b,data,fc,2,3,4,5,9,7,8,6,如何找双亲结点,孩子链表:每个结点的孩子结点用,单链表存储,,再用含,n,个元素的,结构数组,指向每个孩子链表,二、孩子链表表示法,带双亲的孩子链表,6,1,2,3,4,5,7,8,9,a,c,d,e,f,g,h,i,b,data,fc,2,3,4,5,9,7,8,6,0,1,2,2,3,5,5,5,1,parent,a,b,c,d,e,f,h,g,i,typedef,struct,CTNode,int,child;,struct,CTNode,*,next;,*,ChildPtr,;,孩子结点结构,:,child next,C,语言的类型描述:,typedef,struct,Elem data;,ChildPtr,firstchild,;/,孩子链的头指针,CTBox,;,双亲结点结构,data,firstchild,typedef,struct,CTBox,nodesMAX_TREE_SIZE;,int,n,r;/,结点数和根结点的位置,CTree,;,树结构,:,三、孩子兄弟表示法,(,二叉树表示法,),实现:用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其,第一个孩子结点,和,下一个兄弟结点,特点,操作容易,破坏了树的层次,typedef,struct,CSNode,ElemType,data;,struct,CSNnode,*,firstchild,*,nextsibling,;,CSNode,*,CSTree,;,a,b,c,d,e,f,h,g,i,a,b,c,d,e,f,g,h,i,A,B,C,D,E,F,G,A,B,C,E D,F,G,root,A,B,C,E D,F,G,三、树的二展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


数据结构-第6章-树.ppt
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14775537.html