二叉树的遍历及其应用

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

1、优集学院学期论文二叉树的遍历及其应用摘要：二叉树是一种特殊的树，它在计算机科学领域提供了大量的实际应用。二叉树依照需求可以通过阵列以及链接链表来实现。树的遍历是指一次访问树的所有节点的过程。遍历二叉树有三种方式，分别是先序遍历，中序遍历，后序遍历。在遍历的过程中更加深入的了解二叉树遍历的算法过程及其应用，以至于充分的认识到二叉树遍历的优越性。关键词：二叉树，遍历，先序遍历，中序遍历，后序遍历TraversingabinarytreeanditsapplicationAbstract:Abinarytreeisaspecialt

2、ypeoftreethatoffersalotofpracticalapplicationsinthefieldofcomputerscience.Binarytreescanbeimplementedbyusingarraysaswellaslinkedlists,dependingupontherequirements.Traversingatreereferstotheprocessofvisitingallthenodesofthetreeonce.Therearethreewaysinwhichyoucantrave

3、rseabinarytree.Theyareinorder,preorder,andpostordertraversal.Intheprocessofbinary,Ideeplyrealisethearithmeticprocessandtheapplianceofbinary.Ialsorealisethesuperiorityoftraversingabinarytree.Keywords:binarytree;traversal;inordertraversal;preordertraversal;postordertr

4、aversal0引言所谓遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历在二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。二叉树作为一种重要的数据结构是工农业应用与开发的重要工具。遍历是二叉树算法设计中经典且永恒的话题。经典的算法大多采用递归搜索。递归算法具有简练、清晰等优点，但因其执行过程涉及到大量的堆栈使用，难于应用到一些严格限制堆栈使用的系统，也无法应用到一些不支持递归的语言环境[9]。1遍历二叉树的概念所谓遍历二叉树，就是遵从某种次序，访问二叉树

5、中的所有结点，使得每个结点仅被访问一次。这里提到的“访问”是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。在本文中，我们规定访问是输出结点信息data，且以二叉链表作为二叉树的存贮结构。由于二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此，必须规定遍历的规则,并按此规则遍历二叉树,最后得到二叉树所有结点的一个线性序列[1]。2二叉树遍历的算法二叉树的遍历方式有三种：中序遍历、前序遍历、后序遍历。1、中序遍历的递归算法定义：7优集学院学期论文若二叉树非空，则

6、依次执行如下操作：(1)遍历左子树；(2)访问根结点；(3)遍历右子树。首先，先确定根结点（A）及其左右子树（B）、（C），按照中序遍历LTR的顺序，任一节结点在以其为根的子树中的访问顺序为左子树、根结点、右子树。而对于以B、C为根结点的两个子树，还可继续将其拆分为左、右子树，按左中右的顺序，遍历左子树直到其只有一个结点或为空为止，然后遍历右子树，直到其右子树只有一个结点或为空为止[3]。此步骤可借助图1来讲解。编程时，可以用如下代码：publicvoidpreorder(Nodeptr){if(ROOT==null){Con

7、sole.Writeline("Treeisempty");return;}if(ptf!=null){Console.Writeline(ptr.info+"");preorder(ptr.lchild);preorder(ptr.rchild);}}2、先序遍历的递归算法定义：7优集学院学期论文若二叉树非空，则依次执行如下操作：(1)访问根结点；(2)遍历左子树；(3)遍历右子树。编程时，可以用如下代码：publicvoidinorder(Nodeptr){if(ROOT==null){Console.Writeline(

8、"Treeisempty");return;}if(ptf!=null){inorder(ptr.lchild);Console.Writeline(ptr.info+"");inorder(ptr.rchild);}}3、后序遍历得递归算法定义：若二叉树非空，则依次执行如下