Chapter二叉树的遍历

会计学1Chapter二叉树的遍历28.6二叉树遍历

8.6.1遍历二叉树的定义

二叉树遍历是指按照某种顺序访问二叉树中的每个节点，使每个节点被访问一次，且只被访问一次。“访问”的含义：是指对节点施行某种操作，操作可以是输出节点信息，修改节点的数据值等，但要求这种访问不破坏它原来的数据结构。以二叉链表作为二叉树的存储结构。第1页/共61页3例假设一棵二叉树存储着有关人事方面的信息，每个节点含有姓名、工资等信息。管理和使用这些信息时可能需要作这样一些工作：（1）将每个人的工资提高20%；（2）打印每个人的姓名和工资；（3）求最低工资数额和领取最低工资的人数。对于（1），访问是对工资值进行修改的操作；对于（2），访问的含义是打印该节点的信息；对于（3），访问只是检查和统计。不管访问的具体操作是什么，都必须做到既无重复，又无遗漏。第2页/共61页4线性结构的遍历非线性结构的遍历只要按照结构原有的线性顺序，从第一个元素起依次访问各元素即可。每个节点可能有一个以上的直接后继；必须规定遍历的规则，并按此规则遍历二叉树；最后得到二叉树所有节点的一个线性序列。线性结构与非线性结构遍历的区别第3页/共61页58.6.2遍历二叉树的方式

深度优先遍历：是尽可能地沿分支节点向深度方向进行周游。节点既可以在向下遍历之前访问，也可以在从子树返回之前访问。

广度优先遍历：是按照从上到下、从左到右的顺序进行层次访问节点。ABEHJDLIKCGFM第4页/共61页6深度优先遍历1、一棵二叉树由三部分组成：根节点（V）；左子树（L）；右子树（R）。VLR2、若规定：L：遍历根节点的左子树;R：遍历根节点的右子树；V：访问根节点。则遍历二叉树有6种方式：

VLRLVRLRVVRLRVLRLV若规定按先左子树后右子树的顺序进行遍历，则有：VLR：前序遍历（先根遍历）LVR：中序遍历（中根遍历）LRV：后序遍历（后根遍历）演示8-1第5页/共61页7

8.6.3前序遍历1、前序遍历的递归定义若二叉树为空，遍历结束；否则（1）访问根节点；（V）（2）前序遍历根节点的左子树；（L）（3）前序遍历根节点的右子树。（R）ABDEFCHIG前序遍历的序列：ABDGHCEIF演示8-2前序序列的第一个元素必为二叉树的根节点第6页/共61页82、前序遍历的递归算法template<classT>voidPreOrder(BinaryTreeNode<T>*t){if(t!=NULL){Visit(t);

PreOrder(t->LeftChild);

PreOrder(t->RightChild);}}第7页/共61页9

8.6.4中序遍历1、中序遍历的递归定义若二叉树为空，遍历结束；否则：（1）中序遍历根节点的左子树；（L）（2）访问根节点；（V）（3）中序遍历根节点的右子树。（R）ABDEFCHIG中序遍历的序列：GDHBAEICF演示8-3中序序列的根节点恰为左右子树的中序序列的分界点第8页/共61页102、中序遍历的递归算法template<classT>voidInOrder(BinaryTreeNode<T>*t){if(t!=NULL){

InOrder(t->LeftChild); Visit(t);

InOrder(t->RightChild);}}第9页/共61页11

8.6.5后序遍历1、后序遍历的递归定义若二叉树为空，遍历结束；否则：（1）后序遍历根节点的左子树；（L）（2）后序遍历根节点的右子树。（R）（3）访问根节点；（V）ABDEFCHIG后序遍历的序列：GHDBIEFCA演示8-4后序序列的最后一个元素必为二叉树的根节点第10页/共61页123、后序遍历的递归算法template<classT>voidPostOrder(BinaryTreeNode<T>*t){if(t!=NULL){

PostOrder(t->LeftChild);

PostOrder(t->RightChild); Visit(t); }}第11页/共61页13

