二叉树的遍历及其应用.doc

优集学院学期论文二叉树的遍历及其应用摘要：二叉树是一种特殊的树，它在计算机科学领域提供了大量的实际应用。二叉树依照需求可以通过阵列以及链接链表来实现。树的遍历是指一次访问树的所有节点的过程。遍历二叉树有三种方式，分别是先序遍历，中序遍历，后序遍历。在遍历的过程中更加深入的了解二叉树遍历的算法过程及其应用，以至于充分的认识到二叉树遍历的优越性。关键词：二叉树，遍历，先序遍历，中序遍历，后序遍历Traversing a binary tree and its applicationAbstract:A binary tree is a special type of tree that offers a lot of practical applications in the field of computer science.Binary trees can be implemented by using arrays as well as linked lists,depending upon the requirements. Traversing a tree refers to the process of visiting all the nodes of the tree once.There are three ways in which you can traverse a binary tree.They are inorder,preorder,and postorder traversal. In the process of binary,I deeply realise the arithmetic process and theappliance of binary.I also realise the superiority of traversing a binary tree. Key words:binary tree; traversal;inorder traversal; preorder traversal; postorder traversal0引言所谓遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历在二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。二叉树作为一种重要的数据结构是工农业应用与开发的重要工具。遍历是二叉树算法设计中经典且永恒的话题。经典的算法大多采用递归搜索。递归算法具有简练、清晰等优点，但因其执行过程涉及到大量的堆栈使用，难于应用到一些严格限制堆栈使用的系统，也无法应用到一些不支持递归的语言环境9。1遍历二叉树的概念所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。这里提到的“访问”是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。在本文中，我们规定访问是输出结点信息data，且以二叉链表作为二叉树的存贮结构。由于二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此，必须规定遍历的规则,并按此规则遍历二叉树,最后得到二叉树所有结点的一个线性序列1。 2二叉树遍历的算法二叉树的遍历方式有三种：中序遍历、前序遍历、后序遍历。1、中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)访问根结点； (3)遍历右子树。首先，先确定根结点（A）及其左右子树（B）、（C），按照中序遍历LTR 的顺序，任一节结点在以其为根的子树中的访问顺序为左子树、根结点、右子树。而对于以B、C 为根结点的两个子树，还可继续将其拆分为左、右子树，按左中右的顺序，遍历左子树直到其只有一个结点或为空为止，然后遍历右子树，直到其右子树只有一个结点或为空为止3。此步骤可借助图1 来讲解。编程时，可以用如下代码： public void preorder(Node ptr) if (ROOT=null) Console.Writeline(Tree is empty); return; if(ptf!=null) Console.Writeline( + ); preorder(ptr.lchild); preorder(ptr.rchild); 2、先序遍历的递归算法定义：若二叉树非空，则依次执行如下操作： (1) 访问根结点； (2) 遍历左子树； (3) 遍历右子树。编程时，可以用如下代码： public void inorder(Node ptr) if (ROOT=null) Console.Writeline(Tree is empty); return; if(ptf!=null) inorder(ptr.lchild); Console.Writeline( + ); inorder(ptr.rchild); 3、后序遍历得递归算法定义：若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)遍历右子树； (3)访问根结点编程时，可以用如下代码： public void postorder(Node ptr) if (ROOT=null) Console.Writeline(Tree is empty); return; if(ptf!=null) postorder(ptr.lchild); postorder(ptr.rchild); Console.Writeline( + ); 3二叉树的遍历还原研究通过先序遍历序列和中序遍历序列来确定二叉树的方法：从先序遍历序列的最左边找出并画出根结点。在中序遍历序列中，找到这个根结点，并以此根结点为界，根节点左边是其左子树的中序遍历序列，右边是其右子树的中序遍历序列，因此我们确定了其左子树上的节点，右子树上的节点，并记下来相应节点。再从先序遍历中找到这些左子树上节点，最左边的节点就是其左子树上的根节点，找到右子树上的节点，最左边的节点即是其右子树上的节点。根据第3步找到的左右子树根节点在中序遍历中利用第2步的方法来确定子树的左右子树，如此这般，一步一步找到根节点画出来，直到所有的结点全部画完。即从先序序列确定根节点，再从中序序列来判断左右子树4。已知先序序列BEFCGDH，中序序列FEBGCHD，确定对应二叉树6。根据先序序列知道B为根节点。从中序序列得出F、E为以B为根节点的左子树上节点，B右边的节点G、C、H、D即为以B为根节点的右子树上节点。找到F、E和G、C、H、D在先序序列中的位置，最左边的即为子树的根节点。我们可以看到在先序序列中E在F的左边，所以E是左子树的根节点，C在G、D、H的最左边，所以C是右子树的根节点。从中序序列找到E和C节点，F在E的左边判断出F是E的左子树，G是C的左子树上节点，H、D是右子树节点。未能确定的还有H、D，从先序序列找到H、D得出D在左边所以是根节点，再从中序序列找到D，可以判断出H是D的左子树，因此我们得出这棵二叉树如图2所示。由先序序列和中序序列来还原二叉树的过程算法思想7：（1）若二叉树空，返回空；（2）若不空，取先序序列第一个元素，建立根节点；（3）在中序序列中查找根节点，以此来确定左右子树的先序序列和中序序列；（4）递归调用自己，建左子树；（5）递归调用自己，建右子树。4二叉树的遍历的应用根据二叉树的遍历算法, 可得出如下规律:规律1: 前序序列遍历第一个为根结点, 后序遍历的最后一个结点为根结点。规律2: 前序序列遍历最后一个为根结点右子树的最右叶子结点, 中序遍历的最后一个结点为根结点右子树的最右叶子结点。规律3: 中序序列遍历第一个结点为根结点左子树的最左叶子结点, 后序遍历的第一个结点为根结点左子树的最左叶子结点。由上述规律我们得出如下推论:（1）先序遍历序列和中序遍历序列可以唯一确定一棵二叉树5。证明：a、 如果先序遍历序列和中序遍历序列都是空, 则该二叉树是空树, 而空二叉树是唯一的。b、如果先序遍历序列和中序遍历序列中都只有一个结点,那么该二叉树是只有一个结点的二叉树, 而只有一个结点的二叉树也是唯一的。c、其它的情况, 设少于n( n 2) 个结点的二叉树可由先序遍历序列和中序遍历序列唯一确定。则对于有n 个结点的二叉树, 先序遍历序列中的第一个结点必然是该二叉树的根结点, 然后在中序遍历序中找到根结点, 故根结点可以唯一确定。在中序遍列序列中根结点前面的结点序列就是根结点左子树的中序遍历序列, 在先序遍历序列中根结点后面的属于中序遍历序列中根结点前面的那些结点组成序列就是根结点左子树的先序遍历序列, 因为根结点的左子树至少比原二叉树少一个结点, 所以根据归纳假设可知根结点的左子树是唯一的: 原中序序列中根结点后面的结点序列就是根结点右子树的中序序列, 原先序序列中去掉左子树先序序列后剩下的结点序列就是根结点右子树的先序序列, 根结点的右子树至少比原二叉树少一个结点, 根据归纳假设可知根结点的右子树也是唯一的. 所以对于有n 个结点的二叉树也可由先序遍历序列和中序遍历序列唯一确定。由 a、b、c可知对于任意个结点的二叉树都可由先序遍历序列和中序遍历序列唯一确定4。（2）先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。下面我们用一个反例证明它。如图3所示的两棵二叉树:对于二叉树（1） , 它的先序遍历序列是: AB，它的后序遍历序列是: BA；对于二叉树（2） , 它的先序遍历序列也是: AB, 它的后序遍历序列也是: BA, 但是这两棵二叉树是不同的两棵二叉树, 因为二叉树是位置树, 对于一个结点的两个子树要分别指明哪个是左子树, 哪个是右子树, 左右子树不能任意交换。（3）单独由中序遍历序列也不能唯一确定一棵二叉树。下面我们也用一个反例证明它。如图4所示的两棵二叉树:对于二叉树（1） , 它的中序遍历序列是: ABC; 对于二叉树（2）, 它的中序遍历序列也是: ABC , 这显然不是同一棵二叉树但它们却有相同的中序遍历序列。5总结语二叉树在计算机科学中有着重要的作用, 现实世界中有好多问题都是用树这种数据结构描述的, 而二叉树在计算机中操作和实现都非常方便。二叉树在计算机领域应用很广泛，二叉树的遍历又是最基础的操作，所以对二叉树遍历方法的研究就更为重要。通过对遍历方法的研究进一步实现了二叉树的还原，在相关的二叉树遍历的应用中起到重要作用8。现实世界中多种问题都可归纳成为树和森林的模型，而树和森林又可以用二叉链表作媒介同二叉树进行相互转换，因此，学好二叉树对学习程序设计、利用计算机解决实际问题特别重要；二叉树的各种复杂运算大都是建立在其三种遍历之上的，因此，掌握好二叉树的遍历算法是极有必要的。参考文献：1 严蔚敏,吴伟民.数据结构（C 语言版）M.北京:清华大学出版社,1997:121-1312 王若梅，贺晓军. 数据结构M. 西安：西安电子科技大学出版社，1994, 80109.3 娄定俊. 算法分析与设计M. 中山大学计算机科学系，1998.4 李春葆.数据结构习题与解析M.2 版.北京:清华大学出版社,2004:3115谭浩强,张基温.c/c+语言程序设计教程M. 北京:高等教育出版社,2001.6 耿国华编