《Chapter二叉树的遍历.pptx》由会员分享，可在线阅读，更多相关《Chapter二叉树的遍历.pptx（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、18.6 8.6 二叉树遍历二叉树遍历二叉树遍历二叉树遍历n 8.6.1 遍历二叉树的定义遍历二叉树的定义n n 二叉树遍历二叉树遍历二叉树遍历二叉树遍历是指按照某种顺序是指按照某种顺序是指按照某种顺序是指按照某种顺序访问访问访问访问二叉树中的每个节二叉树中的每个节二叉树中的每个节二叉树中的每个节点，使每个节点被访问一次，且只被访问一次。点，使每个节点被访问一次，且只被访问一次。点，使每个节点被访问一次，且只被访问一次。点，使每个节点被访问一次，且只被访问一次。n n “访访访访问问问问”的的的的含含含含义义义义：是是是是指指指指对对对对节节节节点点点点施施施施行行行行某某某某种种种种操操操操
2、作作作作，操操操操作作作作可可可可以以以以是是是是输输输输出出出出节节节节点点点点信信信信息息息息，修修修修改改改改节节节节点点点点的的的的数数数数据据据据值值值值等等等等，但但但但要要要要求求求求这这这这种种种种访访访访问问问问不破坏它原来的数据结构不破坏它原来的数据结构不破坏它原来的数据结构不破坏它原来的数据结构。n n 以以以以二叉链表二叉链表二叉链表二叉链表作为二叉树的存储结构。作为二叉树的存储结构。作为二叉树的存储结构。作为二叉树的存储结构。第1页/共61页2uu 例例例例 假设一棵二叉树存储着有关人事方面的信息，每个节点假设一棵二叉树存储着有关人事方面的信息，每个节点假设一棵二叉树
3、存储着有关人事方面的信息，每个节点假设一棵二叉树存储着有关人事方面的信息，每个节点含有姓名、工资等信息。管理和使用这些信息时可能需要作这含有姓名、工资等信息。管理和使用这些信息时可能需要作这含有姓名、工资等信息。管理和使用这些信息时可能需要作这含有姓名、工资等信息。管理和使用这些信息时可能需要作这样一些工作：样一些工作：样一些工作：样一些工作：（1 1）将每个人的）将每个人的）将每个人的）将每个人的工资提高工资提高工资提高工资提高20%20%；（2 2）打印打印打印打印每个人的姓名和工资；每个人的姓名和工资；每个人的姓名和工资；每个人的姓名和工资；（3 3）求最低工资数额和领取最低工资的）求最
4、低工资数额和领取最低工资的）求最低工资数额和领取最低工资的）求最低工资数额和领取最低工资的人数人数人数人数。对于（对于（对于（对于（1 1），访问是），访问是），访问是），访问是对工资值进行修改对工资值进行修改对工资值进行修改对工资值进行修改的操作；的操作；的操作；的操作；对于（对于（对于（对于（2 2），访问的含义是），访问的含义是），访问的含义是），访问的含义是打印该节点的信息打印该节点的信息打印该节点的信息打印该节点的信息；对于（对于（对于（对于（3 3），访问只是），访问只是），访问只是），访问只是检查和统计检查和统计检查和统计检查和统计。不管访问的具体操作是什么，都必须做到不管访问的
5、具体操作是什么，都必须做到不管访问的具体操作是什么，都必须做到不管访问的具体操作是什么，都必须做到既无重既无重既无重既无重复，又无遗漏复，又无遗漏复，又无遗漏复，又无遗漏。第2页/共61页3线性结构的遍历线性结构的遍历线性结构的遍历线性结构的遍历非线性结构的遍历非线性结构的遍历非线性结构的遍历非线性结构的遍历只要按照结构原有的线只要按照结构原有的线只要按照结构原有的线只要按照结构原有的线性顺序，从第一个元素性顺序，从第一个元素性顺序，从第一个元素性顺序，从第一个元素起依次访问各元素即可。起依次访问各元素即可。起依次访问各元素即可。起依次访问各元素即可。v每个节点可能有一个以上每个节点可能有一个
6、以上每个节点可能有一个以上每个节点可能有一个以上的直接后继；的直接后继；的直接后继；的直接后继；v必须必须必须必须规定遍历的规则规定遍历的规则规定遍历的规则规定遍历的规则，并，并，并，并按此规则遍历二叉树；按此规则遍历二叉树；按此规则遍历二叉树；按此规则遍历二叉树；v最后得到二叉树所有节点最后得到二叉树所有节点最后得到二叉树所有节点最后得到二叉树所有节点的一个的一个的一个的一个线性序列线性序列线性序列线性序列。线性结构与非线性结构遍历的区别线性结构与非线性结构遍历的区别第3页/共61页4n 8.6.2 遍历二叉树的方式遍历二叉树的方式n n 深度优先遍历：深度优先遍历：深度优先遍历：深度优先遍
7、历：是尽可能地沿分支节点向深度方向进是尽可能地沿分支节点向深度方向进是尽可能地沿分支节点向深度方向进是尽可能地沿分支节点向深度方向进行周游。节点既可以在向下遍历之前访问，也可以在从子行周游。节点既可以在向下遍历之前访问，也可以在从子行周游。节点既可以在向下遍历之前访问，也可以在从子行周游。节点既可以在向下遍历之前访问，也可以在从子树返回之前访问。树返回之前访问。树返回之前访问。树返回之前访问。n n 广度优先遍历：广度优先遍历：广度优先遍历：广度优先遍历：是按照从上到下、从左到右的顺序进是按照从上到下、从左到右的顺序进是按照从上到下、从左到右的顺序进是按照从上到下、从左到右的顺序进行层次访问节
8、点。行层次访问节点。行层次访问节点。行层次访问节点。A AB BE EHHJ JD DL LI IKKC CGGF FMM第4页/共61页5深度优先遍历深度优先遍历1 1、一棵二叉树由三部分组成：、一棵二叉树由三部分组成：、一棵二叉树由三部分组成：、一棵二叉树由三部分组成：根节点（根节点（根节点（根节点（V V）；左子树（）；左子树（）；左子树（）；左子树（L L）；）；）；）；右子树（右子树（右子树（右子树（R R）。）。）。）。V VL LR R2 2、若规定：、若规定：、若规定：、若规定：L L：遍历根节点的左子树：遍历根节点的左子树：遍历根节点的左子树：遍历根节点的左子树 ;R R：遍
9、历根节点的右子树；：遍历根节点的右子树；：遍历根节点的右子树；：遍历根节点的右子树；V V：访问根节点。：访问根节点。：访问根节点。：访问根节点。则遍历二叉树有则遍历二叉树有则遍历二叉树有则遍历二叉树有6 6种方式：种方式：种方式：种方式：VLR LVR LRVVLR LVR LRV VRL RVL RLV VRL RVL RLV 若规定按若规定按若规定按若规定按先左子树后右子树先左子树后右子树先左子树后右子树先左子树后右子树的顺序进行遍历，则有：的顺序进行遍历，则有：的顺序进行遍历，则有：的顺序进行遍历，则有：VLRVLR：前序遍历（先根遍历）：前序遍历（先根遍历）：前序遍历（先根遍历）：前
10、序遍历（先根遍历）LVRLVR：中序遍历（中根遍历）：中序遍历（中根遍历）：中序遍历（中根遍历）：中序遍历（中根遍历）LRVLRV：后序遍历（后根遍历）：后序遍历（后根遍历）：后序遍历（后根遍历）：后序遍历（后根遍历）演示演示演示演示8-18-1第5页/共61页6n 8.6.3 前序遍历前序遍历1 1、前序遍历的递归定义、前序遍历的递归定义、前序遍历的递归定义、前序遍历的递归定义若二叉树为空，遍历结束；否则若二叉树为空，遍历结束；否则若二叉树为空，遍历结束；否则若二叉树为空，遍历结束；否则（1 1）访问根节点；（）访问根节点；（）访问根节点；（）访问根节点；（V V）（2 2）前序遍历根节点的
11、左子树；（）前序遍历根节点的左子树；（）前序遍历根节点的左子树；（）前序遍历根节点的左子树；（L L）（3 3）前序遍历根节点的右子树。（）前序遍历根节点的右子树。（）前序遍历根节点的右子树。（）前序遍历根节点的右子树。（R R）A AB BD DE EF FC CHHI IGG前序遍历的序列：前序遍历的序列：前序遍历的序列：前序遍历的序列：A B D G H C E I FA B D G H C E I F演示演示演示演示8-28-2前序序列的第一个元素前序序列的第一个元素必为二叉树的根节点必为二叉树的根节点第6页/共61页72 2、前序遍历的递归算法、前序遍历的递归算法、前序遍历的递归算法
12、、前序遍历的递归算法template template void void PreOrderPreOrder(BinaryTreeNode BinaryTreeNode *t t)if(if(t t!=!=NULLNULL)Visit(t);Visit(t);PreOrderPreOrder(t t-LeftChildLeftChild););PreOrderPreOrder(t t-RightChild RightChild););第7页/共61页8n 8.6.4 中序遍历中序遍历1 1、中序遍历的递归定义、中序遍历的递归定义、中序遍历的递归定义、中序遍历的递归定义若二叉树为空，遍历结束；否
13、则：若二叉树为空，遍历结束；否则：若二叉树为空，遍历结束；否则：若二叉树为空，遍历结束；否则：（1 1）中序遍历根节点的左子树；（）中序遍历根节点的左子树；（）中序遍历根节点的左子树；（）中序遍历根节点的左子树；（L L）（2 2）访问根节点；（）访问根节点；（）访问根节点；（）访问根节点；（V V）（3 3）中序遍历根节点的右子树。（）中序遍历根节点的右子树。（）中序遍历根节点的右子树。（）中序遍历根节点的右子树。（R R）A AB BD DE EF FC CHHI IGG中序遍历的序列：中序遍历的序列：中序遍历的序列：中序遍历的序列：G D H B G D H B A A E I C F
14、E I C F演示演示演示演示8-38-3中序序列的中序序列的根节点根节点恰为恰为左右子树的中序序列的左右子树的中序序列的分界分界点点第8页/共61页92 2、中序遍历的递归算法、中序遍历的递归算法、中序遍历的递归算法、中序遍历的递归算法template template void void InOrderInOrder(BinaryTreeNode BinaryTreeNode *t t)if(if(t t!=!=NULLNULL)InOrderInOrder(t t-LeftChildLeftChild););Visit(t);Visit(t);InOrderInOrder(t t-Rig
15、htChild RightChild););第9页/共61页10n 8.6.5 后序遍历后序遍历1 1、后序遍历的递归定义、后序遍历的递归定义、后序遍历的递归定义、后序遍历的递归定义若二叉树为空，遍历结束；否则：若二叉树为空，遍历结束；否则：若二叉树为空，遍历结束；否则：若二叉树为空，遍历结束；否则：（1 1）后序遍历根节点的左子树；（）后序遍历根节点的左子树；（）后序遍历根节点的左子树；（）后序遍历根节点的左子树；（L L）（2 2）后序遍历根节点的右子树。（）后序遍历根节点的右子树。（）后序遍历根节点的右子树。（）后序遍历根节点的右子树。（R R）（3 3）访问根节点；（）访问根节点；（）
16、访问根节点；（）访问根节点；（V V）A AB BD DE EF FC CHHI IGG后序遍历的序列：后序遍历的序列：后序遍历的序列：后序遍历的序列：G H D B I E F C G H D B I E F C A A演示演示演示演示 8-48-4后序序列的后序序列的最后最后一个元素一个元素必为二叉树的必为二叉树的根节点根节点第10页/共61页113 3、后序遍历的递归算法、后序遍历的递归算法、后序遍历的递归算法、后序遍历的递归算法template template void void PostOrderPostOrder(BinaryTreeNode BinaryTreeNode *t
17、t)if(if(t t!=!=NULLNULL)PostOrderPostOrder(t t-LeftChildLeftChild););PostOrderPostOrder(t t-RightChild RightChild););Visit(t);Visit(t);第11页/共61页12n 8.6.6 遍历表达式二叉树遍历表达式二叉树1 1、可以把任意一个算术表达式用一棵二叉树表示、可以把任意一个算术表达式用一棵二叉树表示、可以把任意一个算术表达式用一棵二叉树表示、可以把任意一个算术表达式用一棵二叉树表示表达式的形式：表达式的形式：表达式的形式：表达式的形式：根节点为根节点为根节点为根节点
18、为操作符操作符操作符操作符；第一操作数为第一操作数为第一操作数为第一操作数为左子树左子树左子树左子树；第二操作数为第二操作数为第二操作数为第二操作数为右子树右子树右子树右子树。u 例如：表达式例如：表达式例如：表达式例如：表达式a/(b-c)*d+ea/(b-c)*d+e的二叉树表示为：的二叉树表示为：的二叉树表示为：的二叉树表示为：+*/d dc ce e-a ab b第12页/共61页132 2、对该二叉树分别进行前序、对该二叉树分别进行前序、对该二叉树分别进行前序、对该二叉树分别进行前序、中序和后序遍历，得到以下三中序和后序遍历，得到以下三中序和后序遍历，得到以下三中序和后序遍历，得到以
19、下三种不同形式：种不同形式：种不同形式：种不同形式：（1 1）前序遍历：）前序遍历：）前序遍历：）前序遍历：+*/a-bcde+*/a-bcde（前缀表（前缀表（前缀表（前缀表达式，波兰式）达式，波兰式）达式，波兰式）达式，波兰式）（2 2）中序遍历：）中序遍历：）中序遍历：）中序遍历：a/b-c*d+ea/b-c*d+e（中缀表（中缀表（中缀表（中缀表达式）达式）达式）达式）（3 3）后序遍历：）后序遍历：）后序遍历：）后序遍历：abc-/d*e+abc-/d*e+（后缀表（后缀表（后缀表（后缀表达式，逆波兰式）达式，逆波兰式）达式，逆波兰式）达式，逆波兰式）3 3、前缀表达式前缀表达式前缀
20、表达式前缀表达式和和和和后缀表达式后缀表达式后缀表达式后缀表达式在编译程序中有着非常在编译程序中有着非常在编译程序中有着非常在编译程序中有着非常重要的作用。重要的作用。重要的作用。重要的作用。+*/d dc ce e-a ab b表达式为表达式为表达式为表达式为a/(b-c)*d+ea/(b-c)*d+e第13页/共61页14u 例例例例:表达式表达式表达式表达式 Exp=Exp=a*ba*b+(c-d/e)*f(c-d/e)*fl 前缀式：前缀式：前缀式：前缀式：+*ab*-c/def*ab*-c/defl 中缀式：中缀式：中缀式：中缀式：a*ba*b+c-d/e*fc-d/e*fl 后缀式
21、：后缀式：后缀式：后缀式：ab*ab*cde/-f*+cde/-f*+结论：三种表达方式结论：三种表达方式结论：三种表达方式结论：三种表达方式 VS.VS.原始表达式原始表达式原始表达式原始表达式（1 1）操作数之间的相对次序不变；）操作数之间的相对次序不变；）操作数之间的相对次序不变；）操作数之间的相对次序不变；（2 2）运算符的相对次序不同；）运算符的相对次序不同；）运算符的相对次序不同；）运算符的相对次序不同；（3 3）中缀式丢失了括号信息，致使运算的次序不确）中缀式丢失了括号信息，致使运算的次序不确）中缀式丢失了括号信息，致使运算的次序不确）中缀式丢失了括号信息，致使运算的次序不确定、
22、无意义。定、无意义。定、无意义。定、无意义。第14页/共61页15u 例例例例:表达式表达式表达式表达式 Exp=Exp=a*ba*b+(c-d/e)*f(c-d/e)*fl 前缀式：前缀式：前缀式：前缀式：+*ab*-c/def*ab*-c/def（4 4）前缀式的运算规则为：连续出现的）前缀式的运算规则为：连续出现的）前缀式的运算规则为：连续出现的）前缀式的运算规则为：连续出现的两个操作数两个操作数两个操作数两个操作数和和和和它们它们它们它们之前之前之前之前紧靠它们的紧靠它们的紧靠它们的紧靠它们的运算符运算符运算符运算符构成一个最小表达式；构成一个最小表达式；构成一个最小表达式；构成一个最
23、小表达式；l 后缀式：后缀式：后缀式：后缀式：ab*ab*cde/-f*+cde/-f*+（5 5）后缀式的运算规则为：运算符在式中的顺序恰好）后缀式的运算规则为：运算符在式中的顺序恰好）后缀式的运算规则为：运算符在式中的顺序恰好）后缀式的运算规则为：运算符在式中的顺序恰好为表达式的运算顺序；为表达式的运算顺序；为表达式的运算顺序；为表达式的运算顺序；每个每个每个每个运算符运算符运算符运算符和它和它和它和它之前之前之前之前出现且紧靠它的出现且紧靠它的出现且紧靠它的出现且紧靠它的两个操作数两个操作数两个操作数两个操作数构构构构成一个最小表达式。成一个最小表达式。成一个最小表达式。成一个最小表达式
24、。演示演示演示演示 8-58-5第15页/共61页16n 后缀表达式的特点：后缀表达式的特点：后缀表达式的特点：后缀表达式的特点：后缀表达式后缀表达式后缀表达式后缀表达式与表达式的操作数的先后次序相同与表达式的操作数的先后次序相同与表达式的操作数的先后次序相同与表达式的操作数的先后次序相同，只是运，只是运，只是运，只是运算符的先后次序有所改变，算符的先后次序有所改变，算符的先后次序有所改变，算符的先后次序有所改变，后缀表达式的运算符次序就后缀表达式的运算符次序就后缀表达式的运算符次序就后缀表达式的运算符次序就是其执行次序是其执行次序是其执行次序是其执行次序；后缀表达式中后缀表达式中后缀表达式中
25、后缀表达式中没有括号没有括号没有括号没有括号（因为括号的作用就是改变运算（因为括号的作用就是改变运算（因为括号的作用就是改变运算（因为括号的作用就是改变运算次序，既然后缀表达式中已经考虑了运算规则，所以就次序，既然后缀表达式中已经考虑了运算规则，所以就次序，既然后缀表达式中已经考虑了运算规则，所以就次序，既然后缀表达式中已经考虑了运算规则，所以就不需要括号了）。不需要括号了）。不需要括号了）。不需要括号了）。u 如何从后缀式求值？如何从后缀式求值？如何从后缀式求值？如何从后缀式求值？例例例例:表达式表达式表达式表达式 Exp=a*b+(c-d/e)*fExp=a*b+(c-d/e)*f，后缀式
26、：，后缀式：，后缀式：，后缀式：ab*cde/-f*+ab*cde/-f*+第16页/共61页17n 后缀表达式的计算方法：后缀表达式的计算方法：后缀表达式的计算方法：后缀表达式的计算方法：从左自右依次扫描表达式的各单词从左自右依次扫描表达式的各单词从左自右依次扫描表达式的各单词从左自右依次扫描表达式的各单词：（1 1）如果是操作数，存入栈中；）如果是操作数，存入栈中；）如果是操作数，存入栈中；）如果是操作数，存入栈中；（2 2）如果是运算符，就取其前面的两个操作数（从栈）如果是运算符，就取其前面的两个操作数（从栈）如果是运算符，就取其前面的两个操作数（从栈）如果是运算符，就取其前面的两个操作
27、数（从栈中弹出的两个数）进行运算，中间结果同样存入栈中，中弹出的两个数）进行运算，中间结果同样存入栈中，中弹出的两个数）进行运算，中间结果同样存入栈中，中弹出的两个数）进行运算，中间结果同样存入栈中，作为下一个运算的操作数；作为下一个运算的操作数；作为下一个运算的操作数；作为下一个运算的操作数；（3 3）如此反复直到表达式处理完毕。如此反复直到表达式处理完毕。如此反复直到表达式处理完毕。如此反复直到表达式处理完毕。【注意注意注意注意】第一次弹栈得到的操作数为运算符第一次弹栈得到的操作数为运算符第一次弹栈得到的操作数为运算符第一次弹栈得到的操作数为运算符后后后后的操作数；的操作数；的操作数；的操
28、作数；第二次第二次第二次第二次弹弹栈得到的操作数为运算符栈得到的操作数为运算符栈得到的操作数为运算符栈得到的操作数为运算符前前前前的操作数。的操作数。的操作数。的操作数。ab*ab*cde/-f*+cde/-f*+第17页/共61页18例：表达式例：表达式例：表达式例：表达式A/(B+C*D)-EA/(B+C*D)-E的后缀式的后缀式的后缀式的后缀式ABCD*+/E-ABCD*+/E-toptopT1BAtopT2A读入读入读入读入*C*D-TC*D-T1 1读入读入读入读入+B+TB+T1 1-T-T2 2topT3topET3topT4读入读入读入读入E E读入读入读入读入-T T3 3-
29、E-T-E-T4 4读入读入读入读入/A/TA/T2 2-T-T3 3B BC CD DA A第18页/共61页19n 8.6.7 层序遍历：广度优先遍历层序遍历：广度优先遍历1 1、层序遍历的定义、层序遍历的定义、层序遍历的定义、层序遍历的定义 层序遍历是指从二叉树的第层序遍历是指从二叉树的第层序遍历是指从二叉树的第层序遍历是指从二叉树的第1 1层（根节点）开始，层（根节点）开始，层（根节点）开始，层（根节点）开始，从上至下从上至下从上至下从上至下逐层遍历，在同一层中，则按逐层遍历，在同一层中，则按逐层遍历，在同一层中，则按逐层遍历，在同一层中，则按从左至右从左至右从左至右从左至右的的的的顺
30、序逐个访问。顺序逐个访问。顺序逐个访问。顺序逐个访问。A AB BD DE EF FC CHHI IGG层序遍历的序列：层序遍历的序列：层序遍历的序列：层序遍历的序列：A B C D E F G H IA B C D E F G H I第19页/共61页202 2、层序遍历的算法思想、层序遍历的算法思想、层序遍历的算法思想、层序遍历的算法思想【思路思路思路思路】在进行层序遍历时，对第在进行层序遍历时，对第在进行层序遍历时，对第在进行层序遍历时，对第i i层节点访问后，层节点访问后，层节点访问后，层节点访问后，紧接着对第紧接着对第紧接着对第紧接着对第i+1i+1层节点进行访问，访问的顺序是按照层
31、节点进行访问，访问的顺序是按照层节点进行访问，访问的顺序是按照层节点进行访问，访问的顺序是按照第第第第i i层的访问顺序依次访问各节点的左孩子和右孩子。层的访问顺序依次访问各节点的左孩子和右孩子。层的访问顺序依次访问各节点的左孩子和右孩子。层的访问顺序依次访问各节点的左孩子和右孩子。即：先访问的节点，其左右孩子先访问；即：先访问的节点，其左右孩子先访问；即：先访问的节点，其左右孩子先访问；即：先访问的节点，其左右孩子先访问；后访问的节点，其左右孩子后访问。后访问的节点，其左右孩子后访问。后访问的节点，其左右孩子后访问。后访问的节点，其左右孩子后访问。设置一个队列结构设置一个队列结构设置一个队列
32、结构设置一个队列结构第20页/共61页21l 层序遍历从二叉树的根节点开始，层序遍历从二叉树的根节点开始，层序遍历从二叉树的根节点开始，层序遍历从二叉树的根节点开始，l 首先将根节点指针入队，首先将根节点指针入队，首先将根节点指针入队，首先将根节点指针入队，l 然后从队头取出一个元素，每取出一个元素，执行两然后从队头取出一个元素，每取出一个元素，执行两然后从队头取出一个元素，每取出一个元素，执行两然后从队头取出一个元素，每取出一个元素，执行两个操作：个操作：个操作：个操作：（1 1）访问该元素所指节点；）访问该元素所指节点；）访问该元素所指节点；）访问该元素所指节点；（2 2）若该元素所指节点
33、的左右孩子节点非空，）若该元素所指节点的左右孩子节点非空，）若该元素所指节点的左右孩子节点非空，）若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针则将该元素所指节点的左孩子指针和右孩子指针则将该元素所指节点的左孩子指针和右孩子指针则将该元素所指节点的左孩子指针和右孩子指针顺序入队。顺序入队。顺序入队。顺序入队。l 重复以上步骤，直到队列为空。重复以上步骤，直到队列为空。重复以上步骤，直到队列为空。重复以上步骤，直到队列为空。层序遍历的算法思想层序遍历的算法思想层序遍历的算法思想层序遍历的算法思想第21页/共61页22A AB BD DE EF FC CHHI IG
34、GA AB B C C D D E E F FGGHHI I层序遍历结果：层序遍历结果：层序遍历结果：层序遍历结果：A AI IB B C C D D E E F F GG HH层序遍历的演示层序遍历的演示层序遍历的演示层序遍历的演示第22页/共61页23第23页/共61页24u 例：已知一棵二叉树的前序序列和中序序列分别为例：已知一棵二叉树的前序序列和中序序列分别为例：已知一棵二叉树的前序序列和中序序列分别为例：已知一棵二叉树的前序序列和中序序列分别为ABDEGCFHABDEGCFH和和和和DBGEACHFDBGEACHF，则该二叉树的后序序列，则该二叉树的后序序列，则该二叉树的后序序列，则
35、该二叉树的后序序列为为为为 ，层序序列为，层序序列为，层序序列为，层序序列为 。A AB BD DE EF FC CGGHHDGEBHFCADGEBHFCAABCDEFGHABCDEFGH8.6.8 由由由由前序（后序）序列前序（后序）序列前序（后序）序列前序（后序）序列和和和和中序序列中序序列中序序列中序序列建立二叉树建立二叉树建立二叉树建立二叉树A ABDEGBDEGCFHCFHDBGEDBGEA ACHFCHFB BDEGDEGD DB BGEGEE EGGGGE EC CFHFHC CHFHFF FHHHHF F左子树：左子树：左子树：左子树：右子树：右子树：右子树：右子树：第24页/
36、共61页25uu 解答：解答：解答：解答：若二叉树的任意两个节点的值都不相同，若二叉树的任意两个节点的值都不相同，若二叉树的任意两个节点的值都不相同，若二叉树的任意两个节点的值都不相同，则二叉树的则二叉树的则二叉树的则二叉树的前序序列和中序序列可唯一确定一棵二叉树，确定方法如下：前序序列和中序序列可唯一确定一棵二叉树，确定方法如下：前序序列和中序序列可唯一确定一棵二叉树，确定方法如下：前序序列和中序序列可唯一确定一棵二叉树，确定方法如下：（1 1）根据前序遍历的定义：）根据前序遍历的定义：）根据前序遍历的定义：）根据前序遍历的定义：前序序列的第一个元素必为二叉树前序序列的第一个元素必为二叉树前
37、序序列的第一个元素必为二叉树前序序列的第一个元素必为二叉树的根节点的根节点的根节点的根节点；根据中序遍历的定义：根据中序遍历的定义：根据中序遍历的定义：根据中序遍历的定义：中序序列的根节点恰为左右子树的中中序序列的根节点恰为左右子树的中中序序列的根节点恰为左右子树的中中序序列的根节点恰为左右子树的中序序列的分界点序序列的分界点序序列的分界点序序列的分界点；根节点前的子序列为左子树的中序序列；根节；根节点前的子序列为左子树的中序序列；根节；根节点前的子序列为左子树的中序序列；根节；根节点前的子序列为左子树的中序序列；根节点后的子序列为右子树的中序序列；点后的子序列为右子树的中序序列；点后的子序列
38、为右子树的中序序列；点后的子序列为右子树的中序序列；（2 2）根据左子树的中序序列根据左子树的中序序列根据左子树的中序序列根据左子树的中序序列的节点个数，的节点个数，的节点个数，的节点个数，在前序序列中找出左在前序序列中找出左在前序序列中找出左在前序序列中找出左子树的前序序列子树的前序序列子树的前序序列子树的前序序列，剩下的即为右子树的前序序列；，剩下的即为右子树的前序序列；，剩下的即为右子树的前序序列；，剩下的即为右子树的前序序列；（3 3）然后用相同的办法分别找出左、右子树的根及其左右子树）然后用相同的办法分别找出左、右子树的根及其左右子树）然后用相同的办法分别找出左、右子树的根及其左右子
39、树）然后用相同的办法分别找出左、右子树的根及其左右子树的前序序列和中序序列；的前序序列和中序序列；的前序序列和中序序列；的前序序列和中序序列；（4 4）依此类推，直至待构造的二叉树的前序序列仅剩一个字母）依此类推，直至待构造的二叉树的前序序列仅剩一个字母）依此类推，直至待构造的二叉树的前序序列仅剩一个字母）依此类推，直至待构造的二叉树的前序序列仅剩一个字母为止。为止。为止。为止。第25页/共61页26结论结论 由二叉树的由二叉树的由二叉树的由二叉树的前序序列和中序序列前序序列和中序序列前序序列和中序序列前序序列和中序序列或者或者或者或者中序序列和后序序列中序序列和后序序列中序序列和后序序列中序
40、序列和后序序列可以可以可以可以唯一确定唯一确定唯一确定唯一确定一棵二叉树一棵二叉树一棵二叉树一棵二叉树第26页/共61页27u 20002000年南开大学考研题年南开大学考研题年南开大学考研题年南开大学考研题 一棵非空的二叉树的一棵非空的二叉树的一棵非空的二叉树的一棵非空的二叉树的前序遍历前序遍历前序遍历前序遍历序列与序列与序列与序列与后序遍历后序遍历后序遍历后序遍历序列正好序列正好序列正好序列正好相反相反相反相反，则该二叉树一定满足：，则该二叉树一定满足：，则该二叉树一定满足：，则该二叉树一定满足：A A、所有的节点均无左孩子、所有的节点均无左孩子、所有的节点均无左孩子、所有的节点均无左孩子
41、 B B、所有的节点均无右孩子、所有的节点均无右孩子、所有的节点均无右孩子、所有的节点均无右孩子 C C、只有一个叶子节点、只有一个叶子节点、只有一个叶子节点、只有一个叶子节点 D D、是任意一棵二叉树、是任意一棵二叉树、是任意一棵二叉树、是任意一棵二叉树C C课堂练习课堂练习课堂练习课堂练习1 1第27页/共61页28u 20002000年西电考研题年西电考研题年西电考研题年西电考研题 一棵二叉树的前序、中序和后序序列分别如下，其中一一棵二叉树的前序、中序和后序序列分别如下，其中一一棵二叉树的前序、中序和后序序列分别如下，其中一一棵二叉树的前序、中序和后序序列分别如下，其中一部分未显示出来，
42、试求出空格处的内容，并画出该二叉树。部分未显示出来，试求出空格处的内容，并画出该二叉树。部分未显示出来，试求出空格处的内容，并画出该二叉树。部分未显示出来，试求出空格处的内容，并画出该二叉树。前序序列：前序序列：前序序列：前序序列：B B F F ICEHICEH GG；中序序列：中序序列：中序序列：中序序列：D D KFIAKFIA EJCEJC ；后序序列：后序序列：后序序列：后序序列：KK FBHJFBHJ GG A A。A AD DKKJ JB BHHGGD DI IE EC C课堂练习课堂练习课堂练习课堂练习2 2第28页/共61页29A AB BC CD DE EF FKKI IJ
43、 JHHGGABDFKICEHJGABDFKICEHJGDBKFIAHEJCGDBKFIAHEJCGDKIFBHJEGCADKIFBHJEGCA 前序遍历序列：前序遍历序列：前序遍历序列：前序遍历序列：中序遍历序列：中序遍历序列：中序遍历序列：中序遍历序列：后序遍历序列：后序遍历序列：后序遍历序列：后序遍历序列：第29页/共61页30课后作业课后作业课后作业课后作业n P252-P252-P252-P252-练习练习练习练习4 4 4 4：绘制表达式的二叉树：绘制表达式的二叉树：绘制表达式的二叉树：绘制表达式的二叉树n P259-P259-P259-P259-练习练习练习练习9 9 9 9：采
44、用数组存储二叉树，实现中序遍：采用数组存储二叉树，实现中序遍：采用数组存储二叉树，实现中序遍：采用数组存储二叉树，实现中序遍历（提示：递归算法）历（提示：递归算法）历（提示：递归算法）历（提示：递归算法）n P259-P259-P259-P259-练习练习练习练习17171717：使用链式堆栈方法，来实现二叉树：使用链式堆栈方法，来实现二叉树：使用链式堆栈方法，来实现二叉树：使用链式堆栈方法，来实现二叉树的前序遍历的前序遍历的前序遍历的前序遍历 （提示：非递归算法；在向左子树遍历（提示：非递归算法；在向左子树遍历（提示：非递归算法；在向左子树遍历（提示：非递归算法；在向左子树遍历之前，先把当前
45、右子树节点压入栈中，以便后面遍之前，先把当前右子树节点压入栈中，以便后面遍之前，先把当前右子树节点压入栈中，以便后面遍之前，先把当前右子树节点压入栈中，以便后面遍历）历）历）历）第30页/共61页318.7 8.7 抽象数据类型抽象数据类型抽象数据类型抽象数据类型BinaryTreeBinaryTreeADT BinaryTreeADT BinaryTree实例实例实例实例 元素集合；如果不空，则被划分为根节点、左子树和右子树；元素集合；如果不空，则被划分为根节点、左子树和右子树；元素集合；如果不空，则被划分为根节点、左子树和右子树；元素集合；如果不空，则被划分为根节点、左子树和右子树；每棵子
46、树仍是一棵二叉树每棵子树仍是一棵二叉树每棵子树仍是一棵二叉树每棵子树仍是一棵二叉树操作操作操作操作 Create()Create()：创建一棵空二叉树：创建一棵空二叉树：创建一棵空二叉树：创建一棵空二叉树 IsEmpty()IsEmpty()：如果二叉树为空，：如果二叉树为空，：如果二叉树为空，：如果二叉树为空，return truereturn true；否则；否则；否则；否则return falsereturn false；Root(x)Root(x)：取根节点：取根节点：取根节点：取根节点x x；操作失败，；操作失败，；操作失败，；操作失败，return falsereturn fals
47、e，否则，否则，否则，否则return truereturn true；MakeTree(root,left,right)MakeTree(root,left,right)：创建一棵二叉树，根节点为：创建一棵二叉树，根节点为：创建一棵二叉树，根节点为：创建一棵二叉树，根节点为rootroot BreakTree(root,left,right)BreakTree(root,left,right)：拆分二叉树：拆分二叉树：拆分二叉树：拆分二叉树 PreOrderPreOrder：前序遍历前序遍历前序遍历前序遍历 InOrderInOrder：中序遍历中序遍历中序遍历中序遍历 PostOrderP
48、ostOrder：后序遍历后序遍历后序遍历后序遍历 LevelOrderLevelOrder：层次遍历层次遍历层次遍历层次遍历 第31页/共61页32函数指针作为函数的参数函数指针作为函数的参数函数指针作为函数的参数函数指针作为函数的参数int fa(int a)return a+1;int fa(int a)return a+1;int fb(int b)return b+2;int fb(int b)return b+2;int AddFunc(int AddFunc(int(*f1)(int),int(*f2)(int)int(*f1)(int),int(*f2)(int),int a,
49、int b),int a,int b)return(*f1)(a)+(*f2)(b);return(*f1)(a)+(*f2)(b);int main()int main()int a=5,b=3;int a=5,b=3;a=AddFunc(fa,fb,a,b);a=AddFunc(fa,fb,a,b);return 0;return 0;return fa(a)+fb(b);return fa(a)+fb(b);第32页/共61页338.8 8.8 类类类类BinaryTreeBinaryTreetemplatetemplateclass BinaryTree class BinaryTre
50、e public:public:BinaryTree()root=0;BinaryTree()root=0;BinaryTree();BinaryTree();bool IsEmpty()const bool IsEmpty()const return(root)?false:true);return(root)?false:true);bool Root(T&x)const;bool Root(T&x)const;void void MakeTreeMakeTree(const T&element,(const T&element,BinaryTree&left,BinaryTree&rig