8.6.6遍历表达式二叉树1、可以把任意一个算术表达式用一棵二叉树表示表达式的形式：根节点为操作符；第一操作数为左子树；第二操作数为右子树。例如：表达式a/(b-c)*d+e的二叉树表示为：+*/dce-ab第12页/共61页142、对该二叉树分别进行前序、中序和后序遍历，得到以下三种不同形式：（1）前序遍历：+*/a-bcde（前缀表达式，波兰式）（2）中序遍历：a/b-c*d+e（中缀表达式）（3）后序遍历：abc-/d*e+（后缀表达式，逆波兰式）3、前缀表达式和后缀表达式在编译程序中有着非常重要的作用。+*/dce-ab表达式为a/(b-c)*d+e第13页/共61页15例:表达式Exp=a*b+(c-d/e)*f前缀式：+*ab*-c/def中缀式：a*b+c-d/e*f后缀式：ab*cde/-f*+结论：三种表达方式VS.原始表达式（1）操作数之间的相对次序不变；（2）运算符的相对次序不同；（3）中缀式丢失了括号信息，致使运算的次序不确定、无意义。第14页/共61页16例:表达式Exp=a*b+(c-d/e)*f前缀式：+*ab*-c/def（4）前缀式的运算规则为：连续出现的两个操作数和它们之前紧靠它们的运算符构成一个最小表达式；后缀式：ab*cde/-f*+（5）后缀式的运算规则为：运算符在式中的顺序恰好为表达式的运算顺序；每个运算符和它之前出现且紧靠它的两个操作数构成一个最小表达式。演示8-5第15页/共61页17

后缀表达式的特点：后缀表达式与表达式的操作数的先后次序相同，只是运算符的先后次序有所改变，后缀表达式的运算符次序就是其执行次序；后缀表达式中没有括号（因为括号的作用就是改变运算次序，既然后缀表达式中已经考虑了运算规则，所以就不需要括号了）。如何从后缀式求值？例:表达式Exp=a*b+(c-d/e)*f，后缀式：ab*cde/-f*+第16页/共61页18后缀表达式的计算方法：从左自右依次扫描表达式的各单词：（1）如果是操作数，存入栈中；（2）如果是运算符，就取其前面的两个操作数（从栈中弹出的两个数）进行运算，中间结果同样存入栈中，作为下一个运算的操作数；（3）如此反复直到表达式处理完毕。【注意】第一次弹栈得到的操作数为运算符后的操作数；第二次弹栈得到的操作数为运算符前的操作数。

ab*cde/-f*+第17页/共61页19例：表达式A/(B+C*D)-E的后缀式ABCD*+/E-toptopT1BAtopT2A读入*C*D->T1读入+B+T1->T2topT3topET3topT4读入E读入-T3-E->T4读入/A/T2->T3BCDA第18页/共61页20

8.6.7层序遍历：广度优先遍历1、层序遍历的定义层序遍历是指从二叉树的第1层（根节点）开始，从上至下逐层遍历，在同一层中，则按从左至右的顺序逐个访问。ABDEFCHIG层序遍历的序列：ABCDEFGHI第19页/共61页212、层序遍历的算法思想【思路】在进行层序遍历时，对第i层节点访问后，紧接着对第i+1层节点进行访问，访问的顺序是按照第i层的访问顺序依次访问各节点的左孩子和右孩子。即：先访问的节点，其左右孩子先访问；后访问的节点，其左右孩子后访问。——设置一个队列结构第20页/共61页22层序遍历从二叉树的根节点开始，首先将根节点指针入队，然后从队头取出一个元素，每取出一个元素，执行两个操作：（1）访问该元素所指节点；（2）若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。重复以上步骤，直到队列为空。层序遍历的算法思想第21页/共61页23ABDEFCHIGABCDEFGHI层序遍历结果：AIBCDEFGH层序遍历的演示第22页/共61页24第23页/共61页25例：已知一棵二叉树的前序序列和中序序列分别为ABDEGCFH和DBGEACHF，则该二叉树的后序序列为

，层序序列为

。ABDEFCGHDGEBHFCAABCDEFGH8.6.8

由前序（后序）序列和中序序列建立二叉树ABDEGCFHDBGEACHFBDEGDBGEEGGECFHCHFFHHF左子树：右子树：第24页/共61页26

解答：若二叉树的任意两个节点的值都不相同，则二叉树的前序序列和中序序列可唯一确定一棵二叉树，确定方法如下：（1）根据前序遍历的定义：前序序列的第一个元素必为二叉树的根节点；

根据中序遍历的定义：中序序列的根节点恰为左右子树的中序序列的分界点；根节点前的子序列为左子树的中序序列；根节点后的子序列为右子树的中序序列；（2）根据左子树的中序序列的节点个数，在前序序列中找出左子树的前序序列，剩下的即为右子树的前序序列；（3）然后用相同的办法分别找出左、右子树的根及其左右子树的前序序列和中序序列；（4）依此类推，直至待构造的二叉树的前序序列仅剩一个字母为止。第25页/共61页27结论由二叉树的前序序列和中序序列或者中序序列和后序序列可以唯一确定一棵二叉树第26页/共61页28

2000年南开大学考研题一棵非空的二叉树的前序遍历序列与后序遍历序列正好相反，则该二叉树一定满足：

A、所有的节点均无左孩子B、所有的节点均无右孩子

C、只有一个叶子节点D、是任意一棵二叉树C课堂练习1第27页/共61页29

