第四章-树(数据结构word版课件).doc

第四章 树
§4.1 树的基本概念
直观地说，树是按分支关系将数据连接起来的数据结构，就像自然界中的具有树杈分支的树一样。
4.1.1 树的定义
为方便计，有时常将“树”称之为“树形”，或“树形结构”。
定义4.1[1] 一个树（或树形）就是一个有限非空的结点集合T，其中：
[1] 有一个特别标出的被称为该树（或树形）之根root(T)的结点；
[2] 其余结点被分成m ³ 0 个不相交的集合T1, T2, …, Tm，且T1, T2, …, Tm又都是树（或树形）。树（或树形）T1, T2, …, Tm被称作root(T)的子树（或子树形）。
上面给出的定义是递归的，就是说用树来定义树。树形的递归定义似乎是更合适的，因为递归是树形结构的固有特征。在自然界中可观察到，树上的幼芽可长成为具有自己的幼芽的子树，树长出子树，子树又长出它的子树（子树的子树）。图4.1(a)是一棵根结点为A的树，由定义4.1可知，该树中除结点A之外的每个结点，又都是该树中某个子树的根。
图4.1 (a) 树
A
E
C
D
B
I
H
G
F

为了从另外一个角度来理解树结构的概念，我们给出了树的非递归定义。
定义4.2 树是包含n ( n ≥ 1 )个结点且满足如下条件的有限集合：
1) 存在一个唯一的结点v0，它没有前驱结点，称为树的根（或根结点）；
2) 任何非根结点都有且仅有一个前驱结点，称为该结点的父结点；
3) 任何结点都可能有多个（£ n-1）后继结点，称之为该结点的子结点；若某结点没有后继结点，则称之为叶结点。
4) 任一非根结点vk都有且仅有一条从根节点v0到该结点的结点序列（或曰路径）v0 ® v1 ®…® vk，其中vi是vi-1的子结点（1 £ i £ k）。
如对于图4.1(a)中的结点F来说，存在唯一一条从根结点A到它的结点序列A®B®E®F；对于结点H，存在唯一一条从根结点A到它的结点序列A®C®H .
图4.1 (a) 树
A
E
C
D
B
I
H
G
F

4.1.2 树的相关术语
1．度
一个结点的子结点的数目，称为该结点的度或者次数。一棵树的度为maxi=1,…, n D (i)，其中n为树中结点总数，i指树中的第i个结点，D(i)表结点i的度。
2．叶结点、分支结点
度为0的结点被称为叶结点；度 > 0的结点被称为分支结点。
在图4.1(a)中： B有一个子结点E，度为1；A有三个子结点B、C和D（换言之，A是B、C和D的父结点），度为3，故这棵树的度也为3 .
图4.1 (a) 树
A
E
C
D
B
I
H
G
F

3．结点的层数
树形T中结点的层数递归定义如下：
⑴ root(T)层数为零；
⑵ 其余结点的层数为其前驱结点的层数加1 .
4．路径
树形中结点间的连线被称为边。若树形T中存在结点序列vm ® vm+1 ® … ® vm+k，1 £ k £ T的最大层数，满足vi+1是vi（m £ i £ m+k-1）的子结点，则称此结点序列为vm到vm+k的路径，该路径所经历的边数k被称为路径长度。
5. 子孙结点、祖先结点
一棵树中若存在结点vm到vn的路径，则称vn为vm的子孙结点，vm为vn的祖先结点。
图4.1 (a) 树
A
E
C
D
B
I
H
G
F

不难看出，一个结点到它的某个子孙结点有且仅有一条路径。
树形T的任一结点p都是T的一棵子树的根结点，该子树由结点p和其所有子孙结点构成。图4.1(a)中的结点B是由结点B、E、F组成的子树的根，而结点C是由结点C、G、H组成的子树的根。

6．树的高度
树的高度为maxi=1,…, n NL (i)，其中n为树中结点总数，i指树中第i个结点，NL(i)之值为结点i的层数。例如，图4.1(b)中，结点A的层数为0 ，B、C、D的层数为1 ，E、G、H、I的层数为2 ，F的层数为3，故图4.1(b)中之树的高度为3 .
A
E
C
D
B
I
H
G
F
第0层
第1层

第2层

第3层

图4.1 (b) 结点的层数

图4.2给出了一个高度为5的世系树。

图4.2 世系树

