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