2000年西电考研题一棵二叉树的前序、中序和后序序列分别如下，其中一部分未显示出来，试求出空格处的内容，并画出该二叉树。前序序列：

B

F

ICEH

G；中序序列：D

KFIA

EJC

；

后序序列：

K

FBHJ

G

A。ADKJBHGDIEC课堂练习2第28页/共61页30ABCDEFKIJHGABDFKICEHJGDBKFIAHEJCGDKIFBHJEGCA前序遍历序列：中序遍历序列：后序遍历序列：第29页/共61页31课后作业

P252-练习4：绘制表达式的二叉树

P259-练习9：采用数组存储二叉树，实现中序遍历（提示：递归算法）P259-练习17：使用链式堆栈方法，来实现二叉树的前序遍历

（提示：非递归算法；在向左子树遍历之前，先把当前右子树节点压入栈中，以便后面遍历）第30页/共61页328.7抽象数据类型BinaryTreeADTBinaryTree{实例元素集合；如果不空，则被划分为根节点、左子树和右子树；每棵子树仍是一棵二叉树操作

Create()：创建一棵空二叉树

IsEmpty()：如果二叉树为空，returntrue；否则returnfalse；

Root(x)：取根节点x；操作失败，returnfalse，否则returntrue；

MakeTree(root,left,right)：创建一棵二叉树，根节点为root

BreakTree(root,left,right)：拆分二叉树

PreOrder：前序遍历

InOrder：中序遍历

PostOrder：后序遍历

LevelOrder：层次遍历}第31页/共61页33函数指针作为函数的参数intfa(inta){returna+1;}intfb(intb){returnb+2;}intAddFunc(int(*f1)(int),int(*f2)(int),inta,intb){return(*f1)(a)+(*f2)(b);}intmain(){inta=5,b=3;a=AddFunc(fa,fb,a,b);return0;

}returnfa(a)+fb(b);第32页/共61页348.8类BinaryTreetemplate<classT>classBinaryTree{public:BinaryTree(){root=0;};~BinaryTree(){};boolIsEmpty()const{return((root)?false:true);}boolRoot(T&x)const;voidMakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right);voidBreakTree(T&element,BinaryTree<T>&left,BinaryTree<T>&right);第33页/共61页35voidPreOrder(void(*Visit)(BinaryTreeNode<T>*u)){PreOrder(Visit,root);}voidInOrder(void(*Visit)(BinaryTreeNode<T>*u)){InOrder(Visit,root);}voidPostOrder(void(*Visit)(BinaryTreeNode<T>*u)){PostOrder(Visit,root);}voidLevelOrder(void(*Visit)(BinaryTreeNode<T>*u));private:BinaryTreeNode<T>*root;//根节点指针voidPreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);voidInOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);voidPostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);};第34页/共61页36template<classT>boolBinaryTree<T>::Root(T&x)const{if(root){x=root->data;returntrue;}elsereturnfalse;}成员函数Root（取根节点）第35页/共61页37template<classT>voidBinaryTree<T>::MakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right){//将两颗已有子树合并成一棵新树！root=newBinaryTreeNode<T>(element,left.root,right.root);

//子树已经被合并，将其根节点置空！left.root=right.root=0;}成员函数MakeTree（创建树）第36页/共61页38template<classT>voidBinaryTree<T>::BreakTree(T&element,BinaryTree<T>&left,BinaryTree<T>&right){if(!root)throwBadInput();//treeempty

//breakthetreeelement=root->data;left.root=root->LeftChild;right.root=root->RightChild;deleteroot;root=0;}成员函数BreakTree（分解树）第37页/共61页39template<classT>voidBinaryTree<int>::PreOrder(

void(*Visit)(BinaryTreeNode<int>*u),BinaryTreeNode<int>*t){if(t){Visit(t); PreOrder(Visit,t->LeftChild); PreOrder(Visit,t->RightChild);}}

前序遍历PreOrder（private成员函数）时间复杂度Θ(n)第38页/共61页40template<classT>voidBinaryTree<int>::InOrder(

void(*Visit)(BinaryTreeNode<int>*u),BinaryTreeNode<int>*t){if(t){InOrder(Visit,t->LeftChild);Visit(t);InOrder(Visit,t->RightChild);}}

中序遍历InOrder（private成员函数）时间复杂度Θ(n)第39页/共61页41template<classT>voidBinaryTree<int>::PostOrder(

void(*Visit)(BinaryTreeNode<int>*u),BinaryTreeNode<int>*t){if(t){PostOrder(Visit,t->LeftChild);PostOrder(Visit,t->RightChild);Visit(t);}}

