数据结构
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第五章 树
★ 基本术语
★ 树的基本操作和存储结构
★ 二叉树
North China Electric Power University
★ 二叉树的遍历及线索二叉树
★ 树的遍历
★ 哈夫曼树及其应用
★ 基本术语
North China Electric Power University
树型结构是一类重要的非线性数据结构，其中以二叉树最为常用。树是以分支关系定义的层次结构，它为计算机应用中出现的具有层次关系或分支关系的数据提供了一种自然的表示方法。用树结构描述的信息模型在客观世界普遍存在。
计算机科学与工程系办公室 教研室 实验室 研究室行政办公室总支办公室计算机教研室软件教研室软件实验室综合实验室数字逻辑实验室组成原理试验室管理信息系统研究室知识工程研究室微机应用研究室
North China Electric Power University
树的定义,树是 n(n≥ 0)个结点的有限集 T,在一棵非空树中：
1)有且仅有一个特定的称为根的结点；
2)当 n>1时,其余结点可分为 m(m>0)个互不相交的有限集合 T1,T2,…,Tm,其中每个集合本身又是一棵树，并且称为根的子树。
树的定义可以用如下形式化描述来表示：
Tree=(D,R)
其中,D是具有相同特性的数据元素的集合 ;若 D只含有一个元素,则 R为空集,否则 R是 D上的某个二元关系 H
的集合,即 R={H},H为如下描述的二元关系,
树的几种表示方法,
1)有且仅有一个结点没有前驱，该结点被称为树的根；
2)除树根结点外，其余每个结点有且仅有一个前驱结点；
3)包含树根结点在内的每个结点，可以有任意多个 (包含
0个 )后继。
A
B C D
E F G H I J
K L M
1)二元组表示
D={A,B,C,D,E,F,G,H,I,J,K,L,M}
R={<A,B>,<A,C>,<A,D>,
<B,E>,<B,F>,<C,G>,<D,H>,
<D,I>,<D,J>,<F,K>,<F,L>,
<J,M>}
North China Electric Power University
4) 广义表表示法,A(B(E,F(K,L)),C(G),D(H,I,J(M)))
A
BE
K LF
C G
H
I
M
D
J
2)集合图表示 3)凹入表表示
North China Electric Power University
树型结构和线性结构的比较树型结构 线性结构根结点无前驱结点 第一个数据元素无前驱多个叶子结点无后继 最后一个数据元素无后继其它数据元素有一个前驱和多个后继其它元素有且仅有一个直接前驱和一个直接后继
North China Electric Power University
树中的基本术语,A
B C D
E F G H I J
K L M
1.结点、结点的度、树的度
2.叶子结点、分支结点
3.孩子、双亲、兄弟、
堂兄弟、祖先、子孙
4.结点的层次、树的深度
5.有序树和无序树
6.森林
B C D
E F G H I J
K L M
North China Electric Power University
树的性质,
性质 1:树中的结点数等于所有结点的度加 1。 A
B C D
E F G H I J
K L M
证明：除树的根结点外每个结点有且只有一个直接前驱，除树的根结点之外的结点数等于所有结点的分支数。
性质 2:度为 k的树中第 i层至多有 ki-1个结点。
性质 3:深度为 h的 k叉树至多有 (kh-1)/(k-1)个结点。
性质 4:具有 n个结点的 k叉树的最小深度为 logk(n(k-1)+1) 。
North China Electric Power University
★ 树的基本操作和存储结构树的基本运算
1.Root(T):求树 T的根结点，若 T为空则返回结果为“空”。
2.Parent(T,x):求结点 x在树 T上的双亲结点，若结点 x是树 T的根结点或 x不在树 T中，则返回结果为“空”。
3.Initiate(T):置 T为空树。
4.Child(T,x,i):求树 T上结点 x的第 i个孩子，若 x不在树 T上或 x
没有第 i个孩子，则返回结果为“空”。
5.Create(x,T1,T2,…,T k):建立一棵以 x为根，以 T1,T2,…,T k为第 1,2,
3…,k 棵子树的树。
6.Delete(T,x,i):删除树 T上结点 x的第 i棵子树，若结点 x无第 i棵子树，则为空操作。
7.Traverse(T):按某个次序依次访问树中的各个结点，并使每个结点只被访问一次。
North China Electric Power University
树的存储结构
1.孩子表示法由于树中每个结点可能有多棵子树，可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，则结点形式有如下两种：
data child1 child2 childd…
data child1 child2 childd…degree
在第一种形式中，结点是同构的，存储空间浪费较大，
在第二种形式中，结点是不同构的，虽能节约存储空间，但实现和运算很不方便。
(1)
(2)
North China Electric Power University
可以把每个结点的孩子结点排列起来，看成一个线性表，
且以单链表作存储结构,n个结点有 n个孩子链表,n个头指针又组成一个线性表，为了便于查找，可用向量表示。
Type link=↑ node;
node=record
child:ElemType;
next:link;
end;
tree=Array[1..maxn] of link;
1
2 3
4 5 6
2 3
4 5
6
^
^
1
2
3
4
5
6
^
^
^
^
2 3
4 5
6
^
^
1
2
3
4
5
6
0
1
1
2
2
2
^
^
^
^
North China Electric Power University
2.孩子兄弟表示法又称二叉链表表示法，即以二叉链表作树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为 first-child和 nextsibling。
data first-child nextsibling
1
2 3
4 5 6
1
2 3
4 5 6
^
^^
^ ^ ^^
在孩子兄弟表示法中，要找结点 x的第 i个孩子,则只要先从
first-child域找到第一个孩子结点上，然后沿着该孩子结点的
nextsibling域连续走 i-1步，便可找到 x的第 i个孩子。
North China Electric Power University
3.双亲表示法用一个数组顺序地存放树的各个结点，结点存放的顺序是任意的。每一结点有两个域组成：数据域和指针域，分别存储树上结点中的数据元素和用于指示本结点之双亲所在的存储结点。
指针域的类型定义有两种：高级语言中的指针类型和整型或子界类型，与之对应的链表分别称为动态链表和静态链表。
静态双亲链表的定义：
const size={结点数 };
Type node=record
data:ElemType;
parent:0..size;
end;
stalist=array[1..size] of node;
1
2 3
4 5 6
^1
2
3
4
5
6
1
3
2
4
5
6
data parent
0
1
1
3
3
3
结点序号
North China Electric Power University
★ 二叉树二叉树是一种重要的数据结构类型，它有许多良好的性质和简单的物理表示，它的特点是最多有两个孩子，并且二叉树的子树有左右之分，且其子树的顺序不能任意颠倒。
二叉树的定义二叉树是有 n(n≥0) 个结点的有限集合，此集合或者是空的，或者是由一个根结点加上两棵分别称为左右子树的、互不相交的二叉树组成。
注意,二叉树和树是两个不同的概念，树的子树不必区分其次序，而二叉树的子树有左右之分，另外，二叉树也不能简单地看成是一有序树，因为只有一棵子树时，无法区分其次序。
North China Electric Power University
二叉树的基本形态：
(空 ) 根 根左子树根右子树根左子树右子树具有三个结点的二叉树具有以下五种基本形态：
North China Electric Power University
两种特殊形态的二叉树若一棵二叉树中的结点,
或者为叶结点,或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层,这样的二叉树为满二叉树,
1,满二叉树若一棵二叉树中只有最下面两层的结点的度可以小于 2,
并且最下面一层的结点 (叶结点 )都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树,
2.完全二叉树
North China Electric Power University
1,一棵非空二叉树的第 i 层最多有 2i–1个结点 (i?1)。
证明 (采用归纳法 )
(1).当 i=1时,结论显然正确。非空二叉树的第 1层有且仅有一个结点,即树的根结点,
(2).假设对于第 j层 (1?j?i–1)结论也正确,即第 j层最多有 2j-1个结点,
(3).由定义可知,二叉树中每个结点最多只能有两个孩子结点。若第 i–1层的每个结点都有两棵非空子树,则第 i层的结点数目达到最大,而第 i–1层最多有 2i–2个结点已由假设证明,于是,应有
2?2i–2 = 2i–1证毕,
二叉树的性质
North China Electric Power University
2,深度为 h 的非空二叉树最多有 2h -1个结点,
证明,
由性质 1可知,若深度为 h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。即有
20+21+22+…+2 i-1+ …+2 h-1 = 2h-1
证毕,
华电计算机系
North China Electric Power University
3,若非空二叉树有 n0个叶结点,有 n2个度为 2的结点,
则 n0=n2+1
证明,
设该二叉树有 n1个度为 1的结点,结点总数为 n,有
n=n0+n1+n2 --------(1)
设二叉树的分支数目为 B,有
B=n-1 --------(2)
这些分支来自于度为 1的结点与度度为 2结点,即
B=n1+2n2 --------(3)
联列关系 (1),(2)与 (3),可得到
n0=n2+1证毕,
4,具有 n个结点的完全二叉树的深度 h=?log2n?+1.
证明,
(略 )
推论,n0=n2+2n3+3n4+? +(m-1)nm +1
North China Electric Power University
5,若对具有 n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为 i 的结点具有以下性质,
(1) 当 i=1,则编号为 i的结点为二叉树的根结点 ;
若 i>1,则编号为 i 的结点的双亲结点的编号为?i/2?;
(2) 若 i<?n/2?,即 2i≤n,则编号为 i的结点为分支结点,否则为叶子结点,n/2是最后一个分支结点 ;
(3) 若 n为奇数,则树中每个分支结点都有左右孩子,若 n为偶数,则编号最大的分支结点只有左孩子、无右孩子，其余分支结点都有左右孩子；
(4) 若编号为 i的结点有左孩子，则左孩子结点的编号为 2i;
若编号为 i的结点有右孩子，则右孩子的编号为 2i+1;
North China Electric Power University
二叉树的存储结构一,二叉树的顺序存储结构
1
2 3
4 5 6 7
8 9 10
A
B C
D E F G
H I J
BT[1:15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H I J
根据完全二叉树的性质 5,对于深度为 h 的完全二叉树,
将树中所有结点的数据信息按照编号的顺序依次存储到一维数组 BT[1:2h-1]中,由于编号与数组的下标一一对应,该数组就是该完全二叉树的顺序存储结构,
1,完全二叉树的顺序存储结构华电计算机系
North China Electric Power University
1
2 3
4 5 6 7
8 910
A
B C
D E F G
H IJ
11 12 13
BT[1:15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H J I
A
B C
D E F G
H IJ
2,一般二叉树的顺序存储结构华电计算机系
North China Electric Power University
对于一般二叉树,只须在二叉树中“添加”一些实际上二叉树中并不存在的“虚结点” ( 可以认为这些结点的数据信息为空 ),使其在形式上成为一棵“完全二叉树”,然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组 BT[1,2h -1]中。
A B C
BT[1,7]
A B C D
BT[1,15]
A
C
B
对于一些称为“退化二叉树”的二叉树，
顺序存储结构的空间开销浪费的缺点比较突出。
A
C
B
D
North China Electric Power University
二,二叉树的链式存储结构 (二叉链表 )
链结点的构造为
lchild data rchild
其中,data 为数据域
lchild 与 rchild 分别为指向左、右子树的指针域,
A
B C
D E F G
IJ
A
B C
D E F G
J I
T
^
^
^ ^ ^
^ ^ ^
^ ^
华电计算机系
North China Electric Power University
在 Pascal 语言中，可以如下描述一个链结点的构造,
TYPE
nodeptr=?nodetype;
nodetype=RECORD
data,datatype;
lchild,rchild,nodeptr;
END;
VAR
T,nodeptr;
在 C 语言中，一个链结点的描述为：
struct node {
datatype data;
struct node *lchild,*rchild;
}
struct node *T;
华电 计算机系三,三重链表结构链结点的构造
parent rchildlchilddata
^
其中,data 为数据域 ;
lchild 为指针域,指向左孩子结点 ;
parent 为指针域,指向该结点的双亲结点 ;
brother 为指针域,指向右孩子结点,
华电计算机系
A
B C
D E F G
IJ
A
CB
D E F G
IJ
^
^ ^
^ ^ ^ ^
^ ^^ ^
North China Electric Power University
例,已知深度为 h的二叉树采用顺序存储结构存放于数组
BT[1,2h-1]中,写一算法，求二叉树中叶结点的数目。
function LEAF( BT,h ),integer;
begin
return( total );
end
total:=0
if (BT[i]?^) then
if ( BT[2i]=^ and BT[2i+1]=^ )
or ( i>?(2h-1)/2? ) then
total:=total+1;
for i:=1 to 2h-1 do
[
]
算法北航 计算机系树与二叉树之间的转换
North China Electric Power University
1,在兄弟结点之间加一条连线；
2,对每个结点，除去其最左的孩子之外，去掉该结点与其他孩子之间的连线；
3,以树的根结点为轴心，将整棵树顺时针旋转 45度。
A
B C D
E F G H I J
A
B C D
E F G H I J
A
B
C
D
E
F G
H
I J
森林与二叉树之间的转换
North China Electric Power University
1,将森林中各棵树的根结点之间加一条连线；
2,对每棵树，用树的二叉树表示法相连，然后顺时针旋转 45度。
A
B C D
E G
F H
J
I
A
B E
GC
D
F
H
I
J
North China Electric Power University
★ 二叉树的遍历及线索二叉树常用的二叉树的遍历方法,
1.先序遍历
2.中序遍历
3.后序遍历
4.按层次遍历右子树左子树根华电 计算机系按照一定的顺序 ( 原则 )对二叉树中每一个结点都访问一次 (仅访问一次 ),得到一个由该二叉树的所有结点组成的序列,这一过程称为二叉树的遍历,
North China Electric Power University
前序序列,
A B D E J C F I
原则,
若被遍历的二叉树非空,则
1,访问根结点 ;
2,以前序遍历原则遍历根结点的左子树 ;
3,以前序遍历原则遍历根结点的右子树,
G
华电计算机系
1,先序遍历
A
B C
D E F G
J I
North China Electric Power University
华电计算机系
2,中序遍历
A
B C
D E F G
J I
中序序列,
D B J E A F I C
原则,
若被遍历的二叉树非空,则
1,以中序遍历原则 遍历根结点的左子树 ;
2,访问根结点 ;
3,以中序遍历原则 遍历根结点的右子树,
G
North China Electric Power University
华电计算机系
3,后序遍历
A
B C
D E F G
J I
后序序列,
D J E B I F G C
原则,
若被遍历的二叉树非空,则
1,以后序遍历原则 遍历根结点的左子树 ;
2,以后序遍历原则 遍历根结点的右子树,
3,访问根结点 ;
A
North China Electric Power University
procedure Preorder( T );
begin
if (T?nil) then
[ writeln( T?.data );
Preorder( T?.lchild );
Preorder( T?.rchild );]
end;
先序遍历
procedure Inorder( T );
begin
if (T?nil) then
[ Inorder( T?.lchild );
writeln( T?.data );
Inorder( T?.rchild );]
end;
中序遍历华电 计算机系
North China Electric Power University
按层次遍历按层次遍历序列,
A,B,C,D,E,F,G,J,I
procedure Postorder( T );
begin
if (T?nil) then
[ Postorder( T?.lchild );
Postorder( T?.rchild );
writeln( T?.data );]
end;
后序遍历华电计算机系
A
B C
D E F G
J I
例 下图是代表表达式 a+b*(c-d)-e/f的二叉树
-
+ /
a * e f
b -
c d
华电 计算机系
a+b*c-d-e/f
中序遍历序列,
abcd-*+ef/-
后序遍历序列,
-+a*b-cd/ef
先序遍历序列,
North China Electric Power University
North China Electric Power University
三种遍历方法的非递归算法用自然语言表达的算法
(1) 若 p 指向的结点非空，则将 p指的结点的 地址 进栈,然后,将 p 指向左子树的根 ;
(2) 若 p 指向的结点为空,则从堆栈中退出栈顶元素送 p，访问该结点，然后,将 p 指向右子树的根；
重复上述过程,直到 p 为空,并且堆栈也为空。
STACK[1,M] --- 保存遍历过程中链结 点 的地址
top --- 栈顶指针,初始为 0
p --- 为遍历过程中使用的指针变量，初始时指向根结点。
(以中序遍历为例 )
p?rchild(p)
p?lchild(p)
North China Electric Power University
中序遍历
Procedure Inorder(T);
Begin
if t=nil then return
else [i:=0;p:=t;]
repeat
while p<>nil do
[ i:=i+1;s[i]:=p;p:=p?.lchild;]
if i<>0 then
[ p:=s[i];i:=i-1;
write(p?.data);
p:=p?.rchild;
]
until (i=0) and (p=nil);
end;
North China Electric Power University
先序遍历
Procedure Preorder(T);
Begin
if t=nil then return
else [i:=0;p:=t;]
repeat
while p<>nil do
[ write(p?.data);
if p?.rchild<> nil then
[i:=i+1;s[i]:=p?.rchild;]
p:=p?.lchild;
]
if i<>0 then [ p:=s[i];i:=i-1;]
until (i=0) and (p=nil);
end;
North China Electric Power University
后序遍历
Procedure Postorder(T);
Begin
if t=nil then return
else [i:=0;p:=t;]
repeat
while p<>nil do
[ i:=i+1;s[i]:=p;p:=p?.lchild;]
while(i<>0) and (p=nil) do
[ p:=s[i];i:=i-1;
if p>0 then
[i:=i+1;s[i]:= -p;p:=p?.rchild]
else
[p:= -p;write(p?.data);p:=nil;]
]
until (i=0) and (p=nil);
end;
North China Electric Power University
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
后序序列,
D,J,E,B,I,F,G,C,A
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
后序序列,?！
华电 计算机系
A
B C
D E F G
IJ
由遍历序列恢复二叉树
North China Electric Power University
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
A
D,B,J,E F,I,C,G
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
A
F,I,C,GB
J,ED
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
A
F,I,C,GB
D E
J 华电计算机系
North China Electric Power University
后序序列,
D,J,E,B,I,F,G,C,A
规律 (前,中 ):
在前序序列中找根 ;
到中序序列中分左右。
规律 (中,后 ):
在后序序列中找根 ;
到中序序列中分左右 。
华电 计算机系
A
B C
D E F G
IJ
North China Electric Power University
1.建立二叉树
Procedure CreateBtr(var t);
Begin
read(ch);
if ch=’#’ then t:=nil
else
[ new(p); p?.data:=ch;
t:=p;
CreateBtr(T?.lchild);
CreateBtr(T?.rchild);
]
End;
二叉树遍历算法的应用示例
North China Electric Power University
2.统计二叉树结点个数
BitNode(t)=
0 若 t=nil
1 若 t?.lchild=nil and t?.rchild=nil
BitNode(t?.lchild)+BitNode(t?.rchild) 其他统计方法
Function BitNode(t):integer;
Begin
if(t=nil) return(0)
else if(t?.lchild=nil) and (t?.rchild=nil) then return (1)
else [ nodes1:=BitNode( t?.lchild);
nodes2:=BitNode( t?.rchild);
return(nodes1+nodes2);
]
End;
North China Electric Power University
3.交换二叉树中各结点的左右子树
Procedure Swap(t);
Begin
if(t<>nil) then
[ if (t?,lchild<>nil) or(t?.rchild<>nil)
then[p:=t?.rchild; t?.rchild:=t?.lchild; t?.lchild:=p;]
if (t?,lchild<>nil) then Swap(t?,lchild);
if (t?,rchild<>nil) then Swap(t?,rchild);]
End;
A
B C
D E F
注意：这里不能用中序遍历。
A
B C
E D F
A
C
F
B
E D
North China Electric Power University
4.表达式的计算采用的结点结构如右图所示,lchild rchilddata value
其中 val域存放以该结点为根的子树的值：
-
+ /
- * a e
a b c d
表达式,(a-b)+(c*d)-(a/e)
Procedure Postorder_val(t);
Begin
if(t<>nil) then
[ Postorder_val(t?.lchild);
Postorder_val(t?.rchild);
case t?.data
‘+’:t?.val:=t?.lchild?.val+
t?.rchild?.val;
…
else,t?.val:=t?.data;
end case
]
End;
North China Electric Power University
利用二叉链表中空的指针域指出结点在遍历序列中的直接前驱和直接后继 ;这些指向前驱和后继的指针称为 线索,加了线索的二叉树称为 线索二叉树,
利用链结点为空的左指针域存放该结点的直接前驱的地址,空的右指针域存放该结点直接后继的地址 ; 而非空的指针域仍然存放结点的左孩子或右孩子的地址,
二叉线索树的构造二叉线索树
North China Electric Power University
NIL
(a)先序
NIL
(b)中序
NIL
NIL
(c)后序线索树示例
A
B D
C E F
G H
A
B D
C E F
G H
A
B D
C E F
G H
North China Electric Power University
ltag lchild data rchild rtag
1 表示 lchild(p) 为指向直接前驱的线索
ltag(p) =
0 表示 lchild(p) 为指向左孩子的指针
1 表示 rchild(p) 为指向直接后继的线索
rtag(p) =
0 表示 rchild(p) 为指向右孩子的指针
指针与线索的区分方法之一,
华电 计算机系
North China Electric Power University
指针与线索的区分方法之二,
不改变链结点的构造,而是在作为线索的地址前加一个负号,即负地址表示线索,正地址表示指针,
华电 计算机系
North China Electric Power University
NIL
a
b
c d
e f
NIL
中序线索树示例
-
+ /
*
-
由于左图中 lchild(a)与 rchild(f)是悬空的，为了不使线索断开，这里对于所有的线索树将假定一个头结点，其 data域为空或与其它结点的 data域值不同,
-
+ /
a * e
f
b -
c d
1 1
0 0
0 0 0 0
1 1 0 0 1 1
1 1 0 0
1 1 1 1
1 1
North China Electric Power University
(1),当 rtag(x)=1时,rchild(x)指出的结点就是 x 的直接后继结点。
(2),当 rtag(x)=0时,沿着 x 的右子树的根的左子树方向往下找,直到某结点的 lchild 域为线索时,此结点就是 x 结点直接后继结点。
中序二叉线索树二叉线索树的利用
(3),当 ltag(x)=1时,lchild(x)指出的结点就是 x 的直接前驱结点。
(4),当 ltag(x)=0时,从 x的左链沿右找下去，直到某结点的 rlchild 域为线索时,此结点就是 x 结点直接前驱结点。
North China Electric Power University
后序二叉线索树
(1),当 rtag(x)=1时,rchild(x)指出的结点就是 x 的直接后继结点。
(2),当 rtag(x)=0时,从 x的双亲结点的右孩子沿着左链一直往下找,直到某结点的 lchild 域为线索时,然后再看此结点有无右孩子，若有，则再沿着右孩子走下去，如此递归进行，直到一个无左、右孩子的结点便是 x的后继，若结点 x的双亲没有右孩子或右孩子就是结点本身，
则此双亲结点便是 x的直接后继结点。
(3),当 ltag(x)=1时,lchild(x)指出的结点就是 x 的直接前驱结点。
(4),当 ltag(x)=0时,若 x有右孩子，则 x的右即为其前驱，若
x无右孩子，则必有左孩子，这个左孩子就是 x的直接前驱结点。
North China Electric Power University
★ 树的遍历由于树种每个结点可以有两棵以上的子树，所以有两种遍历树的方法：
1,先序遍历：先访问树的根结点，然后依次先序遍历树的各棵子树。
2,后序遍历：依次后序遍历树的根的各棵子树，然后访问根结点。
树没有中序遍历，因为树中每个结点的子树的个数可以有多个，把根放在那两个子树之间是无法确定的，算法实现上不易统一。
A
B C E
D
先序序列,A B C D E
后序序列,B D C E A
North China Electric Power University
森林的遍历
1.先序遍历森林：
1）访问森林中第一棵树的根结点；
2）先序遍历第一棵树中根结点的子树森林；
3）先序遍历除去第一棵树之后剩余的树构成森林。
2.中序遍历森林
1）中序遍历森林中第一棵树的根结点的子树林；
2）访问第一棵树的根结点；
3）中序遍历除去第一棵树之后剩余的树构成的树林。
由树和二叉树的转换规则可知：森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历。
A
B C D
E
F
G
H I
J先序序列,ABCDEFGHIJ
后序序列,BCDAFEHJIG
North China Electric Power University
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第五章 树
★ 基本术语
★ 树的基本操作和存储结构
★ 二叉树
North China Electric Power University
★ 二叉树的遍历及线索二叉树
★ 树的遍历
★ 哈夫曼树及其应用
★ 基本术语
North China Electric Power University
树型结构是一类重要的非线性数据结构，其中以二叉树最为常用。树是以分支关系定义的层次结构，它为计算机应用中出现的具有层次关系或分支关系的数据提供了一种自然的表示方法。用树结构描述的信息模型在客观世界普遍存在。
计算机科学与工程系办公室 教研室 实验室 研究室行政办公室总支办公室计算机教研室软件教研室软件实验室综合实验室数字逻辑实验室组成原理试验室管理信息系统研究室知识工程研究室微机应用研究室
North China Electric Power University
树的定义,树是 n(n≥ 0)个结点的有限集 T,在一棵非空树中：
1)有且仅有一个特定的称为根的结点；
2)当 n>1时,其余结点可分为 m(m>0)个互不相交的有限集合 T1,T2,…,Tm,其中每个集合本身又是一棵树，并且称为根的子树。
树的定义可以用如下形式化描述来表示：
Tree=(D,R)
其中,D是具有相同特性的数据元素的集合 ;若 D只含有一个元素,则 R为空集,否则 R是 D上的某个二元关系 H
的集合,即 R={H},H为如下描述的二元关系,
树的几种表示方法,
1)有且仅有一个结点没有前驱，该结点被称为树的根；
2)除树根结点外，其余每个结点有且仅有一个前驱结点；
3)包含树根结点在内的每个结点，可以有任意多个 (包含
0个 )后继。
A
B C D
E F G H I J
K L M
1)二元组表示
D={A,B,C,D,E,F,G,H,I,J,K,L,M}
R={<A,B>,<A,C>,<A,D>,
<B,E>,<B,F>,<C,G>,<D,H>,
<D,I>,<D,J>,<F,K>,<F,L>,
<J,M>}
North China Electric Power University
4) 广义表表示法,A(B(E,F(K,L)),C(G),D(H,I,J(M)))
A
BE
K LF
C G
H
I
M
D
J
2)集合图表示 3)凹入表表示
North China Electric Power University
树型结构和线性结构的比较树型结构 线性结构根结点无前驱结点 第一个数据元素无前驱多个叶子结点无后继 最后一个数据元素无后继其它数据元素有一个前驱和多个后继其它元素有且仅有一个直接前驱和一个直接后继
North China Electric Power University
树中的基本术语,A
B C D
E F G H I J
K L M
1.结点、结点的度、树的度
2.叶子结点、分支结点
3.孩子、双亲、兄弟、
堂兄弟、祖先、子孙
4.结点的层次、树的深度
5.有序树和无序树
6.森林
B C D
E F G H I J
K L M
North China Electric Power University
树的性质,
性质 1:树中的结点数等于所有结点的度加 1。 A
B C D
E F G H I J
K L M
证明：除树的根结点外每个结点有且只有一个直接前驱，除树的根结点之外的结点数等于所有结点的分支数。
性质 2:度为 k的树中第 i层至多有 ki-1个结点。
性质 3:深度为 h的 k叉树至多有 (kh-1)/(k-1)个结点。
性质 4:具有 n个结点的 k叉树的最小深度为 logk(n(k-1)+1) 。
North China Electric Power University
★ 树的基本操作和存储结构树的基本运算
1.Root(T):求树 T的根结点，若 T为空则返回结果为“空”。
2.Parent(T,x):求结点 x在树 T上的双亲结点，若结点 x是树 T的根结点或 x不在树 T中，则返回结果为“空”。
3.Initiate(T):置 T为空树。
4.Child(T,x,i):求树 T上结点 x的第 i个孩子，若 x不在树 T上或 x
没有第 i个孩子，则返回结果为“空”。
5.Create(x,T1,T2,…,T k):建立一棵以 x为根，以 T1,T2,…,T k为第 1,2,
3…,k 棵子树的树。
6.Delete(T,x,i):删除树 T上结点 x的第 i棵子树，若结点 x无第 i棵子树，则为空操作。
7.Traverse(T):按某个次序依次访问树中的各个结点，并使每个结点只被访问一次。
North China Electric Power University
树的存储结构
1.孩子表示法由于树中每个结点可能有多棵子树，可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，则结点形式有如下两种：
data child1 child2 childd…
data child1 child2 childd…degree
在第一种形式中，结点是同构的，存储空间浪费较大，
在第二种形式中，结点是不同构的，虽能节约存储空间，但实现和运算很不方便。
(1)
(2)
North China Electric Power University
可以把每个结点的孩子结点排列起来，看成一个线性表，
且以单链表作存储结构,n个结点有 n个孩子链表,n个头指针又组成一个线性表，为了便于查找，可用向量表示。
Type link=↑ node;
node=record
child:ElemType;
next:link;
end;
tree=Array[1..maxn] of link;
1
2 3
4 5 6
2 3
4 5
6
^
^
1
2
3
4
5
6
^
^
^
^
2 3
4 5
6
^
^
1
2
3
4
5
6
0
1
1
2
2
2
^
^
^
^
North China Electric Power University
2.孩子兄弟表示法又称二叉链表表示法，即以二叉链表作树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为 first-child和 nextsibling。
data first-child nextsibling
1
2 3
4 5 6
1
2 3
4 5 6
^
^^
^ ^ ^^
在孩子兄弟表示法中，要找结点 x的第 i个孩子,则只要先从
first-child域找到第一个孩子结点上，然后沿着该孩子结点的
nextsibling域连续走 i-1步，便可找到 x的第 i个孩子。
North China Electric Power University
3.双亲表示法用一个数组顺序地存放树的各个结点，结点存放的顺序是任意的。每一结点有两个域组成：数据域和指针域，分别存储树上结点中的数据元素和用于指示本结点之双亲所在的存储结点。
指针域的类型定义有两种：高级语言中的指针类型和整型或子界类型，与之对应的链表分别称为动态链表和静态链表。
静态双亲链表的定义：
const size={结点数 };
Type node=record
data:ElemType;
parent:0..size;
end;
stalist=array[1..size] of node;
1
2 3
4 5 6
^1
2
3
4
5
6
1
3
2
4
5
6
data parent
0
1
1
3
3
3
结点序号
North China Electric Power University
★ 二叉树二叉树是一种重要的数据结构类型，它有许多良好的性质和简单的物理表示，它的特点是最多有两个孩子，并且二叉树的子树有左右之分，且其子树的顺序不能任意颠倒。
二叉树的定义二叉树是有 n(n≥0) 个结点的有限集合，此集合或者是空的，或者是由一个根结点加上两棵分别称为左右子树的、互不相交的二叉树组成。
注意,二叉树和树是两个不同的概念，树的子树不必区分其次序，而二叉树的子树有左右之分，另外，二叉树也不能简单地看成是一有序树，因为只有一棵子树时，无法区分其次序。
North China Electric Power University
二叉树的基本形态：
(空 ) 根 根左子树根右子树根左子树右子树具有三个结点的二叉树具有以下五种基本形态：
North China Electric Power University
两种特殊形态的二叉树若一棵二叉树中的结点,
或者为叶结点,或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层,这样的二叉树为满二叉树,
1,满二叉树若一棵二叉树中只有最下面两层的结点的度可以小于 2,
并且最下面一层的结点 (叶结点 )都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树,
2.完全二叉树
North China Electric Power University
1,一棵非空二叉树的第 i 层最多有 2i–1个结点 (i?1)。
证明 (采用归纳法 )
(1).当 i=1时,结论显然正确。非空二叉树的第 1层有且仅有一个结点,即树的根结点,
(2).假设对于第 j层 (1?j?i–1)结论也正确,即第 j层最多有 2j-1个结点,
(3).由定义可知,二叉树中每个结点最多只能有两个孩子结点。若第 i–1层的每个结点都有两棵非空子树,则第 i层的结点数目达到最大,而第 i–1层最多有 2i–2个结点已由假设证明,于是,应有
2?2i–2 = 2i–1证毕,
二叉树的性质
North China Electric Power University
2,深度为 h 的非空二叉树最多有 2h -1个结点,
证明,
由性质 1可知,若深度为 h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。即有
20+21+22+…+2 i-1+ …+2 h-1 = 2h-1
证毕,
华电计算机系
North China Electric Power University
3,若非空二叉树有 n0个叶结点,有 n2个度为 2的结点,
则 n0=n2+1
证明,
设该二叉树有 n1个度为 1的结点,结点总数为 n,有
n=n0+n1+n2 --------(1)
设二叉树的分支数目为 B,有
B=n-1 --------(2)
这些分支来自于度为 1的结点与度度为 2结点,即
B=n1+2n2 --------(3)
联列关系 (1),(2)与 (3),可得到
n0=n2+1证毕,
4,具有 n个结点的完全二叉树的深度 h=?log2n?+1.
证明,
(略 )
推论,n0=n2+2n3+3n4+? +(m-1)nm +1
North China Electric Power University
5,若对具有 n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为 i 的结点具有以下性质,
(1) 当 i=1,则编号为 i的结点为二叉树的根结点 ;
若 i>1,则编号为 i 的结点的双亲结点的编号为?i/2?;
(2) 若 i<?n/2?,即 2i≤n,则编号为 i的结点为分支结点,否则为叶子结点,n/2是最后一个分支结点 ;
(3) 若 n为奇数,则树中每个分支结点都有左右孩子,若 n为偶数,则编号最大的分支结点只有左孩子、无右孩子，其余分支结点都有左右孩子；
(4) 若编号为 i的结点有左孩子，则左孩子结点的编号为 2i;
若编号为 i的结点有右孩子，则右孩子的编号为 2i+1;
North China Electric Power University
二叉树的存储结构一,二叉树的顺序存储结构
1
2 3
4 5 6 7
8 9 10
A
B C
D E F G
H I J
BT[1:15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H I J
根据完全二叉树的性质 5,对于深度为 h 的完全二叉树,
将树中所有结点的数据信息按照编号的顺序依次存储到一维数组 BT[1:2h-1]中,由于编号与数组的下标一一对应,该数组就是该完全二叉树的顺序存储结构,
1,完全二叉树的顺序存储结构华电计算机系
North China Electric Power University
1
2 3
4 5 6 7
8 910
A
B C
D E F G
H IJ
11 12 13
BT[1:15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H J I
A
B C
D E F G
H IJ
2,一般二叉树的顺序存储结构华电计算机系
North China Electric Power University
对于一般二叉树,只须在二叉树中“添加”一些实际上二叉树中并不存在的“虚结点” ( 可以认为这些结点的数据信息为空 ),使其在形式上成为一棵“完全二叉树”,然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组 BT[1,2h -1]中。
A B C
BT[1,7]
A B C D
BT[1,15]
A
C
B
对于一些称为“退化二叉树”的二叉树，
顺序存储结构的空间开销浪费的缺点比较突出。
A
C
B
D
North China Electric Power University
二,二叉树的链式存储结构 (二叉链表 )
链结点的构造为
lchild data rchild
其中,data 为数据域
lchild 与 rchild 分别为指向左、右子树的指针域,
A
B C
D E F G
IJ
A
B C
D E F G
J I
T
^
^
^ ^ ^
^ ^ ^
^ ^
华电计算机系
North China Electric Power University
在 Pascal 语言中，可以如下描述一个链结点的构造,
TYPE
nodeptr=?nodetype;
nodetype=RECORD
data,datatype;
lchild,rchild,nodeptr;
END;
VAR
T,nodeptr;
在 C 语言中，一个链结点的描述为：
struct node {
datatype data;
struct node *lchild,*rchild;
}
struct node *T;
华电 计算机系三,三重链表结构链结点的构造
parent rchildlchilddata
^
其中,data 为数据域 ;
lchild 为指针域,指向左孩子结点 ;
parent 为指针域,指向该结点的双亲结点 ;
brother 为指针域,指向右孩子结点,
华电计算机系
A
B C
D E F G
IJ
A
CB
D E F G
IJ
^
^ ^
^ ^ ^ ^
^ ^^ ^
North China Electric Power University
例,已知深度为 h的二叉树采用顺序存储结构存放于数组
BT[1,2h-1]中,写一算法，求二叉树中叶结点的数目。
function LEAF( BT,h ),integer;
begin
return( total );
end
total:=0
if (BT[i]?^) then
if ( BT[2i]=^ and BT[2i+1]=^ )
or ( i>?(2h-1)/2? ) then
total:=total+1;
for i:=1 to 2h-1 do
[
]
算法北航 计算机系树与二叉树之间的转换
North China Electric Power University
1,在兄弟结点之间加一条连线；
2,对每个结点，除去其最左的孩子之外，去掉该结点与其他孩子之间的连线；
3,以树的根结点为轴心，将整棵树顺时针旋转 45度。
A
B C D
E F G H I J
A
B C D
E F G H I J
A
B
C
D
E
F G
H
I J
森林与二叉树之间的转换
North China Electric Power University
1,将森林中各棵树的根结点之间加一条连线；
2,对每棵树，用树的二叉树表示法相连，然后顺时针旋转 45度。
A
B C D
E G
F H
J
I
A
B E
GC
D
F
H
I
J
North China Electric Power University
★ 二叉树的遍历及线索二叉树常用的二叉树的遍历方法,
1.先序遍历
2.中序遍历
3.后序遍历
4.按层次遍历右子树左子树根华电 计算机系按照一定的顺序 ( 原则 )对二叉树中每一个结点都访问一次 (仅访问一次 ),得到一个由该二叉树的所有结点组成的序列,这一过程称为二叉树的遍历,
North China Electric Power University
前序序列,
A B D E J C F I
原则,
若被遍历的二叉树非空,则
1,访问根结点 ;
2,以前序遍历原则遍历根结点的左子树 ;
3,以前序遍历原则遍历根结点的右子树,
G
华电计算机系
1,先序遍历
A
B C
D E F G
J I
North China Electric Power University
华电计算机系
2,中序遍历
A
B C
D E F G
J I
中序序列,
D B J E A F I C
原则,
若被遍历的二叉树非空,则
1,以中序遍历原则 遍历根结点的左子树 ;
2,访问根结点 ;
3,以中序遍历原则 遍历根结点的右子树,
G
North China Electric Power University
华电计算机系
3,后序遍历
A
B C
D E F G
J I
后序序列,
D J E B I F G C
原则,
若被遍历的二叉树非空,则
1,以后序遍历原则 遍历根结点的左子树 ;
2,以后序遍历原则 遍历根结点的右子树,
3,访问根结点 ;
A
North China Electric Power University
procedure Preorder( T );
begin
if (T?nil) then
[ writeln( T?.data );
Preorder( T?.lchild );
Preorder( T?.rchild );]
end;
先序遍历
procedure Inorder( T );
begin
if (T?nil) then
[ Inorder( T?.lchild );
writeln( T?.data );
Inorder( T?.rchild );]
end;
中序遍历华电 计算机系
North China Electric Power University
按层次遍历按层次遍历序列,
A,B,C,D,E,F,G,J,I
procedure Postorder( T );
begin
if (T?nil) then
[ Postorder( T?.lchild );
Postorder( T?.rchild );
writeln( T?.data );]
end;
后序遍历华电计算机系
A
B C
D E F G
J I
例 下图是代表表达式 a+b*(c-d)-e/f的二叉树
-
+ /
a * e f
b -
c d
华电 计算机系
a+b*c-d-e/f
中序遍历序列,
abcd-*+ef/-
后序遍历序列,
-+a*b-cd/ef
先序遍历序列,
North China Electric Power University
North China Electric Power University
三种遍历方法的非递归算法用自然语言表达的算法
(1) 若 p 指向的结点非空，则将 p指的结点的 地址 进栈,然后,将 p 指向左子树的根 ;
(2) 若 p 指向的结点为空,则从堆栈中退出栈顶元素送 p，访问该结点，然后,将 p 指向右子树的根；
重复上述过程,直到 p 为空,并且堆栈也为空。
STACK[1,M] --- 保存遍历过程中链结 点 的地址
top --- 栈顶指针,初始为 0
p --- 为遍历过程中使用的指针变量，初始时指向根结点。
(以中序遍历为例 )
p?rchild(p)
p?lchild(p)
North China Electric Power University
中序遍历
Procedure Inorder(T);
Begin
if t=nil then return
else [i:=0;p:=t;]
repeat
while p<>nil do
[ i:=i+1;s[i]:=p;p:=p?.lchild;]
if i<>0 then
[ p:=s[i];i:=i-1;
write(p?.data);
p:=p?.rchild;
]
until (i=0) and (p=nil);
end;
North China Electric Power University
先序遍历
Procedure Preorder(T);
Begin
if t=nil then return
else [i:=0;p:=t;]
repeat
while p<>nil do
[ write(p?.data);
if p?.rchild<> nil then
[i:=i+1;s[i]:=p?.rchild;]
p:=p?.lchild;
]
if i<>0 then [ p:=s[i];i:=i-1;]
until (i=0) and (p=nil);
end;
North China Electric Power University
后序遍历
Procedure Postorder(T);
Begin
if t=nil then return
else [i:=0;p:=t;]
repeat
while p<>nil do
[ i:=i+1;s[i]:=p;p:=p?.lchild;]
while(i<>0) and (p=nil) do
[ p:=s[i];i:=i-1;
if p>0 then
[i:=i+1;s[i]:= -p;p:=p?.rchild]
else
[p:= -p;write(p?.data);p:=nil;]
]
until (i=0) and (p=nil);
end;
North China Electric Power University
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
后序序列,
D,J,E,B,I,F,G,C,A
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
后序序列,?！
华电 计算机系
A
B C
D E F G
IJ
由遍历序列恢复二叉树
North China Electric Power University
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
A
D,B,J,E F,I,C,G
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
A
F,I,C,GB
J,ED
前序序列,
A,B,D,E,J,C,F,I,G
中序序列,
D,B,J,E,A,F,I,C,G
A
F,I,C,GB
D E
J 华电计算机系
North China Electric Power University
后序序列,
D,J,E,B,I,F,G,C,A
规律 (前,中 ):
在前序序列中找根 ;
到中序序列中分左右。
规律 (中,后 ):
在后序序列中找根 ;
到中序序列中分左右 。
华电 计算机系
A
B C
D E F G
IJ
North China Electric Power University
1.建立二叉树
Procedure CreateBtr(var t);
Begin
read(ch);
if ch=’#’ then t:=nil
else
[ new(p); p?.data:=ch;
t:=p;
CreateBtr(T?.lchild);
CreateBtr(T?.rchild);
]
End;
二叉树遍历算法的应用示例
North China Electric Power University
2.统计二叉树结点个数
BitNode(t)=
0 若 t=nil
1 若 t?.lchild=nil and t?.rchild=nil
BitNode(t?.lchild)+BitNode(t?.rchild) 其他统计方法
Function BitNode(t):integer;
Begin
if(t=nil) return(0)
else if(t?.lchild=nil) and (t?.rchild=nil) then return (1)
else [ nodes1:=BitNode( t?.lchild);
nodes2:=BitNode( t?.rchild);
return(nodes1+nodes2);
]
End;
North China Electric Power University
3.交换二叉树中各结点的左右子树
Procedure Swap(t);
Begin
if(t<>nil) then
[ if (t?,lchild<>nil) or(t?.rchild<>nil)
then[p:=t?.rchild; t?.rchild:=t?.lchild; t?.lchild:=p;]
if (t?,lchild<>nil) then Swap(t?,lchild);
if (t?,rchild<>nil) then Swap(t?,rchild);]
End;
A
B C
D E F
注意：这里不能用中序遍历。
A
B C
E D F
A
C
F
B
E D
North China Electric Power University
4.表达式的计算采用的结点结构如右图所示,lchild rchilddata value
其中 val域存放以该结点为根的子树的值：
-
+ /
- * a e
a b c d
表达式,(a-b)+(c*d)-(a/e)
Procedure Postorder_val(t);
Begin
if(t<>nil) then
[ Postorder_val(t?.lchild);
Postorder_val(t?.rchild);
case t?.data
‘+’:t?.val:=t?.lchild?.val+
t?.rchild?.val;
…
else,t?.val:=t?.data;
end case
]
End;
North China Electric Power University
利用二叉链表中空的指针域指出结点在遍历序列中的直接前驱和直接后继 ;这些指向前驱和后继的指针称为 线索,加了线索的二叉树称为 线索二叉树,
利用链结点为空的左指针域存放该结点的直接前驱的地址,空的右指针域存放该结点直接后继的地址 ; 而非空的指针域仍然存放结点的左孩子或右孩子的地址,
二叉线索树的构造二叉线索树
North China Electric Power University
NIL
(a)先序
NIL
(b)中序
NIL
NIL
(c)后序线索树示例
A
B D
C E F
G H
A
B D
C E F
G H
A
B D
C E F
G H
North China Electric Power University
ltag lchild data rchild rtag
1 表示 lchild(p) 为指向直接前驱的线索
ltag(p) =
0 表示 lchild(p) 为指向左孩子的指针
1 表示 rchild(p) 为指向直接后继的线索
rtag(p) =
0 表示 rchild(p) 为指向右孩子的指针
指针与线索的区分方法之一,
华电 计算机系
North China Electric Power University
指针与线索的区分方法之二,
不改变链结点的构造,而是在作为线索的地址前加一个负号,即负地址表示线索,正地址表示指针,
华电 计算机系
North China Electric Power University
NIL
a
b
c d
e f
NIL
中序线索树示例
-
+ /
*
-
由于左图中 lchild(a)与 rchild(f)是悬空的，为了不使线索断开，这里对于所有的线索树将假定一个头结点，其 data域为空或与其它结点的 data域值不同,
-
+ /
a * e
f
b -
c d
1 1
0 0
0 0 0 0
1 1 0 0 1 1
1 1 0 0
1 1 1 1
1 1
North China Electric Power University
(1),当 rtag(x)=1时,rchild(x)指出的结点就是 x 的直接后继结点。
(2),当 rtag(x)=0时,沿着 x 的右子树的根的左子树方向往下找,直到某结点的 lchild 域为线索时,此结点就是 x 结点直接后继结点。
中序二叉线索树二叉线索树的利用
(3),当 ltag(x)=1时,lchild(x)指出的结点就是 x 的直接前驱结点。
(4),当 ltag(x)=0时,从 x的左链沿右找下去，直到某结点的 rlchild 域为线索时,此结点就是 x 结点直接前驱结点。
North China Electric Power University
后序二叉线索树
(1),当 rtag(x)=1时,rchild(x)指出的结点就是 x 的直接后继结点。
(2),当 rtag(x)=0时,从 x的双亲结点的右孩子沿着左链一直往下找,直到某结点的 lchild 域为线索时,然后再看此结点有无右孩子，若有，则再沿着右孩子走下去，如此递归进行，直到一个无左、右孩子的结点便是 x的后继，若结点 x的双亲没有右孩子或右孩子就是结点本身，
则此双亲结点便是 x的直接后继结点。
(3),当 ltag(x)=1时,lchild(x)指出的结点就是 x 的直接前驱结点。
(4),当 ltag(x)=0时,若 x有右孩子，则 x的右即为其前驱，若
x无右孩子，则必有左孩子，这个左孩子就是 x的直接前驱结点。
North China Electric Power University
★ 树的遍历由于树种每个结点可以有两棵以上的子树，所以有两种遍历树的方法：
1,先序遍历：先访问树的根结点，然后依次先序遍历树的各棵子树。
2,后序遍历：依次后序遍历树的根的各棵子树，然后访问根结点。
树没有中序遍历，因为树中每个结点的子树的个数可以有多个，把根放在那两个子树之间是无法确定的，算法实现上不易统一。
A
B C E
D
先序序列,A B C D E
后序序列,B D C E A
North China Electric Power University
森林的遍历
1.先序遍历森林：
1）访问森林中第一棵树的根结点；
2）先序遍历第一棵树中根结点的子树森林；
3）先序遍历除去第一棵树之后剩余的树构成森林。
2.中序遍历森林
1）中序遍历森林中第一棵树的根结点的子树林；
2）访问第一棵树的根结点；
3）中序遍历除去第一棵树之后剩余的树构成的树林。
由树和二叉树的转换规则可知：森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历。
A
B C D
E
F
G
H I
J先序序列,ABCDEFGHIJ
后序序列,BCDAFEHJIG
North China Electric Power University