§4.2 二叉树
二叉树是一种常用的树结构，它是树结构的另一种重要类型，其特征是：树中每个结点最多有两个子树形。
4.2.1 二叉树定义和主要性质
定义4.3 二叉树（形）是结点的有限集合，它或者是空集，或者由一个根及两个不相交的称为这个根的左、右子树形的二叉树组成。
-
´
a
b

c
/
+
/

d
e
f
图4.3 公式a-b(c/d+e/f)的二叉树表示

二叉树有如下重要性质：
引理4.1 二叉树中层数为的结点至多有2i个，i ³ 0 .
证明：用数学归纳法。
当i = 0时，仅有一个根结点，其层数为0，因此i = 0时引理成立。假定当i = j ( j ³ 0)时，引理成立，即第j层上至多有2j个结点。对于二叉树的任意结点，其子结点个数最多为2，故第j +1层上至多有2´2j = 2j+1个结点，故i = j + 1时，引理亦成立。证毕▐

容易看出高度为k (k ³ 1)的二叉树中至少有k+1个结点。含有k (k ³ 1)个结点的二叉树高度至多为k-1 . 如图4.5是高度为3结点最少的二叉树之一。图4.6(a)是高度为3结点最多的二叉树。
图4.5 有4个结点、高度为3的二叉树
C
A
B
D

(a) 15个结点的满二叉树
8
3
2
1
4
5
6
7
13
14
15
10
11
12
9
引理4.2 高度为k的二叉树中至多有2k+1-1( k ³ 0)个结点。
证明：从第0层到第k层，对每层的最大结点数求和，由引理4.1知，证毕▐
引理4.3 设T是由n个结点构成的二叉树，其中叶结点个数为n0，次数为2的结点个数为n2，则有n0 = n2 +1 .
证明：设n1是T中次数为1的结点个数，则
n = n0 + n1 + n2 (1) （4.1）
设二叉树T的边个数为E. 我们知道，除根结点外，每个结点和父结点之间都有且仅有一条边，即一个结点对应一条边，因此，n比边的个数多1（根结点不对应边），即
n =E+1 (2)
从另一个角度看，次数为1的结点对应一条边，次数为2的结点对应两条边，因此
E = n1+2n2 (3)
由(1)、(2)和(3)可以得到 n0= n2+1. 证毕▐
定义4.4 一棵非空高度为k( k ³ 0)的满二叉树，是有2k+1-1个结点的二叉树。

(a) 15个结点的满二叉树
8
3
2
1
4
5
6
7
13
14
15
10
11
12
9
我们可按层次顺序（即按从第0层到第k层，每层由左向右的次序）将一棵满二叉树的所有结点用自然数从1开始编号。例如，图4.6(a) 给出了高度为3的满二叉树的24-1个结点的编号。

定义4.5 一棵包含n个结点高为k的二叉树T，当按层次顺序编号T的所有结点，对应于一棵高为k的满二叉树中编号由1至n的那些结点时，T被称为完全二叉树。
满二叉树和完全二叉树是二叉树的两种特殊情形。
(a) 15个结点的满二叉树
8
3
2
1
4
5
6
7
13
14
15
10
11
12
9

图4.6 满二叉树与完全二叉树
(b) 10个结点的完全二叉树
8
3
2
1
4
5
6
7
10
9

引理4.4 若将一棵有n个结点的完全二叉树按层次顺序用自然数从1开始编号，则编号为i (1£ i £ n)的结点满足如下性质：
⑴ 若i ¹ 1，则编号为i的结点之父结点的编号为 ëi /2û；
⑵ 若2i £ n，则编号为的结点的左孩子编号为2i，否则i无左孩子；
⑶ 若2i + 1£ n，则i结点的右孩子编号为2i + 1，否则i无右孩子。
证明：用归纳法可证明⑵.
若i =1，如果n ³ 2，则左孩子编号显然为2 .
假定对所有j(1£ j £ i，2i £ n)，j的左孩子编号为2j，则往证结点j=i+1之左孩子的编号为2(i+1)的情况。如果2(i +1) £ n，则由层次顺序知，i +1的左孩子之前的两个结点就是i的左孩子和右孩子，因为i的左孩子编号为2i（由归纳假设），故i的右孩子编号为2i+1，从而i+1的左孩子编号为2i+2=2(i+1) .
因为由⑵可直接推出⑶，由⑵和⑶又可得到⑴，证毕▐

