二叉树的遍历操作.doc

二叉树的遍历操作
摘要:二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,掌握二叉树的遍历对于二叉树的学习有重要作用。
关键词:二叉树;遍历
Binary Tree Traversal
Abstract: The binary tree is an important type of tree structure. Many practical problems in abstract data structures are often in the form of a binary tree, general tree can be simply converted to a binary tree and binary tree storage structure and its algorithms are relatively simple, master binary tree traversal important role for the binary tree learning .
Key Words:Binary Tree;Traversal
0引言
先序遍历中序遍历后序遍历还原二叉树引言二叉树是数据结构非常重要的一种非线性结构,是树型结构的一种特殊形式,在计算机处理领域有着广泛的应用。
1 概述
二叉树遍历的背景与意义
现实世界中很多问题都可归纳为树的模型,在树这种数据结构中,所有数据元素之间的关系具有明显的层次特性。其中以树和二叉树最为常用,它可以很好地描述客观世界中广泛存在的具有分支关系或层次特性的对象,因此在计算机领域有着广泛应用,如操作系统中的文件件管理、编译程序中的语法结构和数据库系统信息组织形式等。
二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树对学习程序设计、利用计算机解决实际问题特别重要。二叉树的各种复杂运算大都是建立在其三种遍历之上,因此掌握好二叉树的遍历算法是很有必要的。

树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用,如在编译源程序时,可用树表示源程序的语法结构。又如在数据库系统中,树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述[1] 。
树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前驱。以下具体地给出树的定义及树的数据结构表示。
2 二叉树
二叉树的定义
在计算机科学中,树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作
“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。值得注