后序遍历PostOrder（private成员函数）时间复杂度Θ(n)第40页/共61页42template<classT>voidBinaryTree<int>::LevelOrder(

void(*Visit)(BinaryTreeNode<int>*u)

){LinkedQueue<BinaryTreeNode<int>*>Q;BinaryTreeNode<int>*t;

t=root;while(t){Visit(t);if(t->LeftChild)Q.Add(t->LeftChild);if(t->RightChild)Q.Add(t->RightChild);try{Q.Delete(t);}catch(OutOfBounds){return;}}}

逐层遍历LevelOrder（private成员函数）时间复杂度Θ(n)第41页/共61页43调用示例BinaryTree<int>a,x,y,z;intmain(){y.MakeTree(1,a,a);z.MakeTree(2,a,a);x.MakeTree(3,y,z);y.MakeTree(4,x,a);}1234第42页/共61页448.9抽象数据类型及类的扩充增加二叉树的操作：

PreOutput();//按前序方式输出数据域

InOutput();//按中序方式输出数据域

PostOutput();//按后序方式输出数据域

LevelOutput();//逐层输出数据域

Delete();//删除一棵二叉树，释放其节点

Height();//返回树的高度

Size();//返回树中节点数第43页/共61页45private:staticvoidOuput(BinaryTreeNode<T>*t){cout<<t->data<<‘’;}

8.9.1输出Outputpublic:voidPreOuput(){PreOrder(Output,root);

cout<<endl;}第44页/共61页46public:voidInOuput(){InOrder(Output,root);

cout<<endl;}voidPostOuput(){InOrder(Output,root);

cout<<endl;}voidLevelOuput(){LevelOrder(Output,root);

cout<<endl;}时间复杂度Θ(n)第45页/共61页47public：voidDelete(){PostOrder(Free,root);root=0;}

8.9.2删除Delete通过后序遍历在访问一个节点时，将其删除。private：staticvoidFree(BinaryTreeNode<T>*t){deletet;}时间复杂度Θ(n)第46页/共61页48template<classT>intBinaryTree<T>::Height(BinaryTree<T>*t)const{if(!t)return0;inthl=Height(t->LefChild);inthr=Height(t->RightChild);if(hl>hr)return++hl;elsereturn++hr;}

8.9.3计算高度Height：类似后序遍历树的高度：max{hl,hr}+1时间复杂度Θ(n)第47页/共61页49template<classT>intBinaryTree<T>::Size(BinaryTree<T>*t)const{if(!t)return0;intsl=Size(t->LefChild);intsr=Size(t->RightChild);return(1+sl+sr);}

8.9.4统计节点数Size：类似后序遍历时间复杂度Θ(n)第48页/共61页50int_count=0;//类外定义private:staticvoidAdd1(BinaryTreeNode<T>*t){_count++;}统计节点数另一种方法：在过程中完成第49页/共61页51public:intSize(){_count=0;PreOrder(Add1,root);return_count;}将统计函数作为函数参数传入第50页/共61页52类BinaryTree：调用示例#include<iostream.h>#include"binary.h"//globalsintcount=0;BinaryTree<int>a,x,y,z;template<classT>voidct(BinaryTreeNode<T>*t){count++;}第51页/共61页53intmain(){y.MakeTree(1,a,a);z.MakeTree(2,a,a);x.MakeTree(3,y,z);y.MakeTree(4,x,a);cout<<"Preordersequenceis";y.PreOutput();cout<<"Inordersequenceis";y.InOutput();cout<<"Postordersequenceis";y.PostOutput();cout<<"Levelordersequenceis";y.LevelOutput();cout<<"Numberofnodes=";cout<<y.Size()<<endl;cout<<"Height=";cout<<y.Height()<<endl;y.PreOrder(ct);cout<<"Countofnodesis"<<count<<endl;return0;}Preordersequenceis4312Inordersequenceis1324Postordersequenceis1234Levelordersequenceis4312Numberofnodes=4Height=3Countofnodesis41234第52页/共61页54二叉树遍历的非递归算法

递归算法转换为等价的非递归算法，使用“栈”

以前序为例：根-左-右，左下降abcde思考：如果能在左下降的过程中，记录留待以后访问的右子树的根结点，以便在遍历完一个结点的左子树后能转移到这个结点的右子树，即可实现！第53页/共61页55非递归前序遍历二叉树主要思想：每遇到一个结点，先访问该结点，并把该结点的非空右子结点压入栈中，然后遍历其左子树；当左子树为空时，从栈顶弹出待访问的结点，继续遍历。abcde访问a进栈c左进b访问b进栈d左进空退栈d访问d左进空退栈c访问c左进e访问e左进空退栈cdcc结束第54页/共61页56算法描述voidPreOrder(BinTreeT){stackS;InitStack(&S);//递归工作栈

BinTreeNode*p=T;

Push(&S,NULL);while(p!=NULL){cout<<p->data<<endl;if