例如：图4.6 (b)中编号为4的结点的父结点编号为2，其左孩子编号为8，右孩子编号为9，而编号为5的结点的父结点编号为2，其左孩子编号为10，无右孩子。
图4.6 满二叉树与完全二叉树
(b) 10个结点的完全二叉树
8
3
2
1
4
5
6
7
10
9

引理4.5 具有n个结点的完全二叉树的高度是ëlog2 nû .
证明：设二叉树高度为k，由定义4.5知，完全二叉树的结点个数介于高度为k和高度为k - 1的满二叉树的结点数之间，即有：
2k-1 < n £ 2k+1-1，从而有2k £ n £ 2k+1-1，即k £ log2 n < k +1，有log2 n -1< k£ log2 n，因为k为整数，故有k = ëlog2 nû，证毕▐

4.2.2 二叉树顺序存储
要存储一棵二叉树，必须存储其所有结点的数据信息、左孩子和右孩子地址，既可用顺序结构存储，也可用链接结构存储。
二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中，同时反映出二叉树中结点间的逻辑关系。
对于完全二叉树，结点的层次顺序反映了其结构，可按层次顺序给出一棵完全二叉树之结点的编号，事实上，这就是完全二叉树的顺序存储方法，结点编号恰好反映了结点间的逻辑关系。只要对二叉树之结点按照层次顺序进行编号，就可利用一维数组A来存储一棵含有n个结点的完全二叉树，其中A[1]存储二叉树的根结点，A[i]存储二叉树中编号为i的结点，并且结点A[i]的左孩子（若存在）存放在A[2i]处，而A[i]的右孩子（若存在）存放在A[2i+1]处。

图4.7 (b) 描述了图4.7 (a) 所示的完全二叉树的顺序存储结构。
图4.7 完全二叉树与顺序存储结构
A
E
C
D
B
(b) 图(a)的顺序存储结构
A[1]
A[3]
A[2]
1
(a) 5个结点的完全二叉树
E
B
A
C
D
2
3
4
5
A[4]
A[5]

这种顺序存储方式是完全二叉树最简单、最节省空间的存储方式，多数完全二叉树应用算法都采用了这种顺序存储方式。它实际上只存储了结点信息域之值，而未存储其左孩子和右孩子地址，通过计算可找到它的左孩子、右孩子和父结点，寻找子孙结点和祖先结点也非常方便。
但是，这种方法应用到非完全二叉树时，却有很多缺点。如果采用上述的顺序存储方式，按照层次顺序，对非完全二叉树之结点进行编号，则这时的编号不能与结点一一对应。为此，先加入若干虚结点将其转换成一棵“完全二叉树”，然后再对原来的结点和虚结点统一编号，最后完成顺序存储。但这增加了用于存储虚结点的空间。
如图4.8(a) 所示，二叉树中只有4个结点，转换为“完全二叉树”后如图4.8 (b) 所示，图中的方形结点为增加的虚结点，其顺序存储结构如图4.8(c)所示，需要15个数组元素，但

A
B
C
D

A
B
C
D

(a) 非完全二叉树

(b) 完全二叉树

A

B

C

D
A[1] A[3] A[7] A[15]

图4.8 非完全二叉树与顺序存储结构
(c) 非完全二叉树的顺序存储结构

实际上只有A[1]、A[3]、A[7]和A[15] 等4个数组元素的存储空间能被充分利用，而其它11个数组元素所占用的空间却被浪费。
显然，对非完全二叉树，顺序存储结构可能会浪费大量存储空间。此外，同线性表的顺序存储一样，二叉树顺序存储方式对插入或删除结点等操作不够方便。

4.2.3 二叉树链接存储
二叉树的链接存储系指二叉树诸结点被随机存放在内存空间中，结点之间的关系用指针说明。在二叉树的链接存储中，二叉树结点应包含三个域：数据域Data、左指针域Left和右指针域Right，结点结构如下：
Left
Data
Right

其中数据域Data存放结点自身的信息，域Left和Right分别存放指向该结点之左孩子和右孩子的指针。
在二叉树的链接存储中，有一个指向根结点的指针，称为根指针，二叉树由根指针唯一确定。若二叉树为空，则根指针为NULL（即L）；若结点的某个孩子不存在，则相应的指针域存放NULL.显然，叶结点的左、右指针域皆存放NULL. 在包含n个结点之二叉树的链接存储中，需要2n个指针域，但其中只有n-1个用来指示结点的左、右孩子，其余n+1个指针域为空（见引理4.3，E = n -1）。
图4.9 (a) 为一棵二叉树，其链接存储结构如图4.9 (b)，结点A的Left指针指向其左子结点B，Right指针指向其右子结点C，结点B的Left指针为空， Right指针指向其子结点D .
Λ
B

