二叉树的遍历及其应用

2021年1月25日发(作者：音乐圈)
优集学院学期论文

二叉树的遍历及其应用

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

关键词：
二叉树，遍历，先序遍历，中序遍历，后序遍历

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

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

are
three
ways
in
which
you
can
traverse
a
binary

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
引言

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

1
遍历二叉树的概念

所谓遍历二 叉树，
就是遵从某种次序，
访问二叉树中的所有结点，
使得每个结点仅被访
问 一次。
这里提到的“访问”是指对结点施行某种操作，
操作可以是输出结点信息，
修改 结
点的数据值等，
但要求这种访问不破坏它原来的数据结构。
在本文中，
我们 规定访问是输出
结点信息
data
，且以二叉链表作为二叉树的存贮结构。由于二叉树 是一种非线性结构，每
个结点可能有一个以上的直接后继，因此，必须规定遍历的规则
,
并按此规则遍历二叉树
,
最后得到二叉树所有结点的一个线性序列
。

[1]
2
二叉树遍历的算法

二叉树的遍历方式有三种：中序遍历、前序遍历、后序遍历。

1
、中序遍历的递归算法定义：


1
优集学院学期论文

若二叉树非空，则依次执行如下操作：

(1)
遍历左子树；

(2)
访问根结点；

(3)
遍历右子树。

首先，先确定根结点（
A
）及其左右子树（< br>B
）、（
C
），按照中序遍历
LTR
的顺序，任
一 节结点在以其为根的子树中的访问顺序为左子树、根结点、右子树。而对于以
B
、
C
为根
结点的两个子树，还可继续将其拆分为左、右子树，按左中右的顺序，
遍历左子树 直到其只
有一个结点或为空为止，然后遍历右子树，直到其右子树只有一个结点或为空为止
。此 步
骤可借助图
1
来讲解。

[3]

编程时，可以用如下代码：



public void preorder(Node ptr)
{




if (ROOT==null)





{










ine(










return;






}




if(ptf!=null)





{










ine( +













preorder();










preorder();






}
}
2
、先序遍历的递归算法定义：


2
优集学院学期论文

若二叉树非空，则依次执行如下操作：

(1)
访问根结点；

(2)
遍历左子树；

(3)
遍历右子树。

编程时，可以用如下代码：



public void inorder(Node ptr)
{




if (ROOT==null)





{










ine(










return;






}




if(ptf!=null)





{










inorder();










ine( +













inorder();






}
}
3
、后序遍历得递归算法定义：

若二叉树非空，则依次执行如下操作：

(1)
遍历左子树；

(2)
遍历右子树；

(3)
访问根结点

编程时，可以用如下代码：



public void postorder(Node ptr)
{




if (ROOT==null)





{










ine(










return;






}




if(ptf!=null)





{










postorder();










postorder();










ine( +




3