数据结构树课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,-,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,-,*,引言,在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。而现实中的许多事物的关系并非如此简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。,所谓非线性结构，是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树结构和图结构是非常重要的非线性结构。,-,引言在前面几章里讨论的数据结构都属于线性结构，线性结构的特点,1,第六章,树和二叉树,本章内容,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,赫夫曼编码,-,第六章 树和二叉树本章内容-,2,6.1,树,树,是,n,个结点的有限集合,(,可以是空集,),，在任一棵非空树中：（,1,）有且仅有一个称为,根,的结点。（,2,）其余结点可分为互不相交的子集，而且这些子集本身又是一棵树，称为根的,子树,。,J,I,A,C,B,D,H,G,F,E,K,L,M,-,6.1 树树是n个结点的有限集合(可以是空集)，在任一棵非空,3,从逻辑结构看：,1,）树中只有,树根没有父结点,；,2,）除根外，其余结点都有且仅一个父结点；,3,）树中的结点，可以有零个或多个,孩子结点,；,4),没有孩子的结点称为,叶子结点,，或终端结点；,5,）除根外的其他结点，都存在唯一一条从根到该结点的路径；,J,I,A,C,B,D,H,G,F,E,K,L,M,-,从逻辑结构看：1）树中只有树根没有父结点；2）除根外，其,4,树的基本术语,树的结点：,包含一个数据元素及若干指向子树的分支；,孩子结点：,结点的子树的根称为该结点的孩子；,父结点：,B,是,A,的孩子，则,A,是,B,的父亲；,兄弟结点：,同一双亲的孩子结点；,堂兄弟结点：,其父结点在同一层上的结点；,祖先结点,:,从根到该结点所经分支上的所有结点；,子孙结点：,以某结点为根的子树中任一结点都称为该结点的子孙；,结点的度,:,结点的孩子数目,J,I,A,C,B,D,H,G,F,E,K,L,M,-,树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；,5,树的基本运算,找树的根结点,求树的高度,找指定结点的父结点,找指定结点的孩子结点,在树中插入、删除一个结点,遍历树,.,J,I,A,C,B,D,H,G,F,E,K,L,M,-,树的基本运算找树的根结点JIACBDHGFEKLM-,6,树的表示,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),(A(,B,(E(k,L),F),C,(G),D,(H(M),I(),J(),(b),-,树的表示JIACBDHGFEKLMGCKLEFBMHJIDA,7,6.2,二叉树,二叉树的定义：二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。,注意：二叉树的子树有严格的左右之分，而树没有。,A,C,B,F,E,D,G,-,6.2 二叉树二叉树的定义：二叉树要么为空，要么由根结点、左,8,二叉树的子树要区分左子树和右子树，即使只有一棵子树也要进行区分。这是二叉树与树的最主要的差别。下面列出了二叉树的,5,种基本形态，,(c),和（,d,）是不同的两棵二叉树。,(a),空二叉树,A,A,B,A,B,A,C,B,(b),只有根的,二叉树,(c),根和左子树,(d),根和右子树,(e),根和左右子树,二叉树的,5,种基本形式,-,二叉树的子树要区分左子树和右子树，即使只有一棵子树也要进行区,9,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 二叉树的性质性质1GKJCFABEIHD-,10,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,-,6.2.2 二叉树的性质 性质3 任何一个二,11,满二叉树和完全二叉树,高度为,3,的满二叉树,高度为,3,的一个完全二叉树,高度为,3,的一个完全二叉树,-,满二叉树和完全二叉树高度为3的满二叉树高度为3的一个完全二叉,12,完全二叉树,高度为,3,的完全二叉树,(a),(b),(c),(d),-,完全二叉树高度为3的完全二叉树(a)(b)(c)(d)-,13,满二叉树和完全二叉树,高度为,3,的满二叉树,高度为,3,的一个完全二叉树,1,2,3,4,5,6,7,1,2,3,4,5,-,满二叉树和完全二叉树高度为3的满二叉树高度为3的一个完全二叉,14,二叉树的性质,(,续,),性质,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 *ro,25,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 *ro,26,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 *ro,27,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 *ro,28,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 *ro,29,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,-,void preorder (BiTNode *ro,30,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,-,D void preorder (BiTNode *r,31,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,-,void preorder (BiTNode *ro,32,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,-,D void preorder (BiTNode *r,33,E,E,void preorder (BiTNode *root),if (root!=NULL),coutdata,；,/,访问根结点,preorder(root-Lchild);,/,先序遍历根的左子树,preorder(root-Rchild);,/,先序遍历根的右子树,/if,/preorder,B,A,C,D,G,F,root,root: B,root: A,先序遍历序列：,A,B,D,root: E,E,-,EE void preorder (BiTNode *,34,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,-,G void preorder (BiTNode *r,35,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,-,E void preorder (BiTNode *r,36,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,-,B void preorder (BiTNode *r,37,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,-,A void preorder (BiTNode *r,38,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,-,C void preorder (BiTNode *r,39,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,-,void preorder (BiTNode *ro,40,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,-,C void preorder (BiTNode *r,41,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,-,F void preorder (BiTNode *r,42,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,-,C void preorder (BiTNode *r,43,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,-,A void preorder (BiTNode *r,44,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,-,void preorder (BiTNode *ro,45,先序遍历过程,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,-,先序遍历过程BACEDGF先序遍历序列：ABDEGCFABD,46,root: A,root: B,root: E,root: G,栈在先序遍历中的作用,B,A,C,E,D,G,F,root,先序遍历序列：,A,B,D,E,G,栈用于保存当前结点的祖先结点,-,root: Aroot: Broot: Eroot: G栈在,47,中序遍历,LDR,：,中序遍历左子树、访问根结点、中序遍历右子树,D,L,R,2,1,3,-,中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树D,48,中序遍历,LDR,：,中序遍历左子树、访问根结点、中序遍历右子树,若二叉树非空,（,1,）中序遍历左子树；,（,2,）访问根结点；,（,3,）中序遍历右子树；,若二叉树为空，结束,基本项（也叫终止项）,若二叉树非空,递归项,（,1,）中序遍历左子树；,（,2,）访问根结点；,（,3,）中序遍历右子树；,D,L,R,-,中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树若,49,void inorder (BiTNode *root),/,中序遍历,root,指向根的二叉树,if (root!=NULL),inorder(root-Lchild);,/,中序遍历根的左子树,coutdata,；,/,访问根结点,inorder(root-Rchild);,/,中序遍历根的右子树,/if,/inorder,中序遍历,Lchild,data,Rchild,-,void inorder (BiTNode *roo,50,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,-,void inorder (BiTNode *roo,51,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 *roo,52,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 *roo,53,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 *roo,54,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 *roo,55,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 *roo,56,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 *roo,57,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 *roo,58,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 *roo,59,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 *roo,60,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 *roo,61,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 *roo,62,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 *roo,63,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 *roo,64,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 *roo,65,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 *roo,66,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 *roo,67,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 *roo,68,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 *roo,69,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,root: NULL,-,void inorder (BiTNode *roo,70,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 *roo,71,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 *roo,72,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 *roo,73,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,-,void inorder (BiTNode *roo,74,B,A,C,E,D,G,F,root,root: A,root: B,root: E,root: G,栈在中序遍历中的作用,中序遍历序列：,D,B,G,栈用于保存当前结点的祖先结点,-,BACEDGFrootroot: Aroot: Broot:,75,后序遍历,LRD,：,后序遍历左子树、后序遍历右子树、访问根结点,D,L,R,3,1,2,E,G,F,C,D,A,B,后序,遍历序列,:BDFGECA,-,后序遍历LRD：后序遍历左子树、后序遍历右子树、访问根结点D,76,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 *roo,77,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 *roo,78,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,-,void inorder (BiTNode *roo,79,用二叉树表示表达式,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,80,用栈对后缀表达式求值,表达式的,后缀表示,: 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,-,用栈对后缀表达式求值表达式的后缀表示: a b c d ,81,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,树根结点,A,入队,层序,遍历序列,:,-,层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队,82,层序遍历,E,G,F,C,D,A,B,队列,队头,A,层序,遍历序列,:,A,出队,先根，后子树；先左子树，后右子树,-,层序遍历EGFCDAB队列队头A层序遍历序列:A出队先根，后,83,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,根结点,B,、,C,入队,A,的子树,层序,遍历序列,: A,-,层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队,84,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,B,B,出队,C,层序,遍历序列,: A,-,层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队,85,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,C,根结点入队,B,的子树,层序,遍历序列,: AB,-,层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队,86,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,C,C,出队,层序,遍历序列,: AB,-,层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队,87,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,根结点入队,C,的子树,层序,遍历序列,: ABC,-,层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队,88,层序遍历,先根，后子树；先左子树，