Λ
D
Λ

root
Λ
E
Λ

C
Λ

A

A
C
B
D
E

(a) 二叉树

(b) 二叉树的链接表示

图4.9二叉树的链接存储结构

下面用三个算法来说明，二叉树的链接存储可方便地进行二叉树的一些操作。
① 在二叉树中搜索给定结点的父结点
算法Father ( t, p . q )
/* 指针t指向二叉树T之根，在T中搜索给定结点p之父结点； q指向p之父结点；本算法使用了递归 */
Father1. [ t =L? ]
IF t = L THEN ( q ¬ L . RETURN. )
Father2. [ t为所求? ]
IF Left ( t ) = p OR Right ( t ) = p THEN ( q ¬ t. RETURN. )
Father3. [递归]
Father ( Left ( t ) , p . qL).
IF qL ¹ L THEN (q ¬ qL . RETURN. )
ELSE (Father (Right ( t ), p . qR). q ¬ qR . RETURN. )▐

② 搜索二叉树中符合数据域条件的结点
算法Find( t, item . q )
/* 在二叉树T中搜索Data域之值为item的结点，指针t指向T之根，指针q指向欲搜索的结点 */
Find1. [ t =L? ]
IF t = L THEN (q ¬ L . RETURN. ).
IF Data( t ) = item THEN (q ¬ t . RETURN. ).
Find2 .[递归]
Find ( Left(t), item . p ).
IF p ¹ L THEN (q ¬ p . RETURN. ).
Find (Right(t), item . q ).
RETURN.▐

③ 从二叉树中删除给定结点及其左右子树
算法DST ( t )
/* root指向一棵二叉树T之根，本算法从T中删除给定结点t (是简称，其含义是：t是指向该结点的指针)及其左右子树；DST是DelSubTree之缩写*/
DST1. [ t =L? ]
IF t = L THEN RETURN .
DST 2. [ t = root ? ]
IF t = root THEN (Del(t) . root ¬ L . RETURN. )
DST3. [ 找t的父结点q ]
p ¬ t . Father(root, p. q).
DST 4. [修改q的指针域]
IF Left(q) = p THEN Left(q) ¬ L .
IF Right(q) = p THEN Right(q) ¬ L .
DST 5. [删除p及其子树]
Del(p).▐
算法Del( p )
/* 删除结点p及其左右子树 */
Del1. [ p = L? ]
IF p = L THEN RETURN.
Del2. [递归删除]
Del (Left (p)).
Del (Right (p)).
AVAIL Ü p .▐

4.2.4 二叉树遍历
对于树结构的操作有许多算法，并且在这些算法中将反复对树进行“遍历”。遍历树形是系统地考察树形之结点，使得树形的每个结点恰好被访问一次的方法。在计算机内一般的树是借助某个等价的二叉树来表示的。为此，我们先考虑二叉树的遍历问题。我们知道，线性表是一种线性结构，对于链接存储的线性表可通过指针域Next进行顺序遍历。但二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此无法像线性表一样进行简单的顺序遍历。

遍历方法
步骤

先根序
中根序
后根序
步骤一
访问根
遍历左子树
遍历左子树
步骤二
遍历左子树
访问根
遍历右子树
步骤三
遍历右子树
遍历右子树
访问根
例2: 用上述三种方法遍历图4.11 中的二叉树.
图4.11 (A+B)´((C-D)´E+F)对应的二叉树

＋
＋
A
B
×
E
F
－
C
D
×

先根序得到的结点序列：´+AB+´-CDEF
中根序得到的结点序列：A+B´C-D´E+F
后根序得到的结点序列：AB+CD-E´F+´
这三种排列方式都非常重要，因为它们分别对应表达式的前缀、中缀和后缀表示法（其中，中缀表示还需要括号和优先级，稍有差别）。
先根序、中根序、后根序这些名称来自于根相对它的子树的位置。在二叉树的许多应用中，左子树和右子树之间存在着对称性，故对称序可作为中根序的同义词。
有上述定义，对于给定的一棵二叉树，我们可给出在先根序、中根序和后根序下的唯一结点排列。但反过来，也就是由先根序或中根序或后根序所得到的结点序列，我们并不能确定相应二叉树之结构（因为不唯一）。
1．递归遍历算法
根据二叉树先根、中根和后根序遍历的递归定义，可设计出先根、中根和后根序遍历的递归算法PreOrder、InOrder和PostOrder .

