数据结构-树.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,引言,在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。而现实中的许多事物的关系并非如此简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。,所谓非线性结构，是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树结构和图结构是非常重要的非线性结构。,.,第六章,树和二叉树,本章内容,6.1,树的定义和基本术语,6.2,二叉树,6.2.1,二叉树的定义及基本运算,6.2.2,二叉树的性质,6.2.3,二叉树的存储结构,6.3,遍历二叉树和线索二叉树,6.3.1,遍历二叉树,6.3.2,线索二叉树,6.4,树和森林,6.4.1,树的存储结构,6.4.2,森林与二叉树的转换及遍历,6.6,赫夫曼树及应用,6.6.1,赫夫曼树（最优二叉树）,6.6.2,赫夫曼编码,.,6.1,树,树,是,n,个结点的有限集合,(,可以是空集,),，在任一棵非空树中：（,1,）有且仅有一个称为,根,的结点。（2,）其余结点可分为互不相交的子集，而且这些子集本身又是一棵树，称为根的,子树,。,J,I,A,C,B,D,H,G,F,E,K,L,M,.,从逻辑结构看：,1,）树中只有,树根没有父结点,；,2,）除根外，其余结点都有且仅一个父结点；,3,）树中的结点，可以有零个或多个,孩子结点,；,4),没有孩子的结点称为,叶子结点,，或终端结点；,5,）除根外的其他结点，都存在唯一一条从根到该结点的路径；,J,I,A,C,B,D,H,G,F,E,K,L,M,.,树的基本术语,树的结点：,包含一个数据元素及若干指向子树的分支；,孩子结点：,结点的子树的根称为该结点的孩子；,父结点：,B,是,A,的孩子，则A,是,B,的父亲；,兄弟结点：,同一双亲的孩子结点；,堂兄弟结点：,其父结点在同一层上的结点；,祖先结点,:,从根到该结点所经分支上的所有结点；,子孙结点：,以某结点为根的子树中任一结点都称为该结点的子孙；,结点的度,:,结点的孩子数目,J,I,A,C,B,D,H,G,F,E,K,L,M,.,树的基本运算,找树的根结点,求树的高度,找指定结点的父结点,找指定结点的孩子结点,在树中插入、删除一个结点,遍历树,.,J,I,A,C,B,D,H,G,F,E,K,L,M,.,树的表示,J,I,A,C,B,D,H,G,F,E,K,L,M,G,C,K,L,E,F,B,M,H,J,I,D,A,(a),(AB,(E(k,L),F),C,(G),D,(H(M),I(),J(),(b),.,6.2,二叉树,二叉树的定义：二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。,注意：二叉树的子树有严格的左右之分，而树没有。,A,C,B,F,E,D,G,.,二叉树的子树要区分左子树和右子树，即使只有一棵子树也要进行区分。这是二叉树与树的最主要的差别。下面列出了二叉树的,5,种基本形态，,(c),和（,d,）是不同的两棵二叉树。,(a),空二叉树,A,A,B,A,B,A,C,B,(b),只有根的,二叉树,(c),根和左子树,(d),根和右子树,(e),根和左右子树,二叉树的,5,种基本形式,.,6.2.2,二叉树的性质,性质,1,在二叉树的第,i,层上至多有,2,i-1,个结点,性质,2,深度为,k,的二叉树至多有,2,k,-1,个结点,性质,3,任何一个二叉树中度为,2,的结点数目,(n,2,),比度为,0,的结点数目,(n,0,),少,1,，即,n,2,n,0,-1,。,G,K,J,C,F,A,B,E,I,H,D,.,6.2.2,二叉树的性质,性质,3,任何一个二叉树中度为,2,的结点数目,(n,2,),比度为,0,的结点数目,(n,0,),少,1,，即,n,2,n,0,-1,。,证明：设二叉树上叶结点数为,n,0,，单分支结点数为,n,1,，双分支结点数为,n,2,，则总结点数,=n,0,+n,1,+n,2,。,在一棵二叉树中，所有结点的分支数,(,即度数,),应等于单分支结点数加上双分支结点数的,2,倍，即总的分支数,=n,1,+2n,2,。,由于二叉树中除根结点以外，每个结点都有惟一的一个分支指向它，因此二叉树中：总的分支数,=,总结点数,-1,。,由上述三个等式可得：,n,1,+2n,2,=n,0,+n,1,+n,2,-1,即：,n,0,=n,2,+1,.,满二叉树和完全二叉树,高度为,3,的满二叉树,高度为,3,的一个完全二叉树,高度为,3,的一个完全二叉树,.,完全二叉树,高度为,3,的完全二叉树,(a),(b),(c),(d),.,满二叉树和完全二叉树,高度为,3,的满二叉树,高度为,3,的一个完全二叉树,1,2,3,4,5,6,7,1,2,3,4,5,.,二叉树的性质,(,续,),性质,4,一个有,n,个结点的完全二叉树的高度,H,log(n)+1,。,证明：,设具有,n,个结点的完全二叉树的深度为,h,，则根据性质,3,：深度为,h,的二叉树至多有,2,h,-1,个结点，因此，,n=2,h-1,综上，,2,h-1,=n 2,h,，或,h-1=log,2,n Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,先序遍历,Lchild,data,Rchild,E,C,D,A,B,A,B,C,E,D,root,.,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,先序遍历序列：,root:A,.,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,先序遍历序列：,A,root:A,.,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,.,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,.,void preorder(BiTNode*root),if(,root!=NULL,),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,root:NULL,.,D,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：A,B,root:D,D,.,void preorder(BiTNode*root),if(,root!=NULL,),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,root:NULL,.,D,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,.,E,E,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,D,G,F,rootroot:B,root:A,先序遍历序列：,A,B,D,root:E,E,.,G,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,root:E,E,G,root:G,.,E,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,root:E,E,G,.,B,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,E,G,.,A,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,.,C,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,.,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,root:NULL,.,C,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,.,F,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,root:F,F,.,C,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,F,.,A,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,C,F,.,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,E,D,G,F,root,先序遍历序列：,A,B,D,E,G,C,F,.,先序遍历过程,B,A,C,E,D,G,F,先序遍历序列：,A,B,D,E,G,C,F,A,B,D,E,G,C,F,递归调用,返回,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,.,root:A,root:B,root:E,root:G,栈在先序遍历中的作用,B,A,C,E,D,G,F,root,先序遍历序列：,A,B,D,E,G,栈用于保存当前结点的祖先结点,.,中序遍历,LDR,：,中序遍历左子树、访问根结点、中序遍历右子树,D,L,R,2,1,3,.,中序遍历,LDR,：,中序遍历左子树、访问根结点、中序遍历右子树,若二叉树非空,（,1,）中序遍历左子树；,（,2,）访问根结点；,（,3,）中序遍历右子树；,若二叉树为空，结束,基本项（也叫终止项）,若二叉树非空,递归项,（,1,）中序遍历左子树；,（,2,）访问根结点；,（,3,）中序遍历右子树；,D,L,R,.,void inorder(BiTNode*root),/,中序遍历,root,指向根的二叉树,if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,中序遍历,Lchild,data,Rchild,.,void inorder(BiTNoderoot),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,root:NULL,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,D,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,D,root:NULL,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,D,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,root:G,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,root:G,root:NULL,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,root:G,G,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,G,E,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,G,E,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,root:NULL,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,root:F,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,EA,root:C,C,root:F,root:NULL,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,root:F,F,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,F,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,C,F,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,D,B,G,E,A,C,F,.,B,A,C,E,D,G,F,root,root:A,root:B,root:E,root:G,栈在中序遍历中的作用,中序遍历序列：,D,B,G,栈用于保存当前结点的祖先结点,后序遍历,LRD,：,后序遍历左子树、后序遍历右子树、访问根结点,D,L,R,3,1,2,E,G,F,C,D,A,B,后序,遍历序列,:BDFGECA,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,void preorder(BiTNode*root),if(root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,void postorder(BiTNode*root),if(root!=NULL),postorder(root-Lchild);/,后序遍历根的左子树,postorder(root-Rchild);/,后序遍历根的右子树,coutdata,；,/,访问根结点,/if,/postorder,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,root:A,root:B,root:E,E,中序遍历序列：,D,B,G,void InOrder(BiTNode*root),InitStack(S);Push(S,root);,/,根指针进栈,while(!StackEmpty(S),while(GetTop(S,p)&p),Push(S,p-Lchild);,/,向左走到头,Pop(S,p);/,空指针退栈,if(!StackEmpty(S),Pop(S,p);cout data;/访问结点,Push(S,p-Rchild);/,向右,/if,/while,/InOrder,.,void inorder(BiTNode*root),if(root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);/,中序遍历根的右子树,/if,/inorder,B,A,C,E,D,G,F,root,root:A,root:B,root:E,E,中序遍历序列：,D,B,G,void InOrder(BiTNode*root),InitStack(S);p=root;,/,根指针进栈,while(p|!StackEmpty(S),if(p),Push(S,p);p=p-Lchild;,else,/,根指针退栈，访问根结点，遍历右子树,Pop(S,p);cout data;,p=p-Rchild;,/if-else,/while,/InOrder,.,用二叉树表示表达式,a+b*(c,d),e/f,f,/,e,-,+,*,a,-,b,d,c,先序,遍历序列,:+a*b c d/e f,中序,遍历序列,:a+b*c d e/f,后序,遍历序列,:a b c d *+e f /,表达式的前缀、中缀和后缀表示,.,用栈对后缀表达式求值,表达式的,后缀表示,:a b c d *e f /,b,a,c,d,b,a,t1,t2,a,t1=c d,t2=b*t1,t3=a+t2,t3,e,t3,f,t4=e/f,t4,t3,t5,t5=t3 t4,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,树根结点,A,入队,层序,遍历序列,:,.,层序遍历,E,G,F,C,D,A,B,队列,队头,A,层序,遍历序列,:,A,出队,先根，后子树；先左子树，后右子树,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,根结点,B,、,C,入队,A,的子树,层序,遍历序列,:A,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,B,B,出队,C,层序,遍历序列,:A,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,C,根结点入队,B,的子树,层序,遍历序列,:AB,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,C,C,出队,层序,遍历序列,:AB,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,根结点入队,C,的子树,层序,遍历序列,:ABC,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,D,E,D,出队,层序,遍历序列,:ABC,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,E,根结点入队,D,的子树,层序,遍历序列,:ABCD,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,E,E,出队,层序,遍历序列,:ABCD,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,根结点,F,、,G,入队,E,的子树,层序,遍历序列,:ABCDE,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,F,G,F,出队,层序,遍历序列,:ABCDE,.层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,G,根结点入队,F,的子树,层序,遍历序列,:ABCDEF,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,G,G,出队,层序,遍历序列,:ABCDEF,.,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,层序,遍历序列,:ABCDEFG,利用队列实现二叉树的层序遍历：,构造一个空队列；,树根结点入队列；,while,（队列不空）,队头元素出队列；,访问结点；,刚出队的结点的左孩子、右孩子结点先后入队列；,.,6.3.2,线索二叉树,Ltag=,Lchild,data,Rchild,Lchild,data,Rchild,Rtag,Ltag,0 Lchild,指向左子树根结点,1 Lchild,指向前驱结点,Rtag=,0 Rchild,指向右子树根结点,1 Rchild,指向后继结点,typedef enum PointerTag Link=0,Thread=1;,typedef struct BiThrNode,ElemType data;,struct BiThrNode*Lchild,*Rchild;,PointerTag Ltag,Rtag;,*BiThrTree;,B,A,C,E,D,G,F,root,.,B,A,C,E,D