云大数据结构课程教学树和二叉树.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/12/21,数据结构,#,2025/8/19 周二,数据结构,1,第六章 树,树形结构是一种重要的非线性结构，在我们的客观世界和现实生活中大量存在。,我们学院的组织结构：,在计算机领域也常用到树形结构。例如编译程序中用树表示源程序语法结构，数据库系统中用树组织信息等等。,2025/8/19 周二,数据结构,2,我们的家谱：,张林,张源,张明,张亮,张磊,张京,张群,张华,张平,张维,张力,2025/8/19 周二,数据结构,3,6.1,树的概念,1,、树的定义：,树,(Tree),是,n(n0),个结点的有限集合,T,，它满足如下条件：,(1),有且仅有一个称为根,(Root),的结点。,(2),其余结点可分为,m(m=0),个互不相交的有限集合,T1,T2,Tm,其中每个集合又是一棵树，并称其 为根的子树（,Subtree,）。这是一个递归定义。有时,n=0,也称为空树。,A,B,C,D,E,F,G,集合,1,集合,2,集合,3,一、树的基本概念,2025/8/19 周二,数据结构,4,2,、树的表示方法,1,）树形图法,2,）嵌套集合法,3,）广义表形式,4,）凹入表示法,(A(B,C(E,F),D(G),A,B,C,D,E,F,G,A,B,C,E,F,D,G,A,B,D,G,E,F,C,2025/8/19 周二,数据结构,5,1,）结点的度,(Degree),：,为该结点的子树的个数。,2,）树的度：,为该树中结点的最大度数。,3,）终端结点,(,叶子,),：,度为零的结点。,4,）非终端结点,(,分支结点,),：,度不为零的结点。,5,）内部结点：,除根结点之外的分支结点。,A,C,D,E,F,G,B,3,、树结构的基本术语,2025/8/19 周二,数据结构,6,6,）孩子,(child),：结点的子树之根,双亲（,parent):,该结点称为孩子的双亲,兄弟,(sibling):,同一双亲的孩子,堂兄弟（,cousin):,双亲不同但其双亲处于同一层的结点,7,）路径,(Path),：,若树中存在一个结点序列,k1,k2,kj,使得,ki,是,ki+1,的双亲,(1=i=0),棵,互不相交的树的集合称为森林。,关系：,树,森林,删去一个树根,加上一个树根,A,C,D,E,F,G,B,2025/8/19 周二,数据结构,9,三、树的逻辑运算,1.setnull(T):,置,T,为空树。,2.root(T),或,root(x):,求树,T,或结点,x,所在树的根结点。,3.parent(T,x):,求,T,中,x,结点的双亲，若,x,为根或,x,不在树中，结果为空。,4.child(T,x,i):,求,T,中,x,结点从左至右第,i,个孩子，若,x,为叶子或,x,不在树中，结果为空。,2025/8/19 周二,数据结构,10,6.2,二 叉 树,6.2.1,二叉树的概念,一、二叉树的定义：,二叉树,(Binary Tree),是,n(n=0),个结点的有限集，它或者是空集,(n=0),或者由一个根结点和两棵互不相交的，分别称为根的左子树和右子树的二叉树组成。,可以看出，二叉树的定义和树的定义一样，均为递归定义。,2025/8/19 周二,数据结构,11,二、二叉树的五种基本形态,：,空二叉树,只有一个根结点,的二叉树,右子树为空,的二叉树,左子树为空,的二叉树,左、右子树均,非空的二叉树,注意：,二叉树中子树是有左右之分的，即使只有一棵子树，或为左子树，或为右子树，这一点与度为,2,的有序树不同。,这不是二叉树,这是二叉树,2025/8/19 周二,数据结构,12,6.2.2,二叉树的性质,性质,1,：,二叉树第,i,层上的结点数目最多为,2,i-1,(i=1),该性质可用数学归纳法证明。,证明,:,归纳基础,:,i=1,时,有,2,i-1,=2,0,.,因为第,1,层上只有一个根结点,所以命题成立,.,归纳假设,:,假设对所有的,j(1=j=1),证明,:,在具有相同深度的二叉树中，仅当每一层都含有最大结点数时,其树中结点数最多。因此，利用性质,1,可得,深度为,k,的二叉树的结点数至多为：,2,0,+2,1,+.+2,k-1,=2,k,-1,故命题成立,.,2025/8/19 周二,数据结构,14,性质,3,：,任意二叉树中，若叶结点的个数为,n0,度为,2,的结点数为,n2,，则,n0=n2+1,。,证明：,设,n1,为二叉树,T,中度为,1,的结点数。因为二叉树中所有结点的度均为小于或等于,2,，所以其结点总数为：,n=n0+n1+n2 (6-1),另一方面,1,度结点有一个孩子,2,度结点有两个孩子,故二叉树中孩子结点的总数是,n1+2*n2,但树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：,n=n1+2*n2+1 (6-2),由式,(6-1),和,(6-2),得,n0=n2+1,2025/8/19 周二,数据结构,15,两种特殊形态的二叉树：,满二叉树,和,完全二叉树,深度为,k,且有,2,k,-1,个结点的二叉树称为,满二叉树,。,若一棵二叉树至多只有最下面的两层上结点的度数可以小于,2,，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为,完全二叉树,。,满二叉树,1,2,3,4,5,6,7,非完全二叉树,1,2,3,4,5,6,完全二叉树,2,3,4,5,1,2025/8/19 周二,数据结构,16,两种特殊形态的二叉树：,满二叉树,和,完全二叉树,深度为,k,且有,2,k,-1,个结点的二叉树称为,满二叉树,。,对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左至 右。,深度为,k,的，有,n,个结点的二叉树，当且仅当其每一个结点都与深度为,k,的满二叉树中编号从,1,至,n,的结点一一对应，则称之为,完全二叉树,。,满二叉树,1,2,3,4,5,6,7,非完全二叉树,1,2,3,4,5,6,完全二叉树,2,3,4,5,1,2025/8/19 周二,数据结构,17,根据定义,:(1),满二叉树是完全二叉树,反之不成立,;(2),对于完全二叉树,若某结点无左孩子,则必无右孩子,该结点为叶结点,;,证明：,设深度为,k,，则根据性质,2,和完全二叉树的定义有,2,k-1,-1n=2,k,-1,即,2,k-1,=n2,k,于是,k-1=log,2,nk,又因为,k,是整数，,所以,k-1=,log,2,n,，即,k=,log,2,n,+1,性质,4,：,具有,n,个结点的完全二叉树的深度为,log,2,n,+1(,log,2,(n+1),),2025/8/19 周二,数据结构,18,性质,5,：,如果对一棵有,n,个结点的完全二叉树的结点按层次编号,(,即自上而下，自左至右,),，则对任一结点,i(1=i1,则其双亲是编号为,i/2,的结点。,(2),如果,2*in,则结点,i,无左孩子；否则其左孩子是编号为,2*i,的结点。,(3),如果,2*i+1n,则结点,i,无右孩子；否则其右孩子是编号为,2*i+1,的结点。,(4)若,i,为奇数且不为1,则结点,i,的左兄弟的编号是,i-1;,否则,结点,i,无左兄弟。,(5),若,i,为偶数且小于,n,则结点,i,的右兄弟的编号是,i+1;,否则,结点,i,无右兄弟。,2,3,4,5,1,2025/8/19 周二,数据结构,19,6.2.3,二叉树的存储,1.,顺序存储结构,1,）对于,完全二叉树,可以采用,顺序存储结构,(,即一维数组,),进行存储，编号为,i,的结点存放在第,i,个数组元素所分配的存储单元中，完全二叉树结点之间的逻辑关系通过数组元素的下标体现。,完全二叉树,a,b,c,d,e,非完全二叉树,a,b,c,d,e,f,0 1 2 3 4 5,a b c d e,下标,元素,0 1 2 3 4 5 6 7,a b c *d e f,下标,元素,“,虚结点”占据,的空间,补设的“虚结点”,2025/8/19 周二,数据结构,20,2,）对于非完全二叉树，通过补设一些,“虚结点”,，使得二叉树的结点的编号与完全二叉树相同，再进行顺序存储。每个“虚结点”都将占据一个数组元素存储单元。,结论：非完全二叉树采用顺序存储结构会造成存储空间的浪费。,2025/8/19 周二,数据结构,21,二叉树除了可以采用顺序存储结构实现存储外,还可以采用,链式存储结构,进行存储,与采用顺序存储结构相比,采用链式存储结构实现二叉树的存储显得更自然,.,1,）链式存储结构中结点的结构,:,lchild data rchild,指向左孩子的指针域,指向右孩子的指针域,存放数据,2,、链式存储结构,2025/8/19 周二,数据结构,22,2,）结点的存储描述,:,typedef struct nodedatatype data;struct node*lchild,*rchild;bitree;,bitree *root;,所有类型为,node,的结点，再加上一个指向根结点的头指针,root,，就构成了二叉树的存储结构，称为,二叉链表。,lchild data rchild,指向左孩子的指针域,指向右孩子的指针域,存放数据,2025/8/19 周二,数据结构,23,a,b,c,d,e,二叉树,a,b,c,d,e,root,二叉链表,链式存储,例：,说明：,1,）一个二叉链表由头指针唯一确定。若二叉树为空，则,root=NULL,。,2,）在,n,个结点的二叉树中一共有,2n,个指针域，,n+1,个为空，,n-1,个非空。,2025/8/19 周二,数据结构,24,3,）二叉链表是二叉树最常用的存储结构。还有其它链接方法，采用何种方法，主要取决于所要实施的各种运算频度。,例,:,若经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针域,parent,，称为,三叉链表,。,lchild data parent rchild,root,三叉链表,a,b,c,d,e,a,b,c,d,e,二叉树,链式存储,2025/8/19 周二,数据结构,25,特殊的，,为了方便找到结点的双亲,还可以在结点结构中增加一个指向该结点双亲的指针域,:,dada,lchild,parent,rchild,左指针,数据域,双亲指针,右指针,2025/8/19 周二,数据结构,26,若二叉树中每一个结点均采用上述第一或第二种结构,由此便实现了二叉树的链式存储,这种存储结构又称为,二叉链表,或,三叉链表,。此外,还需引入一个指针变量,使其指向根结点,.,该指针变量说明如下,:,bitree *root;,a,b,c,d,e,二叉树,a,b,c,d,e,root,二叉链表,链式存储,root,三叉链表,a,b,c,d,e,2025/8/19 周二,数据结构,27,2,）结点的存储描述,:,typedef struct nodedatatype data;struct node*lchild,*rchild;bitree;,bitree *root;,所有类型为,node,的结点，再加上一个指向根结点的头指针,root,，就构成了二叉树的存储结构，称为,二叉链表。,lchild data rchild,指向左孩子的指针域,指向右孩子的指针域,存放数据,2025/8/19 周二,数据结构,28,3,、二叉树的生成,1,）顺序存储结构非常简单：,从终端上读入数据填入数组,2,）二叉链表的生成,基本思想：,按完全二叉树的层次顺序,(,非完全二叉树添加虚结点,),，依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点；,否则将新结点作为孩子链接到它的双亲结点上,。如此重复下去，直至所有结点送完并以特殊字符结束。,实现技巧：,实现过程中引入一个指针队列，该队列中的每个元素指向相应结点。,2025/8/19 周二,数据结构,29,事实上：,先入队的结点其孩子必将先入队。因此,front,指针指向的队列元素所指向的结点为当前必须与其孩子建立链接的双亲结点，而,rear,指针指向的队列元素所指向的结点为当前必须与其双亲建立链接的孩子结点。当,rear,为偶数时，为左孩子，否则为右孩子。,算法描述,：,bitree*qmaxsize;,/*,队列,q,为,bitree,指针类型的数组*,/,bitree *creattree()char ch;int front,rear;bitree*root,*s;root=NULL;,/*,置空二叉树*/,front=1;rear=0;,/*,置空队列*,/,ch=getchar();,2025/8/19 周二,数据结构,30,前者简单，不在此讨论，这里仅说明后者的处理方法。,基本思想：,按完全二叉树的层次顺序,(,非完全二叉树添加虚结点,),，依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点；否则将新结点作为孩子链接到它的双亲结点上。如此重复下去，直至所有结点送完并以特殊字符结束。,算法在实现过程中引入一个指针队列，该队列中的每个元素指向相应结点。,注意一个事实：,先入队的结点其孩子必将先入队。因此,front,指针指向的队列元素所指向的结点为当前必须与其孩子建立链接的双亲结点，而,rear,指针指向的队列元素所指向的结点为当前必须与其双亲建立链接的孩子结点。当,rear,为偶数时，为左孩子，否则为右孩子。,算法描述：,bitree*qmaxsize;,/*,队列,q,为,bitree,指针类型的数组*,/,bitree *creattree()char ch;int front,rear;bitree*root,*s;,while(ch!=,#,),/*,#,为结束符号*/,s=NULL;,if(ch!=,),/*,为虚结点符号，不是虚结点时建立新结点*/,s=malloc(sizeof(bitree);s,data=ch;s lchild=NULL;s rchild=NULL;,rear+;qrear=s;,/*,将虚结点指针或新结点地址入队*,/,if(rear=1)root=s;,else if(s&qfront),/*,孩子和双亲结点均不是虚结点*,/,if(rear%2=0)qfront lchild=s;,/*rear,为,偶数，新结点是左孩子*,/,else qfront rchild=s;if(rear%2=1)front+;,/*,结点,Qfront,的孩子处理完毕，出队列*,/,ch=getchar();,return root;,2025/8/19 周二,数据结构,32,while(ch!=,#,),s=NULL;,if(ch!=,),/*,为虚结点符号，不是虚结点时建立新结点*/,s=malloc(sizeof(bitree);s,data=ch;s lchild=NULL;s rchild=NULL;,rear+;qrear=s;,/*,将虚结点指针或新结点地址入队*,/,if(rear=1)root=s;,else if(s&qfront),/*,孩子和双亲结点均不是虚结点*,/,if(rear%2=0)qfront lchild=s;else qfront rchild=s;,if(rear%2=1)front+;,/*,结点,Qfront,出队列*,/,ch=getchar();,return root;,2025/8/19 周二,数据结构,33,作业,:,6.2 6.3 6.4 6.5,2025/8/19 周二,数据结构,34,6.3,二叉树的遍历,二叉树的遍历指的是沿某条搜索路径访问二叉树，对二叉树中的每个结点访问,一次且仅一次,。这里的“访问”实际上指的是对结点进行某种操作。,(,以下“访问”特指打印该结点信息,),2,、遍历方法的推导,1,、定义,非空二叉树,根结点,D,左子树,L,右子树,R,P,3,=6,3,DLRLDRLRD,DRLRDLRLD,先左后右,先右后左,前序遍历,中序遍历,后序遍历,2025/8/19 周二,数据结构,35,1),前序遍历二叉树,前序遍历算法：先访问根结点，再 遍历左子树最后 遍历右子树,3,、遍历算法,a,b,c,d,e,前序遍历结果,a b d e c,e,的前序遍,历前趋为,d,e,的逻辑前趋为,b,前序,前序,若二叉树非空,2025/8/19 周二,数据结构,36,非空的二叉树可以分成三部份：根结点，左子树和右子树。因此，对二叉树的遍历可以分成三个子问题：访问根结点，遍历左子树，遍历右子树。若分别以,D,，,L,，,R,表示上述三个子问题，则对二叉树存在六种遍历次序：,DLR,，,LDR,，,LRD,，,DRL,，,RDL,，,RLD,。后三种与前三种对称，因此仅需讨论前三种。,按照根结点在遍历过程中被访问的先后次序，,DLR,、,LDR,和,LRD,分别被称为前序、中序和后序遍历。,1.,前序遍历二叉树,遍历过程,：若二叉树非空，则,先,访问根结点，再,前序,遍历左子树，最后,前序,遍历右子树。,对如下的二叉树，进行前序遍历，得到怎样的结果？,2025/8/19 周二,数据结构,37,算法描述：,preorder(t)bitree *t;if(t)printf(,“,t%c,”,t,data);,preorder,(t lchild);,preorder,(t rchild);,2),中序遍历二叉树,中序遍历算法,：,若二叉树非空,，,先,中序,遍历左子树，,再,访问根结点，最后,中序,遍历右子树,2025/8/19 周二,数据结构,38,a,b,c,d,e,中序遍历结果,d b e a c,算法描述：,inorder(t)bitree *t;if(t),inorder,(t lchild);,printf(,“,t%c,”,t-data);,inorder,(t rchild);,2025/8/19 周二,数据结构,39,3,）后序遍历二叉树,后序遍历算法：若二叉树非空，先,后序,遍历左子树，再,后序,遍历右子树，最后访问根结点。,a,b,c,d,e,后序遍历结果,d e b c a,2025/8/19 周二,数据结构,40,算法描述：,postorder(t)bitree *t;if(t),postorder,(t lchild);,postorder,(t rchild);printf(,“,t%c,”,t-data);,2025/8/19 周二,数据结构,41,说明,:1),递归算法的终止条件是二叉树为空,.,2),三个算法具有相同的搜索路径,:,该路线从根结点出发,逆时针沿二叉树外缘移动,对每个结点均途径三 次,.,若访问结点均是在第一次经过结点时进行的,则是前序遍历,若访问结点均是在第二次,(,或第三次,),经过结点时进行的,则是中序遍历,(,或后序遍历,).,a,b,c,d,e,f,第一次：,a b d c e f,第二次：,d b a e c f,第三次：,d b e f c a,abdddbbaceeecfffca,2025/8/19 周二,数据结构,42,3,）遍历序列的前趋、后继的称谓问题：,对于上述三种遍历序列，均在某结点的前趋和后继之前加上遍历次序的名称。,a,b,c,d,e,f,例：对于,C,结点，其前序前趋结点是,D,其前序后继结点是,E,。,中序前趋结点是,E,中序后继结点是,F,后序前趋结点是,F,后序后继结点是,A,但是就该树的逻辑结构而言，,C,的前趋结点是,A,，后继结点是,E,和,F,。,第一次：,a b d c e f,第二次：,d b a e c f,第三次：,d b e f c a,程序跟踪见动态演示,1),Inorder(t=&a),2),Inorder(t=&b),1),2),Inorder(t=&d),1),2),Inorder(t=NULL),12 3,a,e,f,c,d,b,t,t,t,t,inorder(t)bitree *t;,1),、,if(t),2),、,inorder(t lchild);,3),、,printf(“t%c”,t-data);,4),、,inorder(t rchild);,5),、,4),Inorder(t=NULL),1),Inorder(t=&a),2),Inorder(t=&b),1),2),Inorder(t=&d),1),2),Inorder(t=NULL),1),3),5),打印,d,12 3,a,e,f,c,d,b,t,t,t,inorder(t)bitree *t;,1),、,if(t),2),、,inorder(t lchild);,3),、,printf(“t%c”,t-data);,4),、,inorder(t rchild);,5),、,1),Inorder(t=&a),2),Inorder(t=&b),1),2),Inorder(t=&d),1),2),Inorder(t=NULL),1),3),2),4),Inorder(t=NULL),5),1),5),打印,d,12 3,a,e,f,c,d,b,t,inorder(t)bitree *t;,1),、,if(t),2),、,inorder(t lchild);,3),、,printf(“t%c”,t-data);,4),、,inorder(t rchild);,5),、,打印,b,3),1),Inorder(t=&a),2),Inorder(t=&b),1),2),Inorder(t=&d),1),2),Inorder(t=NULL),1),3),5),4),Inorder(t=NULL),5),1),5),打印,d,4),Inorder(t=NULL),12 3,a,e,f,c,d,b,t,t,t,inorder(t)bitree *t;,1),、,if(t),2),、,inorder(t lchild);,3),、,printf(“t%c”,t-data);,4),、,inorder(t rchild);,5),、,inorder(t)bitree *t;,1),、,if(t),2),、,inorder(t lchild);,3),、,printf(“t%c”,t-data);,4),、,inorder(t rchild);,5),、,5),1),5),12 3,a,e,f,c,d,b,t,打印,b,3),1),Inorder(t=&a),2),Inorder(t=&b),1),2),Inorder(t=&d),1),2),Inorder(t=NULL),1),3),5),4),Inorder(t=NULL),5),1),5),打印,d,4),Inorder(t=NULL),3),12 3,打印,a,a,e,f,c,d,b,t,t,inorder(t)bitree *t;,1),、,if(t),2),、,inorder(t lchild);,3),、,printf(“t%c”,t-data);,4),、,inorder(t rchild);,5),、,打印,b,3),1),Inorder(t=&a),2),Inorder(t=&b),1),2),Inorder(t=&d),1),2),Inorder(t=NULL),1),3),5),4),Inorder(t=NULL),5),1),5),打印,d,4),Inorder(t=NULL),5),1),5),12 3,打印,a,a,e,f,c,d,b,t,inorder(t)bitree *t;,1),、,if(t),2),、,inorder(t lchild);,3),、,printf(“t%c”,t-data);,4),、,inorder(t rchild);,5),、,4),Inorder(t=&c),打印,b,3),1),Inorder(t=&a),2),Inorder(t=&b),1),2),Inorder(t=&d),1),2),Inorder(t=NULL),1),3),5),4),Inorder(t=NULL),5),1),5),打印,d,4),Inorder(t=NULL),5),1),5),3),1),4),Inorder(t=NULL),5),1),5),3),打印,b,4),Inorder(t=NULL),5),1),5),3),打印,a,4),Inorder(t=&c),Inorder(t=&a),2),Inorder(t=&b),1),2),Inorder(t=&d),1),2),Inorder(t=NULL),5),1),2),4),5),3),Inorder(t=&e),1),2),4),5),3),Inorder(t=NULL),1),5),打印,e,Inorder(t=NULL),1),5),Inorder(t=&f),1),2),4),5),3),Inorder(t=NULL),1),5),打印,f,Inorder(t=NULL),1),5),打印,c,1),3),5),打印,d,d b a e c f,中序序列,12 3,2025/8/19 周二,数据结构,51,中序遍历,(LDR),前提,:,二叉树非空,(1),中序,遍历左子树,(2),访问根结点,(3),中序,遍历右子树,后序遍历,(LRD),前提,:,二叉树非空,(1),后序,遍历左子树,(2),后序,遍历右子树,(3),访问根结点,前序遍历,(DLR),前提,:,二叉树非空,(1),前序,遍历左子树,(2),访问根结点,(3),前序,遍历右子树,2025/8/19 周二,数据结构,52,b,f,c,a,e,d,从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途经三次。,12 3,b,f,c,a,e,d,Inorder(t=NULL),打印,b,Inorder(t=NULL),打印,a,Inorder(t=&c),Inorder(t=&a),Inorder(t=&b),Inorder(t=&d),Inorder(t=NULL),打印,d,2025/8/19 周二,数据结构,54,b,f,c,a,e,d,a c e e e c f f f c a,a,b,d,d,d,b,b,第一次经过的结点,:,第二次经过的结点,:,第三次经过的结点,:,前序序列,中序序列,后序序列,a,b,d,e,c,f,d,b,a,c,e,f,d,b,e,c,f,a,2025/8/19 周二,数据结构,55,b,f,c,a,e,d,t,t,&a,&b,&d,t,t,&a,&b,2025/8/19 周二,数据结构,56,算法描述如下：,typedef bitree*datatype;typedef struct node datatype data;struct node*next;linkstack;,inorder(t)bitree*t;linkstack*top;top=NIL;dowhile(t!=NIL)top=pushlstack(top,t);t=t,lchild;,if(top!=NIL)top=poplstack(top,printf(%dt,t,data);t=t rchild;,while(top!=NIL)|(t!=NIL);,算法思想,：采用非递归算法实现中序遍历必须引入堆栈。具体实现 步骤为,.,。,例：中序遍历的非递归算法,3,、遍历的非递归算法,2025/8/19 周二,数据结构,57,4,、遍历的非递归算法,例：中序遍历的非递归算法,算法思想,：采用非递归算法实现中序遍历必须引入堆栈。具体实现步骤为,.,。,置栈,s,为空,t,为空？,t,入栈,t=t-lchild,栈为空？,t=s-top,出栈打印,t-datat=t-rchild,结束,N,N,Y,Y,typedef bitree*datatype;typedef struct node datatype data;struct node*next;linkstack;,inorder(t)bitree*t;linkstack*top;top=NULL;do while(t!=NULL)top=pushlstack(top,t);t=t,lchild;,if(top!=NULL)top=poplstack(top,printf(%dt,t,data);t=t rchild;,while(top!=NULL)|(t!=NULL);,算法描述如下：,2025/8/19 周二,数据结构,59,考虑：,1,、遍历的第一个结点和最后一个结点的特征,?,2,、前序序列、中序序列、后序序列，已知任意两者可以确定第三者吗,?,3,、遍历算法中对每个结点进行一次访问操作，访问操作可以是,多种形式及多个操作,。,得到求解许多问题的算法。,2025/8/19 周二,数据结构,60,根结点,最右下叶结点,最左下结点,最右下结点,最左下叶结点,根结点,第一个结点,最后一个结点,前序遍历,中序遍历,后序遍历,考虑：,1,、遍历的第一个结点和最后一个结点的特征,?,2025/8/19 周二,数据结构,61,考虑：,2,、前序序列、中序序列、后序序列，已知任意两者可以确定第三者吗,?,前序、中序,二叉树,后序、中序,前序、后序,二叉树,二叉树,后序,前序,2025/8/19 周二,数据结构,62,考虑：,3,、遍历算法中对每个结点进行一次访问操作，访问操作可以是,多种形式及多个操作,。,得到求解许多问题的算法。,例：打印所有叶子结点,求二叉树中的结点数,2025/8/19 周二,数据结构,63,考虑：,4,、二叉树的遍历只有这六种方法吗,?,NO!,2025/8/19 周二,数据结构,64,例：给定一棵采用二叉链表存储的二叉树，编写按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。,算法思想,：,根据题义可知，先被访问的结点，其孩子结点也将被先访问，因此，可以使用一个指针队列。初始时将根结点指针入队，只要队列不空，则出队一个元素，对其指向结点进行访问，并将其孩子结点指针入队，如此反复，直到队列空为止。,算法描述：,typedef bitree*datatype;typedef struct datatype datamaxsize;int front,rear;sequeue;,lorder(t)bitree*t;,sequeue*sq;/*sq,为循环队列指针,*,/bitree*x setnull(sq);,if(t!=NULL)enqueue(sq,t);,while(!empty(sq)x=dequeue(sq);printf(%dt,x,data);if(x lchild!=NULL)enqueue(sq,x lchild);if(x rchild!=NULL)enqueue(sq,x rchild);,2025/8/19 周二,数据结构,66,作业,:,6.7 6.8 6.12 6.15,2025/8/19 周二,数据结构,67,6.4,线索二叉树,遍历二叉树是以一定规则将二叉树中的结点排成一个线性序列,将一个非线性结构线性化,问题,单单依靠二叉树并不能直接得到结点在任一序列中的前趋和后继,这种信息只有在动态遍历中才能得到,.,所以某次遍历得到的信息,下次再用时,仍要重新遍历,.,考虑,如何保存这种在遍历过程中得到的信息,?,1.,简单的方法,:,在每个结点上增加指针域,fwd,和,bkwd,分别指示结点在任一次序遍历时,得到的前趋和后继。,缺点：将大大降低存储空间的利用率。,2025/8/19 周二,数据结构,68,6.4,线索二叉树,问题,单单依靠二叉树并不能直接得到结点在任一序列中的前趋和后继,这种信息只有在动态遍历中才能得到,.,所以某次遍历得到的信息,下次再用时,仍要重新遍历,.,一、如何保存在遍历过程中得到的信息,?,1.,方法,A:,在每个结点上增加指针域,fwd,和,bkwd,分别指示结点在任一次序遍历时,得到的前趋和后继。,缺点：将大大降低存储空间的利用率。,2025/8/19 周二,数据结构,69,2.,方法,B:,利用已有的指针域存放,:,利用,二叉链表上的,n,1,个,空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，由此得到的二叉链表称为,线索链表,，相应地采用这种存储结构的二叉树称为,线索二叉树,。,线索链表中结点的结构：,lchild ltag data rtag rchild,ltag=0,表示,lchild,为指向结,点左孩子的指针,ltag=1,表示,lchild,为指向结,点前趋的左线索,rtag=0,表示,rchild,为指向结,点右孩子的指针,rtag=1,表示,rchild,为指向结,点后继的右线索,typedef struct node int ltag,rtag;datatype data;struct node*lchild,*rchild;bithptr;bithptr *p;,2025/8/19 周二,数据结构,70,n,个结点的二叉链表中含有,n+1,个空指针域，可以充分利用这些空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，以提高遍历或查找结点在指定次序下的前趋和后继运算的效率。由此得到的二叉链表称为,线索链表,，相应地采用这种存储结构的二叉树称为,线,索二叉树,。,线索链表中结点的结构：,lchild ltag data rtag rchild,ltag=0,表示,lchild,为指向结,点左孩子的指针,ltag=1,表示,lchild,为指向结,点前趋的左线索,rtag=0,表示,rchild,为指向结,点右孩子的指针,rtag=1,表示,rchild,为指向结,点后继的右线索,2.,利用已有的指针域存放,:,2025/8/19 周二,数据结构,71,a,b,c,d,e,中序线索二叉树,d b e a c,NULL,NULL,a,b,c,d,e,0,0,1,0,0,1,1,1,1,1,中序线索链表,线索化,(,建立某次序线索二叉树的步骤,2,，步骤,1,类似于二叉链表的建立过程）,:,将二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。具体地体现在将二叉链表变为线索链表。,2025/8/19 周二,数据结构,72,二、如何对二叉树进行线索化？,1,、,线索化的实质：,是将二叉树的空指针改为指向前趋或后继的线索，而前趋或后继的信息只有在遍历时才能得到，因此线索化的过程即为,在遍历的过程中修改指针,的过程。,2,、,技巧：,1,）,该算法与遍历算法类似，区别仅在于访问根结点时所作的处理不同,2,）,附设一个指针,pre,始终指向刚刚访问过的结点,3,）,指针,p,指向当前访问的结点，,pre,指向它的前趋，,相应地,p,指向的结点为,pre,指向结点的后继。,2025/8/19 周二,数据结构,73,4,、后序遍历建立线索化链表的算法如下：,A:,若结点*,P,有空指针域，则将相应标志置为,1,；,B:,若*,P,有前趋结点*,pre(pre!=Null),则：,（,1,）若结点*,pre,的右线索标志已建立（即,pre,rtag=,1,）,则令,pre,rchild,为指向其后继结点*,p,的右线索。,（,2,）若结点*,p,的左线索标志已建立（即,p,ltag=1),则 令,p,lchild,为指向其前趋*,pre,的左线索。,C:,将,pre,指向刚刚访问过的结点*,p(,即,pre=p),下次访问新结点*,p,时，,*,pre,为其前趋结点。,3,、线索化算法中，访问当前根结点*,P,所做的处理是：,2025/8/19 周二,数据结构,74,将二叉树以某种次序遍历使其变为线索二叉树的过程称为,线索化,，具体地体现在将二叉链表变为线索链表。,接下来的问题是如何对二叉树进行线索化？,线索化的,实质,