① 先根遍历算法
算法PreOrder ( t )
IF t = L THEN RETURN.
PRINT ( Data ( t )) .
PreOrder ( Left ( t )) .
PreOrder ( Right ( t )) . ▐

② 中根遍历算法
算法InOrder ( t )
IF t = L THEN RETURN.
InOrder ( Left ( t )) .
PRINT ( Data ( t )) .
InOrder ( Right ( t )) . ▐

③ 后根遍历算法
算法PostOrder ( t )
IF t = L THEN RETURN.
PostOrder ( Left ( t )) .
PostOrder ( Right ( t )) .
PRINT ( Data ( t )) . ▐
从算法来看，二叉树的先根、中根和后根遍历三种递归算法，只是算法中的PRINT(Data(t))语句与两条递归语句的相对位置不同。从遍历序列来看，三种不同遍历序列的叶结点间的相对次序是相同的，叶结点都是按着从左到右的次序排列，三种遍历序列间的区别仅在于非叶结点间的次序以及非叶结点和叶结点间的次序有所不同。

2．非递归遍历算法
为了在计算机上直接实现上述遍历方法，下面给出非递归遍历算法。
① 非递归中根遍历算法
算法NIO( t )
/* 设t是指向与图4.9(b)中之表示相同的一棵二叉树T 的根的指针，本算法利用一个辅助堆栈S以中根序访问T 的所有结点；NIO是NorecInOrder之缩写 */
NIO1. [初始化]
CREATE ( S ). p ¬ t .
NIO2. [入栈]
WHILE p ¹ L DO
( S Ü p . p ¬ Left ( p) . )
NIO3. [栈为空? ]
IF S为空THEN RETURN.
ELSE p Ü S .
NIO4. [访问p，更新p]
PRINT (Data ( p ) ). p ¬ Right ( p ).
NIO5. [返回]
GOTO NIO2 .▐

(a) 二叉树

F
E
A
C
B
D
例如，图4.12(b) 给出了对图4.12(a)中二叉树进行中根遍历时堆栈的变化过程：

(b) 中根遍历(a)中二叉树, 堆栈内容变化过程

B
A

A

D
A

A

访问B 访问D 访问A 访问E 访问C 访问F

E
C

C

F

图4.12非递归中根遍历二叉树

类似于算法NIO，不难形成先根序的非递归遍历二叉树之算法，我们将该算法留作习题，下面我们讨论后根序非递归二叉树遍历算法。

② 非递归后根遍历算法
非递归后根遍历算法也需要一个辅助堆栈来记忆访问路径，算法中栈元素结构如下：
结点
标号i

其中标号i Î{0, 1, 2} . 树中任一结点q都需进栈三次，出栈三次。第一次出栈是为遍历结点q的左子树，第二次出栈是为遍历结点q的右子树，第三次出栈是为访问结点q . 具体方法如下：
（1） 将（根结点，0 ）压入堆栈。
（2） 弹栈，对出栈元素（p，i ）中标号i进行判断，
① 若 i = 0，则将（p，1）压入堆栈；若结点p的左指针不为空，则将（Left(p), 0) 压入堆栈），准备遍历其左子树.
② 若 i = 1，此时已遍历完结点p的左子树，则将（p，2）压入堆栈；若右指针不为空，则将（Right(p), 0)压入堆栈，准备遍历其右子树.
③ 若 i = 2，此时已遍历完结点p的右子树，访问结点p.
算法NPO( t )
/* 设t是指向与图4.9(b)中之表示相同的一棵二叉树T 的根的指针，本非递归算法利用堆栈S以后根序访问T的所有结点*/
NPO1. [初始化]
IF t = L THEN RETURN .
CREATE(S) . S Ü ( t , 0) .
NPO2. [后根遍历]
WHILE S非空 DO
( (p , i) Ü S .
IF i = 0 THEN ( S Ü (p, 1) . IF Left (p) ¹ L THEN S Ü (Left (p), 0) ).
IF i = 1 THEN ( S Ü (p , 2). IF Right (p) ¹ L THEN S Ü (Right (p),0) ) .
IF i = 2 THEN PRINT (Data (p) ).
)▐
图4.13 算法NPO对图4.12(a)中二叉树进行遍历时，栈S之变化。

