《数据结构第五章精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构第五章精品文稿.ppt（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构第五章第1页，本讲稿共67页1.树的基本概念树的基本概念2.二叉树二叉树3.遍历二叉树遍历二叉树4.线索二叉树线索二叉树5.树的应用树的应用特点：非线性结构，一个直接前驱，但可能有多个直接后特点：非线性结构，一个直接前驱，但可能有多个直接后继。继。（一对多或（一对多或1:n1:n）二叉树的定义、性质和存储结构二叉树的运算第2页，本讲稿共67页l树适于反应层次关系的数据对象的研究。层次树适于反应层次关系的数据对象的研究。层次化的数据之间可能有化的数据之间可能有:祖先祖先后代、上级后代、上级下级、下级、整体整体部分部分等其它类似的关系。等其它类似的关系。学院法法学学院院工工商商学学院院信信
2、息息学学院院金金融融学学院院人人文文学学院院会会计计学学院院财财税税学学院院计计算算机机系系信信息息系系统统计计系系图5.1.1 一棵学院信息的树第3页，本讲稿共67页5.1.1 5.1.1 树的定义树的定义 由一个或多个由一个或多个(n0)(n0)结点组成的有限集结点组成的有限集合合T T，有且仅有一个结点称为根（有且仅有一个结点称为根（rootroot）当当n1n1时，其余的结点分为时，其余的结点分为m(m0)m(m0)个互个互不相交的有限集合不相交的有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵树，被称作这个根每个集合本身又是棵树，被称作这个根的子树的子树 。树的定义具有递归
3、性，即树的定义具有递归性，即“树中还有树树中还有树”。第4页，本讲稿共67页一棵树至少包含一个树结点，不存在不一棵树至少包含一个树结点，不存在不含树结点的树；含树结点的树；树中结点存在着层次关系，但同一层上树中结点存在着层次关系，但同一层上的树结点之间是无序的。的树结点之间是无序的。一棵树的每个结点都是某个子树的根。一棵树的每个结点都是某个子树的根。第5页，本讲稿共67页若干术语若干术语（也称父亲）（也称父亲）即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称
4、兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJFLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集合棵不相交的树的集合(例例如删除如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互
5、换位置。结点各子树可互换位置。第6页，本讲稿共67页即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJFLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：右上图
6、中的结点数问：右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4（有几个直接后继就是几度，亦称（有几个直接后继就是几度，亦称“次数次数”）第7页，本讲稿共67页ABCDEFGHIJKLM结点A的度：?结点B的度：?结点M的度：?叶子：?结点A的孩子：?结点B的孩子：?结点I的双亲：?结点L的双亲：?结点B，C，D为?结点K，L为?树的度：?结点A的层次：?结点M的层次：?树的深度：?结点F，G为?结点A是结点F，G的?320B，C，DE，F314K，L，F，G，M，I，JDE兄弟兄弟4堂兄弟祖先第8页，本讲稿共67页5.2.1 5.2.1 二叉树的定义二叉树的定义l定
7、义：二叉树是定义：二叉树是n(nn(n 0)0)个结点的有限集，它或为空树个结点的有限集，它或为空树(n=0)(n=0)，或，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成构成l特点特点每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2 2的结点的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的子树有左、右之分，且其次序不能任意颠倒l基本形态基本形态A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空第9页，本讲稿共67页2.2.二叉树的定义与树的定义的区
8、别二叉树的定义与树的定义的区别1.1.二叉树存在着空树；但树不能为空。二叉树存在着空树；但树不能为空。2.2.二叉树中的每一个结点只可能有二叉树中的每一个结点只可能有0 0个，个，1 1个或个或2 2个孩个孩子，也就是说，二叉树不存在度大于子，也就是说，二叉树不存在度大于2 2的结点；而的结点；而树中的每个结点可以有多个子树。树中的每个结点可以有多个子树。3.3.二叉树的子树有左右之分，两者不能颠倒；但树的二叉树的子树有左右之分，两者不能颠倒；但树的子树一般是无序的。子树一般是无序的。l除以上区别外，上一节引入树的有关术语对于二叉除以上区别外，上一节引入树的有关术语对于二叉树也适用。树也适用。
9、第10页，本讲稿共67页3.3.3.3.满二叉树的定义满二叉树的定义 若若二二叉叉树树中中所所有有分分枝枝结结点点的的度度数数都都为为2 2，且且叶叶子子结结点点都都在在同同一层上，则称这类二叉树为满二叉树。一层上，则称这类二叉树为满二叉树。5.5.完全二叉树的定义完全二叉树的定义 若二叉树中所有分枝结点的度数要就为若二叉树中所有分枝结点的度数要就为2 2，要就为，要就为0 0，称这类，称这类二叉树为完全二叉树。二叉树为完全二叉树。4.4.顺序二叉树的定义顺序二叉树的定义:对对满满二二叉叉树树从从上上至至下下，从从左左至至右右地地从从1 1开开始始编编号号，结结果果是是每每个个结结点都可以与满
10、二叉树中编号为点都可以与满二叉树中编号为1 1至至n n的结点一一对应的结点一一对应6.6.退化二叉树的定义退化二叉树的定义:如果一棵非空的二叉树只有一个叶子，且其余结点均只有一个孩如果一棵非空的二叉树只有一个叶子，且其余结点均只有一个孩子子 第11页，本讲稿共67页ABCDEFG图5.2.2 一棵满二叉树123456789101112图5.2.4 一棵顺序二叉树图5.2.5 一棵非顺序二叉树12345678912图5.2.8 退化的二叉树AIDB12472852(a)(b)第12页，本讲稿共67页5.2.2 5.2.2 二叉二叉树树的性的性质质 性质性质1:1:在二叉树的第在二叉树的第 i
11、i 层上最多有层上最多有2 2i-1i-1个结点（个结点（i1i1）。）。用归纳法证明它。用归纳法证明它。当当i=1i=1时，时，2 21-11-1=1=1，这时只有一个根结点，显然结论是正确的。，这时只有一个根结点，显然结论是正确的。假假设设，对对于于所所有有的的j j（1ji1j0n0）个元素的二叉树的边数为）个元素的二叉树的边数为n-1n-1。l证明：二叉树中每个元素（除根结点外）有且仅有一证明：二叉树中每个元素（除根结点外）有且仅有一个双亲结点。而孩子结点与双亲结点之间有且仅有一个双亲结点。而孩子结点与双亲结点之间有且仅有一条边，因此包含条边，因此包含n n个元素的二叉树的边数是个元素
12、的二叉树的边数是n-1n-1。第15页，本讲稿共67页5.2.2 5.2.2 二叉二叉树树的性的性质质 1.1.性质性质1:1:在二叉树的第在二叉树的第 i i 层上最多有层上最多有2 2i-1i-1个结点（个结点（i1i1）。）。l性质性质2:2:深度为深度为h h的二叉树至多有的二叉树至多有2 2h h-1-1个结点。个结点。l性质性质3:3:包括包括n n（n0n0）个元素的二叉树的边数为）个元素的二叉树的边数为n-1n-1。l性质性质4:4:对于任何一棵二叉树，若其终端结点数为对于任何一棵二叉树，若其终端结点数为n n0 0，其度为其度为2 2的结点数为的结点数为n n2 2，则有：，
13、则有：n n0 0=n=n2 2+1+1。5.5.性质性质5:5:若一棵满二叉树有若一棵满二叉树有n n个结点个结点,则深度则深度h h第16页，本讲稿共67页性质性质6 6一一棵棵有有n n个个结结点点的的顺顺序序二二叉叉树树，如如从从左左至至右右、从从上上至至下下的的，对对每每个个结结点点从从1 1开开始始编编号号，对对于于其其中中任任意意编编号号为为i i的结点（的结点（1in1in）有：）有：(1)(1)若若i i 1,1,则则i i的的父父亲亲是是 i/2i/2；若若i=1i=1，则则i i是是根根结结点点，无父亲。无父亲。(2)(2)若若2in2in，则则i i的的左左孩孩子子是是
14、2i2i；若若2in2in，则则i i无无左左孩孩子。子。(3)(3)若若2i+1n2i+1n，则则i i的的右右孩孩子子是是2i+12i+1；若若2i+1n2i+1n，则则i i无右孩子。无右孩子。第17页，本讲稿共67页123114589126710图5.2.9 顺序二叉树父子关系152178525777ii+12i2i+12i+2i/2第18页，本讲稿共67页3.深度为9的二叉树中至少有 个结点。)9 )8 )912.深度为的二叉树的结点总数，最多为 个。)k-1 )log2k )k )k1.树中各结点的度的最大值称为树的 。)高度 )层次 )深度 )度DCC课堂练习：第19页，本讲稿共
15、67页 4 4：具有：具有3 3个结点的二叉树可能有几种不个结点的二叉树可能有几种不同形态？同形态？第20页，本讲稿共67页二叉二叉树树的抽象数据的抽象数据类类型型 Dset：有限元素集合。有限元素集合。Rset：如果不空，被分为根结点、左子树和如果不空，被分为根结点、左子树和右子树；每个子树仍然是一个二叉树。右子树；每个子树仍然是一个二叉树。OPSet：PreOrder(*BT)二叉树的前序遍历递归算法二叉树的前序遍历递归算法PreOrderN(*BT)二叉树的前序遍历非递归算法二叉树的前序遍历非递归算法InOrder(*BT)二叉树的中序遍历递归算法二叉树的中序遍历递归算法InOrderN
16、(*BT)二叉树的中序遍历非递归算法二叉树的中序遍历非递归算法第21页，本讲稿共67页二叉二叉树树的抽象数据的抽象数据类类型型 PostOrder(*BT)二叉树的后序遍历递归算法二叉树的后序遍历递归算法PostOrderN(*BT)二叉树的后序遍历非递归算法二叉树的后序遍历非递归算法LevelOrderTL(*BT)左至右，上至下层次遍历左至右，上至下层次遍历LevelOrderTR(*BT)右至左，上至下层次遍历右至左，上至下层次遍历MakeNode(&x)构造结点构造结点MakeBinaryTree(*root,*left,*right)联接三个结点为联接三个结点为二叉树二叉树Binar
17、yHeight(*BT)求二叉树的高度求二叉树的高度BinaryDelete(*BT)二叉树的删除算法二叉树的删除算法第22页，本讲稿共67页5.3.1 5.3.1 5.3.1 5.3.1 二叉树的存储结构二叉树的存储结构二叉树的存储结构二叉树的存储结构一、顺序存储结构一、顺序存储结构按按二二叉叉树树的的结结点点“自自上上而而下下、从从左左至至右右”编编号号，用用一一组组连连续续的的存存储储单单元元存储。存储。A AB BC CD DE EF FG GH HI I012345678问：顺序存储后能否复原成唯一对应的二叉树形状？问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全答：若是完
18、全/满二叉树则可以做到唯一复原。满二叉树则可以做到唯一复原。而且有规律：下标值为而且有规律：下标值为i i的双亲，其左孩子的下标值必的双亲，其左孩子的下标值必为为2(i+1)-12(i+1)-1，其右孩子的下标值必为，其右孩子的下标值必为2(i2(i1)1)例如，对应例如，对应2C2C的两个孩子必为的两个孩子必为55和和6,6,即即B B的左孩的左孩子必是子必是F,F,右孩子必为右孩子必为G G。A AB BC CGGE EI ID DHHF F012第23页，本讲稿共67页讨论：讨论：不是完全二叉树怎么办？不是完全二叉树怎么办？答：答：一律转为完全二叉树！一律转为完全二叉树！方法很简单，将各
19、层空缺处统统补上方法很简单，将各层空缺处统统补上“虚结点虚结点”，其内容为空。，其内容为空。A AB B C C D D E E012345678.15ABECD缺点：缺点：浪费空间；浪费空间；插入、删除不便插入、删除不便 第24页，本讲稿共67页二、链式存储结构二、链式存储结构用二叉链表即可方便表用二叉链表即可方便表用二叉链表即可方便表用二叉链表即可方便表示。示。示。示。datadataleft_childright_childdataleft_childright_childtypedef struct BinaryTreeNodeBinaryTreeNodeEType data;Bina
20、ryTreeNode*LChild;BinaryTreeNode*RChild;BinaryTreeNode；一般从根结点开始存储。一般从根结点开始存储。（相应地，访问树中结点时也只（相应地，访问树中结点时也只能从根开始）能从根开始）注：如果需要倒查某结点的双亲，注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉趋）指针，将二叉链表变成三叉链表。链表。第25页，本讲稿共67页优点：优点：不浪费空间；不浪费空间；插入、删除方便插入、删除方便 ABCDEFG AB C D E F G第26页，本讲稿共67页问问：含含有有n n个个结结
21、点点的的二二叉叉树树中中，共共有有链链接接域域有有2n2n个个，空空闲的（不用的）链接域有闲的（不用的）链接域有n+1n+1个（为什么？）个（为什么？）证明：根据性质证明：根据性质4 4：n n0 0=n=n2 2+1,+1,有叶子结点空闲的链接域为有叶子结点空闲的链接域为2n2n2 2+2+2度为度为1 1的结点空闲的链接域为的结点空闲的链接域为n-nn-n0 0-n-n2 2=n-2n=n-2n2 2-1,-1,则总的空闲链接域为则总的空闲链接域为2n2n0 0+n+n1 1=n+1=n+1第27页，本讲稿共67页5.4.4 5.4.4 二叉树的其它操作二叉树的其它操作 l构造一棵二叉树构
22、造一棵二叉树 的结点的结点 BinaryTreeNode *MakeNode(EType&x)/构造结点构造结点BinaryTreeNode*ptr;Ptr=new BinaryTreeNode;if (ptr)return NULL;ptr-data=x;ptr-LChild=NULL;ptr-RChild=NULL;return ptr;x=A;BinaryTreeNode*Aptr=MakeNode(&x);第28页，本讲稿共67页2)2)2)2)构造一棵二叉子构造一棵二叉子构造一棵二叉子构造一棵二叉子树树树树（或二叉（或二叉（或二叉（或二叉树树树树）void MakeBinaryTre
23、e(BinaryTreeNode*root,BinaryTreeNode*left,BinaryTreeNode*right)/联接联接root，left,right所指的结点指针为二叉树所指的结点指针为二叉树root-LChild=left;root-RChild=right;第29页，本讲稿共67页ABCDEFG图5.4.4 一棵二叉树MakeBinaryTree(E,G,NULL);MakeBinaryTree(B,D,E);MakeBinaryTree(C,NULL,F);MakeBinaryTree(A,B,C);用MakeBinaryTree构造下图给出的树。第30页，本讲稿共67
24、页5.4 5.4 二叉树链式存储结构下的操作二叉树链式存储结构下的操作5.4.1 5.4.1 遍历二叉树遍历二叉树遍历定义遍历定义遍历用途遍历用途遍历方法遍历方法指按某条搜索路线遍访每个结点且不重复指按某条搜索路线遍访每个结点且不重复（又称周游）。（又称周游）。它是树结构插入、删除、修改、查找和排它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础序运算的前提，是二叉树一切运算的基础和核心。和核心。对每个结点的查看通常都是对每个结点的查看通常都是“先左后右先左后右”。Traversing Binary Tree第31页，本讲稿共67页遍历规则遍历规则l二叉树由根、左子树、右
25、子树构成，定义为二叉树由根、左子树、右子树构成，定义为D、L、R以根结点为参照系注：注：“前、中、后前、中、后”的意思是指访问的结点的意思是指访问的结点D D是先于子树出现还是是先于子树出现还是后于子树出现。后于子树出现。v D、L、R的组合定义了六种可能的遍历方案：的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLDv 若限定若限定先左后右先左后右，则有三种实现方案：，则有三种实现方案：DLR LDR LRD前前序遍历序遍历 中中序遍历序遍历 后后序遍历序遍历 第32页，本讲稿共67页ADBCD L RAD L RD L RBDCD L R前序遍历序列：前序遍历序列
26、：A B D C前序遍历:第33页，本讲稿共67页ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C中序遍历:第34页，本讲稿共67页ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列：D B C A后序遍历:B第35页，本讲稿共67页+*A*/EDCB先序遍历结果先序遍历结果+*/A B C D E前缀表示法前缀表示法中序遍历结果中序遍历结果A/B*C*D+E中缀表示法中缀表示法后序遍历结果后序遍历结果A B/C*D*E+后缀表示法后缀表示法例例1：用二叉树表示算术表达式：用二叉树表示算术表达式：用二叉树表示算术
27、表达式：用二叉树表示算术表达式先序遍历结果中序遍历结果后序遍历结果层次遍历结果第36页，本讲稿共67页ABCDEFGA AB BC CGGE EI ID DHHF F例例1 1先序遍历结果先序遍历结果A B D H I E C F G中序遍历结果中序遍历结果H D I B E A F C G后序遍历结果后序遍历结果H I D E B F G C A例1例2例例2 2先序先序遍历遍历结果结果A B C D E G F中序遍历结果中序遍历结果C B E G D F A后序遍历结果后序遍历结果C G E F D B A第37页，本讲稿共67页1.1.构构造造二二叉叉树树：一一步步是是先先构构造造结结
28、点点，第第二二步步是是将将产产生的结点联接在一起。生的结点联接在一起。2.2.计计算算二二叉叉树树的的深深度度：比比较较左左子子树树和和右右子子树树的的高度，取其最大值高度，取其最大值 3.3.删删除除二二叉叉树树 ：从从叶叶子子开开始始，先先删删除除左左子子树树，再删除右子树，最后删除根结点。再删除右子树，最后删除根结点。4.4.统统计计二二叉叉树树结结点点数数 ：在在遍遍历历时时，每每次次访访问问一一个个结点时，就在统计个数的计数器中加一。结点时，就在统计个数的计数器中加一。5.5.插入结点或删除结点插入结点或删除结点 ：二叉树的操作第38页，本讲稿共67页5.4.2 5.4.2 二叉二叉
29、树树的前序、中序、后序遍的前序、中序、后序遍历历操操作作 对对于于二二叉叉树树的的遍遍历历，将将用用递递归归算算法法和和非非递递归归算法给予讨论。算法给予讨论。l递递归归算算法法简简单单明明晰晰，但但由由于于递递归归本本身身的的嵌嵌套套执执行行过程，会影响到算法执行的效率；过程，会影响到算法执行的效率；l非非递递归归算算法法相相对对较较复复杂杂，实实现现中中运运用用栈栈结结构构类类型，算法的效率相对效高，型，算法的效率相对效高，第39页，本讲稿共67页1 1）前序遍前序遍历历的的递归递归算法算法voidPreOrder(BinaryTreeNode*BT)/二叉树的前序遍历递归算法二叉树的前序
30、遍历递归算法if(BT)coutdataLChild);PreOrder(BT-RChild);第40页，本讲稿共67页主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C第41页，本讲稿共67页前序遍历的非递归算法前序遍历的非递归算法DLR#define MaxStack
31、Size 100typedef structBinaryTreeNode*element;inttop;intMaxSize;Stack；Stack S;第42页，本讲稿共67页非递归前序算法遍历思想：非递归前序算法遍历思想：lA A。结点指针非空时或堆栈非空时。结点指针非空时或堆栈非空时:如果结点指针非空时，首先访问如果结点指针非空时，首先访问“根根”结点；结点；结点指针为空时，转结点指针为空时，转C C步骤；步骤；lB B。然然后后将将访访问问过过的的结结点点指指针针（一一个个“根根”的的指指针针）进进栈栈，再再将将指指针针指指向向访访问问过过的的结结点点的的左左子子树树的的根根，转转A
32、A步步骤；骤；lC C。堆堆栈栈非非空空时时，退退栈栈，指指针针指指向向退退栈栈结结点点的的右右子子树树结结点点，转转A A。第43页，本讲稿共67页 ABCDE图5.4.3 二叉树表表5.4.1 5.4.1 二叉树前序遍历非递归过程二叉树前序遍历非递归过程步 骤访问结点栈S内容P的指向初 态A1AAB2BABC3C ABC空(C的左孩子)4AB空(C的右孩子)5 AD6D AD空(D的左孩子)7 AE8E AE空(E的左孩子)9 A空(E的右孩子)10 空空(A的右孩子)P第44页，本讲稿共67页二叉树的前序遍历非递归算法二叉树的前序遍历非递归算法while (p|!IsEmpty(&S)i
33、f(p)cout data LChild;/指针指向访问过的指针指向访问过的“根根”结结点左子树点左子树.else/左子树为空时，利用堆栈回朔左子树为空时，利用堆栈回朔第45页，本讲稿共67页二叉树的前序遍历非递归算法二叉树的前序遍历非递归算法if(!IsEmpty(&S)Pop(&S,p);/从堆栈中弹出回朔结点指针（该从堆栈中弹出回朔结点指针（该结点已访问过）结点已访问过）p=p-RChild;/指针指向回朔结点的右子树指针指向回朔结点的右子树 第46页，本讲稿共67页2.2.中序遍历的递归算法中序遍历的递归算法 LDR void InOrder(BinaryTreeNode*BT)/二叉
34、树的中序遍历递归算法二叉树的中序遍历递归算法if(BT)InOrder(BT-LChild);cout data RChild);第47页，本讲稿共67页中序遍历的非递归算法中序遍历的非递归算法 1.1.首先结点指针（一个首先结点指针（一个“根根”的指针）进栈，的指针）进栈，然后将结点指针指向进栈结点的左子树的根，然后将结点指针指向进栈结点的左子树的根，重复重复A A步，直到指针指向空。（最后一个进栈的步，直到指针指向空。（最后一个进栈的是最左子树）；是最左子树）；2.2.堆栈非空时，从堆栈中退出一个指向子树的堆栈非空时，从堆栈中退出一个指向子树的“根根”的指针，访问该指针所指结点，转到的指针
35、，访问该指针所指结点，转到C C步骤。步骤。堆栈为空时，结束算法；堆栈为空时，结束算法；3.3.然后将指针指向访问过结点的右子树的根，重新然后将指针指向访问过结点的右子树的根，重新从从A A步骤做起。步骤做起。第48页，本讲稿共67页表表5.4.2 5.4.2 二叉树中序遍历非递归过程二叉树中序遍历非递归过程步 骤访问结点栈S内容P的指向初 态A1AB2ABC3ABC空(C的左孩子)4CAB空(C的右孩子)5BAD6AD空(D的左孩子)7DAE8AE空(E的左孩子)9EA空(E的右孩子)10A空空(A的右孩子)ABCDE图5.4.3 二叉树第49页，本讲稿共67页dowhile(p)/找最左子
36、树找最左子树Push(S,p);/“根根”结点（未访问）指针进栈，以结点（未访问）指针进栈，以后回朔时再退栈后回朔时再退栈p=p-LChild;/指针指向该指针指向该“根根”结点左子树结点左子树if(!IsEmpty(S)/左子树为空时，利用堆栈左子树为空时，利用堆栈回朔回朔Pop(S,p);/从堆栈中弹出回朔结点指针（该结点从堆栈中弹出回朔结点指针（该结点未访问过）未访问过）cout data RChild;/指针指向回朔结点的右子树指针指向回朔结点的右子树 while（p）|!IsEmpty(S)）;第50页，本讲稿共67页3.3.二叉二叉树树的后序遍的后序遍历历 LRDvoid Post
37、Order(BinaryTreeNode*BT)/二叉树的中序遍历递归算法二叉树的中序遍历递归算法if(BT)PostOrder(BT-LChild);PostOrder(BT-RChild);Cout data LChild;/指针指向该指针指向该“根根”结点左子树结点左子树else第56页，本讲稿共67页if(!IsEmpty(S)/左子树为空时，利用堆栈回朔左子树为空时，利用堆栈回朔Pop(S,temp);/从堆栈中弹出回朔结点指针及标志从堆栈中弹出回朔结点指针及标志（该结点未访问过）（该结点未访问过）p=temp.prt;/p指向退栈结点指向退栈结点if(temp.B)cout dat
38、a RChild;/指针指向指针指向“根根”的右子树的右子树 第57页，本讲稿共67页对遍历的分析：对遍历的分析：1.从前面的三种遍历算法可以知道：从前面的三种遍历算法可以知道：从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的法的访问路径是相同的，只是访问结点的时机不同。访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。AFEDCBG第第1次次经过时访问，是经过时访问，是先序先序遍历遍历第第2次次经过时访问，是经过时访问，是中序中序遍历遍历
39、第第3次次经过时访问，是经过时访问，是后序后序遍历遍历2.2.二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率时间效率:O(n)O(n)O(n)O(n)/每个结点只访问一次每个结点只访问一次空间效率空间效率:O(n)O(n)O(n)O(n)/栈占用的最大辅助空间栈占用的最大辅助空间精确值：树深为k的递归遍历需要k+1个辅助单元第58页，本讲稿共67页5.4.3 5.4.3 二叉树的层次遍历操作二叉树的层次遍历操作 l介绍从上至下的两种遍历过程介绍从上至下的两种遍历过程 l层次遍历时，将使用一个队列作为辅助，来完成遍历层次遍历时，将使用一个队列作为辅助，来完成遍历过程过程ty
40、pedef structBinaryTreeNode*element;intfront;intrear;intMaxSize;Queue；l如如果果一一个个结结点点被被访访问问后后，则则其其先先准准备备访访问问的的孩孩子子就就应应该该先先进进队，后访问的孩子后进队。队，后访问的孩子后进队。第59页，本讲稿共67页1.1.从上至下，从上至下，从左至右（从左至右（Top_LeftTop_Left）ABCDEFG图5.4.4 一棵二叉树第60页，本讲稿共67页while(p)cout data LChild)Enqueue(&Q,p-LChild);/左子树进队左子树进队if(p-RChild)En
41、queue(&Q,p-RChild);/右子树进队右子树进队if(!DeQueue(&Q,p)return;/出出队队返返回回状状码码ERROR时时结结束束（队空）（队空）第61页，本讲稿共67页2.2.从上至下，从右至左（从上至下，从右至左（Top_RightTop_Right）while(p)cout data RChild)Enqueue(&Q,p-RChild);/右子树进队右子树进队if(p-LChild)Enqueue(&Q,p-LChild);/左子树进队左子树进队if(!DeQueue(&Q,p)return;/出队返回状码出队返回状码ERROR时结束（队空）时结束（队空）第6
42、2页，本讲稿共67页程序设计程序设计l1.1.二叉树前序非递归遍历二叉树前序非递归遍历;l2.中序非递归遍历中序非递归遍历;l3.后序非递归遍历后序非递归遍历;l4.4.层层次遍次遍历历l要求：要求：建立如建立如图图的二叉的二叉树树,结结点点为为student,student,定义如下定义如下,给出给出遍遍历历结果。结果。typedef structintnum;/学号学号 char name10;/姓名姓名 student；typedef student EType;1654327第63页，本讲稿共67页3.3.关于从下至上算法讨论关于从下至上算法讨论 l静态队列中，出队时不存在释放空间问题
43、静态队列中，出队时不存在释放空间问题?l队列中除原来的队头和队尾指针外，还要增加一个总队列中除原来的队头和队尾指针外，还要增加一个总是指在第一个进队结点是指在第一个进队结点 l最后进队的结点指针作为栈顶最后进队的结点指针作为栈顶.图5.4.5 队列状态1B2C3D4E5F6G0Afrontfrontrearrear第64页，本讲稿共67页2 2。求二叉树的高度。求二叉树的高度 int BinaryHeight(BinaryTreeNode *BT)/返回二叉树的高度返回二叉树的高度 if(!BT)return 0;int HighL=BinaryHeight(BT-LChild);int Hi
44、ghR=BinaryHeight(BT-RChild);if(HighL HighR)return+HighL;else return+HighR;第65页，本讲稿共67页HL=0HR=0返回1HL=1HL=0HR=0返回1HL=1HR=0返回0返回2HR=2HL=0HR=0返回1HL=0HR=1HR=2HL=3返回3返回2返回返回4第66页，本讲稿共67页3 3。删除二叉树。删除二叉树 void BinaryDelete(BinaryTreeNode*BT)/二叉树的删除算法二叉树的删除算法if(BT)BinaryDelete(BT-LChild);BinaryDelete(BT-RChild);delete BT;/这里的这里的delete是系统过程是系统过程4。统计二叉树中结点的个数统计二叉树中结点的个数 第67页，本讲稿共67页