第四节 二叉树的遍历
一、树的存储结构
1.顺序存储结构
将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括
⑴ 一个数据域（data）；
⑵ 三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。 满二叉树和完全二叉树一般采用顺序存储结构。
| |
|
Const
m=树中结点数上限；
Type
node=record{结点类型}
data：<数据类型>；{数据值}
prt，lch，rch：0‥m； {父结点、左儿子、右儿子编号}
end；
treetype=array[1‥m] of node；{二叉树的顺序表类型}
Var
Tree：treetype；{二叉树}
|
|
2.链式存储结构
对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：
⑴ 值域： data
⑵ 左指针域：lch
⑶ 右指针域：rch
这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点
| |
Type
bitrpetr=^node；{结点指针类型}
node=record{结点类型}
data：<数据类型>；{值域}
lch，rch：bitreptr；{左指针域和右指针域}
end；
Var
bt：bitreptr；{头指针}
|
|
二、二叉树的遍历
1.二叉树遍历的定义
按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。
2.二叉树遍历的顺序
如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。
以下遍历以该树为例
三、前序遍历
规则如下：
若二叉树为空，则退出。否则
⑴ 访问处理根结点；
⑵ 前序遍历左子树；
⑶ 前序遍历右子树；
如上图的前序遍历结果为 a b d e h i c f g
|
顺序结构:
Procedue preorder(i:integer);
begin
if i<>0
then begin
访问处理tree[i].data;
preorder(tree[i].lch);{递归遍历左子树}
preorder(tree[i].rch);{递归遍历右子树}
end;
end;
|
链式结构:
Procedue preorder(bt:bitreptr);
begin
if bt<>nil
then begin
访问处理bt^.data;
preorder(bt^.lch);{递归遍历左子树}
preorder(bt^.rch);{递归遍历右子树}
end;
end;
|
四、中序遍历
规则如下：
若二叉树为空，则退出；否则
⑴ 中序遍历左子树；
⑵ 访问处理根结点；
⑶ 中序遍历右子树；
如上图的中序遍历结果为 d b h e i a f c g
|
顺序结构:
Procedue inorder(i:integer);
begin
if i<>0
then begin
inorder(tree[i].lch);{递归遍历左子树}
访问处理tree[i].data;
inorder(tree[i].rch);{递归遍历右子树}
end;
end;
|
链式结构:
Procedue inorder(bt:bitreptr);
begin
if bt<>nil
then begin
inorder(bt^.lch);{递归遍历左子树}
访问处理bt^.data;
inorder(bt^.rch);{递归遍历右子树}
end;
end;
|
五、后序遍历
规则如下：
若二叉树为空，则退出；否则
⑴ 后序遍历左子树；
⑵ 后序遍历右子树；
⑶ 访问处理根结点；
如上图的后序遍历结果为 d h i e b f g c a
|
顺序结构:
Procedue postorder(i:integer);
begin
if i<>0
then begin
postorder(tree[i].lch);{递归遍历左子树}
postorder(tree[i].rch);{递归遍历右子树}
访问处理tree[i].data;
end;
end;
|
链式结构:
Procedue postorder(bt:bitreptr);
begin
if bt<>nil
then begin
postorder(bt^.lch);{递归遍历左子树}
postorder(bt^.rch);{递归遍历右子树}
访问处理bt^.data;
end;
end;
|
|