E,0
C,1
A,2

C,0
A,2

A,1

B,2
A,1

D,2
B,2
A,1

D,1
B,2
A,1

D,0
B,2
A,1

B,1
A,1

B,0
A,1

A,0

访问B

访问D

A,2

C,2
A,2

F,2
C,2
A,2

F,1
C,2
A,2

F,0
C,2
A,2

C,1
A,2

E,2
C,1
A,2

E,1
C,1
A,2

访问A

访问C

访问F

访问E

图4.13栈S之变化

3．层次遍历
除了上述先根序、中根序和后根序等三种遍历方法外，还有一种较常用的遍历方式，被称为层次遍历。层次遍历按层数由小到大，即从第0层开始逐层向下，同层中由左到右的次序访问二叉树的所有结点。对于图4.12(a) 所示的二叉树，其层次遍历的次序为A B C D E F .
(a) 二叉树

F
E
A
C
B
D

二叉树层次遍历算法需要一个辅助队列，具体方法如下：
（1） 根结点入队.
（2） 重复本步骤直至队为空:
若队非空，取队头结点并访问；若其左指针不空，将其左孩子入队，若其右指针不空，将其右孩子入队.

算法LevelOrder ( t )
/* 设t是指向一棵二叉树T之根的指针，本算法层次遍历T */
CREATE ( Q ).
p ¬ t .
IF p ¹ L THEN Q Ü p .
WHILE Q 非空 DO
( p Ü Q .
PRINT ( Data (p) ) .
IF Left (p) ¹ L THEN Q Ü Left (p) .
IF Right (p) ¹ L THEN Q Ü Right (p) .
(a) 二叉树

F
E
A
C
B
D
) ▐

图4.14 层次遍历二叉树的队列变化过程

C
B
访问A
F
访问E
访问F
A
A入队
访问B、D入队
D
C
访问D
E
F
访问C，E、F入队
E
D
F
图4.14 对图4.12(a)中的二叉树进行层次遍历时，队列的变化过程.

4.2.5 创建二叉树
由二叉树的遍历算法，很容易想到用遍历方法去创建二叉树。
递归算法CreateBinTree（简记为CBT）以根指针 t 为输入参数，以包含空指针信息的先根序列为输入序列. 当读入‘#’字符时，将其初始化为一个空指针；否则生成一个新结点并初始化其父结点之左、右指针. 由于序列中用“#”表示空指针，故在算法中设置tostop =‘#’，以便判断序列中的“#”。
算法CBT (tostop . t )
/* 构造以结点t为根的二叉树；tostop =‘#’ */
CBT1. [读数据]
READ (ch) . /* 顺序读入序列中的一个符号 */
CBT2. [ ch = tostop? ]
IF ch = tostop THEN ( t ¬ L . RETURN t . )
ELSE ( t Ü AVAIL . Data(t) ¬ ch . )
CBT3. [构造左子树]
CBT ( . Left (t) ).
CBT4. [构造右子树]
CBT ( . Right(t) ). ▐  

当输入序列为ABD#E###C##时，可创建图4.15(b)所示二叉树.
C
B
E
D
A

图4.15 (b)

4.2.6 复制二叉树
先复制子结点，后复制父结点，然后再将父结点与子结点连接起来，就可自底向上地复制一棵新树。
A
B
D
E
C
图4.16 二叉树Tree_1

