Chapter5二叉树的遍历及应用

《Chapter5二叉树的遍历及应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构中国地质大学信息工程学院2012年秋第五章树3内容提要5.1树的基本概念5.2二叉树5.3二叉树的存储表示5.4二叉树的遍历及其应用5.6树与森林5.7树与森林的遍历及其应用5.8堆及其应用5.9Huffman树及其应用45.4二叉树的遍历遍历二叉树的定义二叉树遍历是指按照某种顺序访问二叉树中的每个节点，使每个节点被访问一次，且只被访问一次。“访问”的含义：是指对节点施行某种操作，操作可以是输出节点信息，修改节点的数据值等，但要求这种访问不破坏它原来的数据结构。以二叉链表作为二叉树的存储结构。5访问操作的示例例假设一棵二叉树存储着有

2、关人事方面的信息，每个节点含有姓名、工资等信息。管理和使用这些信息时可能需要作这样一些工作：（1）将每个人的工资提高20%；（2）打印每个人的姓名和工资；（3）求最低工资数额和领取最低工资的人数。对于（1），访问是对工资值进行修改的操作；对于（2），访问的含义是打印该节点的信息；对于（3），访问只是检查和统计。不管访问的具体操作是什么，都必须做到既无重复，又无遗漏。6线性结构与非线性结构遍历的区别线性结构的遍历非线性结构的遍历只要按照结构原有的线性顺序，从第一个元素起依次访问各元素即可。每个节点可能有一个以上的直接后继；必须规定遍历的规则，

3、并按此规则遍历二叉树；最后得到二叉树所有节点的一个线性序列。7树的遍历方式深度优先遍历：是尽可能地沿分支节点向深度方向进行周游。节点既可以在向下遍历之前访问，也可以在从子树返回之前访问。广度优先遍历：是按照从上到下、从左到右的顺序进行层次访问节点。ABEHJDLIKCGFM8深度优先遍历1、一棵二叉树由三部分组成：根节点（V）；左子树（L）；右子树（R）。VLR2、若规定：L：遍历根节点的左子树;R：遍历根节点的右子树；V：访问根节点。则遍历二叉树有6种方式：VLRLVRLRVVRLRVLRLV若规定按先左子树后右子树的顺序进行遍历，则有：

4、VLR：前序遍历（先根遍历）LVR：中序遍历（中根遍历）LRV：后序遍历（后根遍历）演示5-191.前序遍历前序遍历的递归定义若二叉树为空，遍历结束；否则（1）访问根节点；（V）（2）前序遍历根节点的左子树；（L）（3）前序遍历根节点的右子树。（R）ABDEFCHIG前序遍历的序列：ABDGHCEIF演示5-2前序序列的第一个元素必为二叉树的根节点10前序遍历的递归算法templatevoidBinaryTree::PreOrder(BinTreeNode*subTree,void(*visit)(BinTree

5、Node*t)){if(subTree!=NULL){visit(subTree);//访问根结点PreOrder(subTree->leftChild,visit);//遍历左子树PreOrder(subTree->rightChild,visit);//遍历右子树}}112.中序遍历中序遍历的递归定义若二叉树为空，遍历结束；否则：（1）中序遍历根节点的左子树；（L）（2）访问根节点；（V）（3）中序遍历根节点的右子树。（R）ABDEFCHIG中序遍历的序列：GDHBAEICF演示5-3中序序列的根节点恰为左右子树的中序序列的分界点

6、12中序遍历的递归算法templatevoidBinaryTree::InOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t)){if(subTree!=NULL){InOrder(subTree->leftChild,visit);//遍历左子树visit(subTree);//访问根结点InOrder(subTree->rightChild,visit);//遍历右子树}}133.后序遍历后序遍历的递归定义若二叉树为空，遍历结束；否则：（1）后序遍历

7、根节点的左子树；（L）（2）后序遍历根节点的右子树。（R）（3）访问根节点；（V）ABDEFCHIG后序遍历的序列：GHDBIEFCA演示5-4后序序列的最后一个元素必为二叉树的根节点14后序遍历的递归算法templatevoidBinaryTree::PostOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t){if(subTree!=NULL){PostOrder(subTree->leftChild,visit);//遍历左子树PostOrder(

8、subTree->rightChild,visit);//遍历右子树visit(subTree);//访问根结点}}155.二叉树遍历的应用后序遍历的应用template