叉树的遍历及应用.ppt

数据结构,中国地质大学信息工程学院 2013年秋,第五章 树,3,内容提要,5.1 树的基本概念 5.2 二叉树 5.3 二叉树的存储表示 5.4 二叉树的遍历及其应用 5.6 树与森林 5.7 树与森林的遍历及其应用 5.8 堆及其应用 5.9 Huffman树及其应用,4,5.4 二叉树的遍历,遍历二叉树的定义,二叉树遍历是指按照某种顺序访问二叉树中的每个节点，使每个节点被访问一次，且只被访问一次。,“访问”的含义：是指对节点施行某种操作，操作可以是输出节点信息，修改节点的数据值等，但要求这种访问不破坏它原来的数据结构。,以二叉链表作为二叉树的存储结构。,5,访问操作的示例,例 假设一棵二叉树存储着有关人事方面的信息，每个节点含有姓名、工资等信息。管理和使用这些信息时可能需要作这样一些工作： （1）将每个人的工资提高20%； （2）打印每个人的姓名和工资； （3）求最低工资数额和领取最低工资的人数。,对于（1），访问是对工资值进行修改的操作； 对于（2），访问的含义是打印该节点的信息； 对于（3），访问只是检查和统计。,不管访问的具体操作是什么，都必须做到既无重复，又无遗漏。,6,线性结构与非线性结构遍历的区别,7,树的遍历方式,深度优先遍历：是尽可能地沿分支节点向深度方向进行周游。节点既可以在向下遍历之前访问，也可以在从子树返回之前访问。,广度优先遍历：是按照从上到下、从左到右的顺序进行层次访问节点。,8,深度优先遍历,1、一棵二叉树由三部分组成： 根节点（V）；左子树（L）； 右子树（R）。,2、若规定： L：遍历根节点的左子树 ; R：遍历根节点的右子树； V：访问根节点。,则遍历二叉树有6种方式： VLR LVR LRV VRL RVL RLV,若规定按先左子树后右子树的顺序进行遍历，则有： VLR：前序遍历（先根遍历） LVR：中序遍历（中根遍历） LRV：后序遍历（后根遍历）,演示5-1,9,1.前序遍历,前序遍历的递归定义,若二叉树为空，遍历结束；否则 （1）访问根节点；（V） （2）前序遍历根节点的左子树；（L） （3）前序遍历根节点的右子树。（R）,前序遍历的序列：,A B D G H C E I F,演示5-2,前序序列的第一个元素 必为二叉树的根节点,10,前序遍历的递归算法,template void BinaryTree:PreOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) visit (subTree); /访问根结点 PreOrder (subTree-leftChild, visit); /遍历左子树 PreOrder (subTree-rightChild, visit); /遍历右子树 ,11,2.中序遍历,中序遍历的递归定义,若二叉树为空，遍历结束；否则： （1）中序遍历根节点的左子树；（L） （2）访问根节点；（V） （3）中序遍历根节点的右子树。（R）,中序遍历的序列：,G D H B A E I C F,演示5-3,中序序列的根节点恰为 左右子树的中序序列的分界点,12,中序遍历的递归算法,template void BinaryTree:InOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) InOrder (subTree-leftChild, visit); /遍历左子树 visit (subTree); /访问根结点 InOrder (subTree-rightChild, visit); /遍历右子树 ,13,3.后序遍历,后序遍历的递归定义,若二叉树为空，遍历结束；否则： （1）后序遍历根节点的左子树；（L） （2）后序遍历根节点的右子树。（R） （3）访问根节点；（V）,后序遍历的序列：,G H D B I E F C A,演示 5-4,后序序列的最后一个元素 必为二叉树的根节点,14,后序遍历的递归算法,template void BinaryTree:PostOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t ) if (subTree != NULL ) PostOrder (subTree-leftChild, visit); /遍历左子树 PostOrder (subTree-rightChild, visit); /遍历右子树 visit (subTree); /访问根结点 ,15,4.层次遍历：广度优先遍历,层序遍历的定义,层序遍历是指从二叉树的第1层（根节点）开始，从上至下逐层遍历，在同一层中，则按从左至右的顺序逐个访问。,层序遍历的序列：,A B C D E F G H I,16,层次遍历的算法思想,【思路】在进行层序遍历时，对第i层节点访问后，紧接着对第i+1层节点进行访问，访问的顺序是按照第i层的访问顺序依次访问各节点的左孩子和右孩子。,即：先访问的节点，其左右孩子先访问； 后访问的节点，其左右孩子后访问。, 设置一个队列结构,17,层序遍历从二叉树的根节点开始， 首先将根节点指针入队， 然后从队头取出一个元素，每取出一个元素，执行两个操作：,（1）访问该元素所指节点； （2）若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。,重复以上步骤，直到队列为空。,算法实现步骤,18,A,B,C,D,E,F,G,H,I,层序遍历结果：,A,I,B,C,D,E,F,G,H,层序遍历的演示,19,层序遍历的算法实现,template void BinaryTree: levelOrder (void (*visit) (BinTreeNode *t) Queue * Q; BinTreeNode *p = root; Q.EnQueue (p); while (!Q.IsEmpty () /队列不空 Q.DeQueue (p); /退出一个结点，并访问 visit (p);,20,if (p-leftChild != NULL) Q.EnQueue (p-leftChild); /左孩子入队 if (p-rightChild != NULL) Q.EnQueue (p-rightChild); /右孩子入队 ,21,5.二叉树遍历的应用,后序遍历的应用,template void BinaryTree:destroy (BinTreeNode * subTree) /私有函数: 删除根为subTree的子树 if (subTree != NULL) destroy (subTree-leftChild); /删除左子树 destroy (subTree-rightChild); /删除右子树 delete subTree; /删除根结点 ,22,（1）后序遍历的应用,template int BinaryTree:Size (BinTreeNode * subTree) const /利用后序遍历算法计算二叉树的结点个数 if (subTree = NULL) return 0; /空树 else return 1+Size (subTree-leftChild) + Size (subTree-rightChild); ;,23,后序遍历的应用（续）,template int BinaryTree:Height ( BinTreeNode * subTree) const /利用后序遍历算法计算二叉树的高度或深度 if (subTree = NULL) return 0; /空树高度为0 else int i = Height (subTree-leftChild); int j = Height (subTree-rightChild); return (i j) ? j+1 : i+1; ,24,1、可以把任意一个算术表达式用一棵二叉树表示,表达式的形式： 根节点为操作符； 第一操作数为左子树； 第二操作数为右子树。,例如：表达式a/(b-c)*d+e的二叉树表示为：,（2）遍历表达式二叉树,25,2、对该二叉树分别进行前序、中序和后序遍历，得到以下三种不同形式： （1）前序遍历：+*/a-bcde（前缀表达式，波兰式） （2）中序遍历：a/b-c*d+e（中缀表达式） （3）后序遍历：abc-/d*e+（后缀表达式，逆波兰式）,3、前缀表达式和后缀表达式在编译程序中有着非常重要的作用。,表达式为a/(b-c)*d+e,26,例: 表达式 Exp=a*b+(c-d/e)*f,前缀式：+*ab*-c/def,中缀式：a*b+c-d/e*f,后缀式：ab*cde/-f*+,结论：三种表达方式 VS. 原始表达式,（1）操作数之间的相对次序不变；,（2）运算符的相对次序不同；,（3）中缀式丢失了括号信息，致使运算的次序不确定、无意义。解决方法：定义算符优先级！,27,例: 表达式 Exp=a*b+(c-d/e)*f,前缀式：+*ab*-c/def,（4）前缀式的运算规则为：连续出现的两个操作数和它们之前紧靠它们的运算符构成一个最小表达式；,后缀式：ab*cde/-f*+,（5）后缀式的运算规则为：运算符在式中的顺序恰好为表达式的运算顺序； 每个运算符和它之前出现且紧靠它的两个操作数构成一个最小表达式。,演示 5-5,28,后缀表达式的特点：,后缀表达式与表达式的操作数的先后次序相同，只是运算符的先后次序有所改变，后缀表达式的运算符次序就是其执行次序； 后缀表达式中没有括号（因为括号的作用就是改变运算次序，既然后缀表达式中已经考虑了运算规则，所以就不需要括号了）。,如何从后缀式求值？,例: 表达式 Exp=a*b+(c-d/e)*f，后缀式：ab*cde/-f*+,29,后缀表达式的计算方法：,从左自右依次扫描表达式的各单词： （1）如果是操作数，存入栈中； （2）如果是运算符，就取其前面的两个操作数（从栈中弹出的两个数）进行运算，中间结果同样存入栈中，作为下一个运算的操作数； （3） 如此反复直到表达式处理完毕。,【注意】 第一次弹栈得到的操作数为运算符后的操作数； 第二次弹栈得到的操作数为运算符前的操作数。,ab*cde/-f*+,30,例：表达式A/(B+C*D)-E的后缀式ABCD*+/E-,读入*,C*D-T1,读入+,B+T1-T2,读入E,读入-,T3-E-T4,读入/,A/T2-T3,B,C,D,A,31,（3）前序遍历的应用,template BinTreeNode *BinaryTree:Parent (BinTreeNode *subTree, BinTreeNode *t) / 从结点 subTree 开始, 搜索结点 t 的双亲 if (subTree = NULL) return NULL; if (subTree-leftChild = t | subTree-rightChild = t ) return subTree; /找到, 返回父结点地址 BinTreeNode *p; if (p = Parent (subTree-leftChild, t) != NULL) return p; /递归在左子树中搜索 else return Parent (subTree-rightChild, t); /递归在左子树中搜索 ,32,利用前序遍历-创建二叉树,思想,以递归方式建立二叉树。 输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归, 此值在RefValue中。例如用“”或用“-1”表示字符序列或正整数序列空结点。,33,创建二叉树示例,A B C D E G F ,34,template void BinaryTree:CreateBinTree (ifstream,35,CreateBinTree (in, subTree-leftChild); /递归建立左子树 CreateBinTree (in, subTree-rightChild); /递归建立右子树 else subTree = NULL; /遇到空结点值 /封闭指向空子树的指针 ,36,6.二叉树的非递归遍历,递归算法转换为等价的非递归算法，使用“栈” 以前序为例：根-左-右，左下降,思考：如果能在左下降的过程中，记录留待以后访问的右子树的根结点，以便在遍历完一个结点的左子树后能转移到这个结点的右子树，即可实现！,37,（1) 非递归前序遍历二叉树,主要思想：每遇到一个结点，先访问该结点，并把该结点的非空右子结点压入栈中，然后遍历其左子树；当左子树为空时，从栈顶弹出待访问的结点，继续遍历。,访问 a 进栈 c 左进 b,访问 b 进栈 d 左进 空,退栈 d 访问 d 左进 空,退栈 c 访问 c 左进 e,访问 e 左进 空 退栈 ,结束,38,算法实现,template void BinaryTree: PreOrder (void (*visit) (BinTreeNode *t) ) stack* S; BinTreeNode *p = root; S.Push (NULL); while (p != NULL) visit(p); /访问结点 if (p-rightChild != NULL) S.Push (p-rightChild); /预留右指针在栈中 if (p-leftChild != NULL) p = p-leftChild; /进左子树 else S.Pop(p); /左子树为空 ,39,另一种方法：P204程序5.15 进栈时，非空右孩子结点先进入，非空左孩子结点后进 出栈时，访问顺序刚好满足前序访问,思考：算法有没有其它实现形式？,40,（2) 非递归中序遍历二叉树,主要思想：每遇到一个非空结点就把它压入栈，然后去遍历其左子树；遍历完左子树后，从栈中弹出并访问这个结点，然后再去访问该结点的右子树。,41,算法实现,template void BinaryTree:InOrder (void (*visit) (BinTreeNode *t) stack* S; BinTreeNode *p = root; do while (p != NULL) /遍历指针向左下移动 S.Push (p); /该子树沿途结点进栈 p = p-leftChild; if (!S.IsEmpty() /栈不空时退栈 S.Pop (p); visit (p); /退栈, 访问 p = p-rightChild; /遍历指针进到右子女 while (p != NULL | !S.IsEmpty (); ,42,（3) 非递归后序遍历二叉树,主要思想：每遇到一个非空结点，先把它压入栈，然后去遍历其左子树；遍历完其左子树后，应继续遍历该结点的右子树；遍历完右子树之后，才从栈中弹出并访问这个结点。,后序遍历二叉树：左子树-右子树-当前节点,需要注意：访问某个结点之前，需要知道是否已经访问该结点的右子树，因此需要给结点加一个标志位tag， Left：表示已经进入该结点的左子树 Right：表示已经进入该结点的右子树,43,非递归后序遍历示例,44,算法实现,在后序遍历过程中所用栈的结点定义 template struct stkNode BinTreeNode *ptr; /树结点指针 enum tag L, R; /退栈标记 stkNode (BinTreeNode *N = NULL) : ptr(N), tag(L) /构造函数 ; tag = L, 表示从左子树退回还要遍历右子树; tag = R，表示从右子树退回要访问根结点。,45,算法实现（续）,template void BinaryTree: PostOrder (void (*visit) (BinTreeNode *t) Stack S; stkNode w; BinTreeNode * p = root; /p是遍历指针 do while (p != NULL) w.ptr = p; w.tag = L; S.Push (w); p = p-leftChild; int continue1 = 1; /继续循环标记, 用于R,46,while (continue1 ,47,7.二叉树计数（形态确定）,二叉树遍历的结果是将一个非线性结构中的数据通过访问排列到一个线性序列中。 前序序列：a b d c e 特点是第一个访问的a一定是树根，只要左子树非空，后面紧跟的b 一定是根的左子女， 中序序列：b d a e c 特点是树 根 a 把整个中序分成两部分， a 左侧子序列是根的左子树上 的结点数据，右侧子序列是根 的右子树上的结点数据。,48,结论,由二叉树的前序序列和中序序列可以唯一确定一棵二叉树 由二叉树的中序序列和后序序列可以唯一确定一棵二叉树,49,例：已知一棵二叉树的前序序列和中序序列分别为ABDEGCFH和DBGEACHF，则该二叉树的后序序列为 ，层序序列为 。,DGEBHFCA,ABCDEFGH,ABDEGCFH,DBGEACHF,BDEG,DBGE,EG,GE,CFH,CHF,FH,HF,左子树：,右子树：,50,解答：若二叉树的任意两个节点的值都不相同，则二叉树的前序序列和中序序列可唯一确定一棵二叉树，确定方法如下： （1）根据前序遍历的定义：前序序列的第一个元素必为二叉树的根节点； 根据中序遍历的定义：中序序列的根节点恰为左右子树的中序序列的分界点；根节点前的子序列为左子树的中序序列；根节点后的子序列为右子树的中序序列； （2）根据左子树的中序序列的节点个数，在前序序列中找出左子树的前序序列，剩下的即为右子树的前序序列； （3）然后用相同的办法分别找出左、右子树的根及其左右子树的前序序列和中序序列； （4）依此类推，直至待构造的二叉树的前序序列仅剩一个字母为止。,51,前序：A B D H I E J C F K G L,中序：H D I B E J A F K C L G,A,B,D,H,I,E,J,C,F,G,K,L,H D I B E J,F K C L G,H D I,E J,H,I,J,F K,L G,K,L,？,？