算法 CopyTree (t . p )
/* t指向一棵二叉树T的根， 二叉树为T的复制品，p指向之根 */
CopyTree1. [递归出口]
IF t = L THEN RETURN L .
CopyTree2. [复制左子树]
IF Left(t) ¹ L THEN CopyTree(Left(t) . newlptr) ELSE newlptr ¬ L .
CopyTree3. [复制右子树]
IF Right(t) ¹ L THEN CopyTree(Right (t). newrptr) ELSE newrptr ¬ L .
CopyTree4. [生成结点]
p ÜAVAIL.
Data(p) ¬ Data (t) . Left (p) ¬ newlptr . Right(p) ¬ newrptr.
RETURN p. ▐
§4.3 线索二叉树
4.3.1 线索二叉树定义
以Left/Right链接表示的二叉树结构，可看作是有很多从根结点一直到叶结点的单链表组成的，一个结点的前驱结点是其父结点，一个结点的后继结点是它的儿子结点。
这种结构有两方面不足：其一是从一个结点只能访问它的儿子结点，而不能访问它的父结点；其二是这种结构通常包含很多未被有效使用的指针字段（或域），譬如包含i个结点的二叉树，在其2i个指针域中仅有i+1个被使用.
为使二叉树之结点的访问更方便，其空间的利用更高效. 1960年， Perlis A J和Thornton C 提出了巧妙的线索二叉树表示。
(a) 二叉树
A
B
D
E
C
图4.18(a)中二叉树的中根遍历序列为BCAED，其中C是A的中根前驱结点，A是C的中根后继结点。类似也可给出先根前驱（先根后继）结点、后根前驱（后根后继）结点之概念.

正象线性表的双向链表一样，二叉树也可采用双向链接. 如图4.17所示，针对某种遍历顺序，可为二叉树的每个结点增加两个指针域，分别存放指向其前驱和后继结点的指针Pred和Succ，并称Pred和Succ为"线索". 在这样的二叉树中搜索一结点在某种遍历顺序下的前驱或后继结点将变得更加容易，但将增加一些存储空间.
Pred
Left
Data
Right
Succ
图4.17 线索二叉树的结点结构

定义4.6 设T*是由增加某种遍历顺序之线索域的结点（如图4.17）所构成的一棵二叉树，在T*中可直接查找任一结点在这种遍历顺序下的前驱和后继结点，则称T*为线索二叉树 (Threaded Binary Tree) .
若在一棵线索二叉树中，指针Pred和Succ分别指向结点的先根（中根、后根）前驱和先根后继，则称其为先序（中序、后序）线索二叉树.

图4.18 (a)所示二叉树之中根遍历序列为BCAED，它的中序线索二叉树的链接表示如图4.18 (b)所示；其后根序列为CBEDA，它的后序线索二叉树的链接表示如图4.18 (c)所示。
root
Succ
Pred
Succ
(b) 中序线索二叉树的链接表示
Pred
Pred
Pred
Succ
Succ
D
L

L
E
L

L

A

C
L

L

B

L

L

(a) 二叉树
A
B
D
E
C

Pred
Succ
Succ
Pred
Pred
Succ
Succ
(c) 后序线索二叉树的链接表示
图4.18 线索二叉树的链接表示，图中虚线箭头表示线索
root
Pred
A
L

D
L

B
L

L

C
L

L

L

L

E

4.3.2 线索二叉树存储
由上节图4.18可看出，线索二叉树的结点中仍有很多空指针，显然存储空间的浪费问题还未得到有效解决。那么能否通过对上述线索二叉树的改进来解决呢？答案是肯定的。指针域需占用较多的存储空间，例如一个空间容量为4GB的内存储器需要32个二进制位来表示地址，若将指针域中的Pred和Succ换成1个二进制位则会节省许多空间。
基于此，有人给出了线索二叉树的改进方案：
⑴ 将原指针域Pred和Succ分别改成存储一个二进制位的域LThread和RThread .
⑵ 若结点t有左孩子，则Left指向t的左孩子，且LThread的值为0；若t没有左孩子，则Left指向t的前驱结点，且LThread的值为1（此时称Left为线索）.
⑶ 若结点t有右孩子，则Right指向t的右孩子，且RThread的值为0；若t没有右孩子，则Right指向t的后继结点，且RThread的值为1（此时称Right为线索）.
经改进，不仅释放了指针域Pred和Succ所占的较多空间，而且使存放空指针的域Left和Right得以充分利用。在线索二叉树中，叶结点的充要条件为：LThread和RThread的值均是1. 改进后，图4.18 (a)的中序线索二叉树的链接表示如图4.19(a)所示，后序线索二叉树的链接表示如图4.19(b)所示。在图4.19中指向一结点前驱或后继结点的指针用虚线箭头表示。
root
(a) 改进的中序线索二叉树
Pred
Succ
Pred
Succ
0
A
0
D
L
1
0
B
L

1
0

E

1
1

C

1
1
root
Succ
Succ
Succ
Pred
(b) 改进的后序线索二叉树
图4.19 改进的线索二叉树
0
A
0
D

1
0
B

1
0

E

1
1
L
C

1
1
Pred