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

二叉树的遍历及其应用 二叉树的遍历及其应用 摘要：二叉树是一种特殊的树，它在计算机科学领域提供了大量的实际应用。二叉树依照需求可以通过阵列以及链接链表来实现。树的遍历是指一次访问树的所有节点的过程。遍历二叉树有三种方式，分别是先序遍历，中序遍历，后序遍历。在遍历的过程中更加深入的了解二叉树遍历的算法过程及其应用，以至于充分的认识到二叉树遍历的优越性 关键词：二叉树，遍历，先序遍历，中序遍历，后序遍历 Traversing a binary tree and its application Abstract: 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 traversal 目录 0 引言 1 遍历二叉树的概念 2 二叉树遍历的算法 3 二叉树的遍历还原研究 4二叉树的遍历的应用 5总结语 0 引言 所谓遍历，是指沿着某条有哪些信誉好的足球投注网站路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历在二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。二叉树作为一种重要的数据结构是工农业应用与开发的重要工具。遍历是二叉树算法设计中经典且永恒的话题。经典的算法大多采用递归有哪些信誉好的足球投注网站。递归算法具有简练、清晰等优点，但因其执行过程涉及到大量的堆栈使用，难于应用到一些严格限制堆栈使用的系统，也无法应用到一些不支持递归的语言环境。 1遍历二叉树的概念 所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。这里提到的“访问”是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。 2二叉树遍历的算法 二叉树的遍历方式有三种：中序遍历、前序遍历、后序遍历。 中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树;(2)访问根结点;(3)遍历右子树。 先序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1) 访问根结点;(2)遍历左子树;(3) 遍历右子树。 后序遍历得递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树；(2)遍历右子树；(3)访问根结点 3二叉树的遍历还原研究 由先序序列和中序序列来还原二叉树的过程算法思想： （1）若二叉树空，返回空； （2）若不空，取先序序列第一个元素，建立根节点； （3）在中序序列中查找根节点，以此来确定左右子树的先序序列和中序序列； （4）递归调用自己，建左子树； （5）递归调用自己，建右子树。 4二叉树的遍历的应用 根据二叉树的遍历算法, 可得出如下规律: 规律1: 前序序列遍历第一个为根结点, 后序遍历的最后一个结点为根结点。 规律2: 前序序列遍历最后一个为根结点右子树的最右叶子结点, 中序遍历的最后一个结点为根结点右子树的最右叶子结点。 规律3: 中序序列遍历第一个结点为根结点左子树的最左叶子结点, 后序遍历的第一个结点为根结点左子树的最左叶子结点。 5总结语 二叉树在计算机科学中有着重要的作用, 现实世界中有好多问题都是用树这种数据结构描述的, 而二叉树在计算机中操作和实现都非常方便。二叉树在计算机领域应用很广泛，二叉树的遍历又是最基础的操作，所以对