,数据结构,
第六章 (上 )
数据结构
tjm
第六章 树和二叉树
6.1 树的定义和基本术语
6.2 二叉树
6.2.1 二叉树的定义
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树与线索二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换
6.4.3 树和森林的遍历
6.6 赫夫曼树及其应用
6.6.1 最优二叉树（赫夫曼树）
6.6.2 赫夫曼编码
数据结构
tjm
6.1 树的定义和基本术语
树的定义
树是一类重要的非线性数据结构，是以分支关系
定义的层次结构。
树 (tree)是 n(n>=0)个结点的有限集 T，对于非空树，
其中 有且仅有一个特定的结点，称为树的 根 (root)。
当 n>1时，其余结点可分为 m(m>0)个互不相交的
有限集 T1,T2,……Tm, 其中每一个集合本身又是
一棵树，称为根的 子树 (subtree)。每棵子树的根
结点有且仅有一个直接前驱，但可以有 0个或多个
直接后继。
树的类型定义参见 P118
数据结构
tjm
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根
子树
数据结构
tjm
结点：包含一个数据元素及若干指向子树的分支。
结点的度：结点子树的个数。
树的度,树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点。
分枝结点：度不为 0的结点。
从根到结点的路径：由从根到该结点所经分支和结
点构成。
树的基本术语：
A
B C D
E F G H I J
K L M
数据结构
tjm
孩子结点：结点的子树的根称为该结点的孩子。
双亲结点,B结点是 A结点的孩子，则 A结点是 B结点
的双亲。
兄弟结点：同一双亲的孩子结点。
堂兄结点：同一层上结点。
祖先结点, 从根到该结点的所经分支上的所有结点。
子孙结点：以某结点为根的子树中任一结点都称为
该结点的子孙。
A
B C D
E F G H I J
K L M
数据结构
tjm
结点的层次：根结点的层定义为 1；根的孩子为
第二层结点，依此类推。
树的深度：树中最大的结点层。
有序树：子树有序的树。
无序树：不考虑子树的顺序。
森林,m(m>=0)棵互不相交的树的集合。
A
B C D
E F G H I J
K L M
树的基本操作分为三大类：查找，插入，删除
（参见 P119）
数据结构
tjm
线性结构与树结构的比较：
线性结构：
第一个数据元素（无前驱）
最后一个数据元素（无后继）
其它数据元素（一个前驱，
一个后继）
树：
根结点（无前驱）
多个叶结点（无后继）
树中其它结点（一个
前驱，多个后继）
数据结构
tjm
6.2 二叉树
6.2.1 二叉树的定义
定义：二叉树是 n(n?0)个结点的有限集，它或为
空树 (n=0),或由一个根结点和两棵分别称为左子
树和右子树的互不相交的二叉树构成。
特点：
每个结点至多有二棵子树 (即不存在度大于 2的
结点 )；
二叉树的子树有左、右之分，且其次序不能任
意颠倒。
二叉树的类型定义参见 P121
数据结构
tjm
二叉树的五种基本形态
A
只有根结点
的二叉树
?
空二叉树
A
B
右子树为空
A
B
左子树为空
A
B C
左、右子树
均非空
二叉树的基本操作也分为三大类：查找，插入，
删除（参见 P121）
数据结构
tjm
6.2.2 二叉树的性质
证明：用归纳法证明之：
?i=1时，只有一个根结点,是对的
?假设对所有 j(1?j<i)命题成立，即第 j层上至多有
个结点，那么，第 i-1层至多有 个结
点。又二叉树每个结点的度至多为 2，
? 第 i层上最大结点数是第 i-1层的 2倍，即
故命题得证。
122 01 ???i
12 ?j 22 ?i
12 222 ?? ?? ii
性质 1：在二叉树的第 i层上至多有 个结点（ i>=1）。12?i
证明：由性质 1，可得深度为 k 的二叉树最大结点数是
122)(
1 1
1 ???? ?
? ?
? k
k
i
k
i
ii 层的最大结点数第
性质 2：深度为 k的 二叉树至多有 个结点（ k>=1）。12 ?k
数据结构
tjm
性质 3：对任何一棵二叉树 T,如果其终端结点数 为 n0，
度为 2的结点数为 n2,则 n0=n2+1。
证明：设 n1为二叉树 T中度为 1的结点数。
因为二叉树中所有结点的度均小于或等于 2，
所以其结点总数 n=n0+n1+n2。
又：二叉树中，除根结点外，其余结点都只有
一个分支进入。设 B为分支总数，则 n=B+1。
又：分支由度为 1和度为 2的结点射出，
?B=n1+2n2
于是,n=B+1=n1+2n2+1=n0+n1+n2
?n0=n2+1
数据结构
tjm
两类特殊的二叉树
深度为 k,有 n个结点的二叉树当且仅当其每一个
结点都与深度为 k的满二叉树中编号从 1至 n的结
点一一对应时，称为 完全二叉树 。
特点,叶子结点只可能在层次最大的两层上出现。
对任一结点，若其右分支下子孙的最大层次为 L，
则其左分支下子孙的最大层次必为 L或 L+1。
一棵深度为 k的且有 个结点的二叉树叫 满
二叉树 。
特点：每一层上的结点数都是最大结点数。
12 ?k
满二叉树
完全二叉树
数据结构
tjm
1
2 3
11
4 5
8 9 12 13
6 7
10 14 15
1
2 3
11
4 5
8 9 12
6 7
10
1
2 3
4 5
6 7
1
2 3
4 5 6
数据结构
tjm
性质 5：如果对一棵有 n个结点的完全二叉树的结点
按层序编号，则对任一结点 i(1?i?n),有：
(1)如果 i=1,则结点 i是二叉树的根，无双亲；如果
i>1,则其双亲是结点 ?i/2?。
(2)如果 2i>n,则结点 i无左孩子；如果 2i?n,则其
左孩子是 2i。
(3)如果 2i+1>n,则结点 i无右孩子；否则其右孩子
是 2i+1。
性质 4,具有 n个结点 的完全 二 叉树的深度为 。? ? 1lo g
2 ?n
证明：由性质 2和完全二叉树的定义有：
1212 1 ????? kk n kk n 22 1 ???
knk ??? 2l o g1
K是整数
? ? 1l o g 2 ?? nk
数据结构
tjm
证明（ 2）和（ 3）,
对于 i＝ 1，由完全二叉树的定义，其左孩子是结点 2，
若 2>n，即不存在结点 2，结点 i无孩子。结点 i的右孩子也
只能是结点 3，若结点 3不存在，即 3>n，此时结点 i无右孩
子。
对于 i>1，可分为两种情况：
1）设第 j（ 1<=j<= ?log2n? )层的第一个结点的编号为 i，
由二叉树的性质 2和定义知 i＝ 2j-1
结点 i的左孩子必定为 j＋ 1层的第一个结点，其编号为 2j
＝ 2× 2j-1＝ 2i。 如果 2i>n，则无左孩子。其右孩子必定
为第 j＋ 1层的第二个结点，编号为 2i＋ 1。若 2i+1>n，则
无右孩子。
数据结构
tjm
2）假设第 j（ 1<=j<= ?log2n? )层上的某个结点编号为 i
（ 2j-1<=i<=2j-1),且 2i＋ 1<n，其左孩子为 2i，右孩子
为 2i＋ 1，则编号为 i＋ 1的结点是编号为 i的结点的右兄
弟或堂兄弟。若它有左孩子，则其编号必定为 2i＋ 2＝
2× （ i＋ 1）：若它有右孩子，则其编号必定为 2i＋ 3＝
2× （ i＋ 1）＋ 1。
证明（ 1）,
当 i＝ 1时，就是根，因此无双亲，当 i>1时，如果 i为左孩
子，即 2× （ i/2)=i,则 i/2是 i的双亲；如果 i为右孩子，
i＝ 2p+1,i的双亲应为 p,p＝（ i－ 1） /2= ?i/2? 。
数据结构
tjm
6.2.3 二叉树的存储结构
一、顺序存储结构
实现：按满二叉树的结点层次编号，依次存放二叉
树中的数据元素。
数据结构
tjm
a b c d e 0 0 0 0 f g
0 1 2 3 4 5 6 7 8 9 10
a
b c
d e
f g
特点：结点间关系蕴含在其存储位置中。浪费
空间，适于存满二叉树和完全二叉树。
二、链式存储结构
1、二叉链表存储法 lchild data rchild
数据结构
tjm
A
B
C D
E F
G
在 n个结点的二叉链表中，有 n+1个空指针域 。
A
B
C D
E F
G
^
^ ^
^ ^ ^
^ ^
typedef struct BiTNode
{ TelemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
数据结构
tjm
A
B
C D
E F
G
A
B
C D
E F
G
^ ^
^ ^
^ ^ ^
^ ^
lchild data parent rchild
typedef struct TriTNode
{ TelemType data;
struct TriTNode *lchild,*parent,*rchild;
}TriTNode,*TriTree;
2、三叉链表存储法
数据结构
tjm
6.3.1 遍历二叉树
所谓树的遍历，就是按某种次序访问树中的结点，要
求每个结点访问一次且仅访问一次。
对二叉树，可有三条搜索路径：
1、先上后下的按层次遍历
2、先左（子树）后右（子树）的遍历
6.3 遍历二叉树和线索二叉树
D
L R
DLR, LDR,LRD
3、先右（子树）后左（子树）的遍历
数据结构
tjm
D L R
A
D L R
D L R
B
D
C
D L R
A
D
B C
先序遍历序列,A B D C
算法参见 P129
前序遍历二叉树算法是,
若二叉树为空，则空操作；
否则
访问根结点 (D)；
前序遍历左子树 (L)；
前序遍历右子树 (R)。
前序遍历
数据结构
tjm
中序遍历二叉树算法：
若二叉树为空，则空操作；
否则,
中序遍历左子树 (L)；
访问根结点 (D)；
中序遍历右子树 (R)。
中序遍历
A
D
B C
L D R
B
L D R
L D R
A
D
C
L D R
中序遍历序列,B D A C
数据结构
tjm
后序遍历二叉树算法是,
若二叉树为空，则空操
作；
否则
后序遍历左子树 (L)；
后序遍历右子树 (R)；
访问根结点 (D)。
后序遍历
A
D
B C
L R D
L R D
L R D
A
D
C
L R D
B
后序遍历序列,D B C A
数据结构
tjm
-
+ /
a *
b -
e f
c d
先序遍历：
中序遍历：
后序遍历：
层次遍历：
- + a * b - c d/e f
-+a *b -c d /e f
-+ a* b-cd/ ef
-+a *b -c d /e f
数据结构
tjm
A
B
C D
E F
G
p
P->A
p A
B
C D
E F
G
P->A
P->B
A
B
C D
E F
G
p
P->A
P->B
P->C p=NULL
A
B
C D
E F
G
P->A
P->B
访问,C
中序遍历二叉树的非递归算法
数据结构
tjm
p A
B
C D
E F
G
P->A
访问,C B
p
A
B
C D
E F
G
P->A
P->D
访问,C B
p
A
B
C D
E F
G
P->A
P->D
P->E
访问,C B
p
A
B
C D
E F
G
P->A
P->D
访问,C B E
数据结构
tjm
A
B
C D
E F
G
P->A
P->D
P->G
访问,C B E
P=NULL
A
B
C D
E F
G
P->A
访问,C B E G D
p
A
B
C D
E F
G
P->A
P->F
访问,C B E G D
p
A
B
C D
E F
G
P->A
P->D
访问,C B E G
p
数据结构
tjm
A
B
C D
E F
G
P->A
访问,C B E G D F
p=NULL
A
B
C D
E F
G 访问,C B E G D F A
p
只知道先序或后序序列都无法唯一地确定一棵二
叉树。若给定先序和后序序列则可唯一地确定一
棵二叉树。
算法 参见 P131
数据结构
tjm
A
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^
按先序遍历序列建立二叉树的二叉链表
例：已知先序序列为：
A B C ? ? D E ? G ? ? F ? ? ?
遍历算法的应用
算法 参见 P131
第六章 (上 )
数据结构
tjm
第六章 树和二叉树
6.1 树的定义和基本术语
6.2 二叉树
6.2.1 二叉树的定义
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树与线索二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换
6.4.3 树和森林的遍历
6.6 赫夫曼树及其应用
6.6.1 最优二叉树（赫夫曼树）
6.6.2 赫夫曼编码
数据结构
tjm
6.1 树的定义和基本术语
树的定义
树是一类重要的非线性数据结构，是以分支关系
定义的层次结构。
树 (tree)是 n(n>=0)个结点的有限集 T，对于非空树，
其中 有且仅有一个特定的结点，称为树的 根 (root)。
当 n>1时，其余结点可分为 m(m>0)个互不相交的
有限集 T1,T2,……Tm, 其中每一个集合本身又是
一棵树，称为根的 子树 (subtree)。每棵子树的根
结点有且仅有一个直接前驱，但可以有 0个或多个
直接后继。
树的类型定义参见 P118
数据结构
tjm
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根
子树
数据结构
tjm
结点：包含一个数据元素及若干指向子树的分支。
结点的度：结点子树的个数。
树的度,树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点。
分枝结点：度不为 0的结点。
从根到结点的路径：由从根到该结点所经分支和结
点构成。
树的基本术语：
A
B C D
E F G H I J
K L M
数据结构
tjm
孩子结点：结点的子树的根称为该结点的孩子。
双亲结点,B结点是 A结点的孩子，则 A结点是 B结点
的双亲。
兄弟结点：同一双亲的孩子结点。
堂兄结点：同一层上结点。
祖先结点, 从根到该结点的所经分支上的所有结点。
子孙结点：以某结点为根的子树中任一结点都称为
该结点的子孙。
A
B C D
E F G H I J
K L M
数据结构
tjm
结点的层次：根结点的层定义为 1；根的孩子为
第二层结点，依此类推。
树的深度：树中最大的结点层。
有序树：子树有序的树。
无序树：不考虑子树的顺序。
森林,m(m>=0)棵互不相交的树的集合。
A
B C D
E F G H I J
K L M
树的基本操作分为三大类：查找，插入，删除
（参见 P119）
数据结构
tjm
线性结构与树结构的比较：
线性结构：
第一个数据元素（无前驱）
最后一个数据元素（无后继）
其它数据元素（一个前驱，
一个后继）
树：
根结点（无前驱）
多个叶结点（无后继）
树中其它结点（一个
前驱，多个后继）
数据结构
tjm
6.2 二叉树
6.2.1 二叉树的定义
定义：二叉树是 n(n?0)个结点的有限集，它或为
空树 (n=0),或由一个根结点和两棵分别称为左子
树和右子树的互不相交的二叉树构成。
特点：
每个结点至多有二棵子树 (即不存在度大于 2的
结点 )；
二叉树的子树有左、右之分，且其次序不能任
意颠倒。
二叉树的类型定义参见 P121
数据结构
tjm
二叉树的五种基本形态
A
只有根结点
的二叉树
?
空二叉树
A
B
右子树为空
A
B
左子树为空
A
B C
左、右子树
均非空
二叉树的基本操作也分为三大类：查找，插入，
删除（参见 P121）
数据结构
tjm
6.2.2 二叉树的性质
证明：用归纳法证明之：
?i=1时，只有一个根结点,是对的
?假设对所有 j(1?j<i)命题成立，即第 j层上至多有
个结点，那么，第 i-1层至多有 个结
点。又二叉树每个结点的度至多为 2，
? 第 i层上最大结点数是第 i-1层的 2倍，即
故命题得证。
122 01 ???i
12 ?j 22 ?i
12 222 ?? ?? ii
性质 1：在二叉树的第 i层上至多有 个结点（ i>=1）。12?i
证明：由性质 1，可得深度为 k 的二叉树最大结点数是
122)(
1 1
1 ???? ?
? ?
? k
k
i
k
i
ii 层的最大结点数第
性质 2：深度为 k的 二叉树至多有 个结点（ k>=1）。12 ?k
数据结构
tjm
性质 3：对任何一棵二叉树 T,如果其终端结点数 为 n0，
度为 2的结点数为 n2,则 n0=n2+1。
证明：设 n1为二叉树 T中度为 1的结点数。
因为二叉树中所有结点的度均小于或等于 2，
所以其结点总数 n=n0+n1+n2。
又：二叉树中，除根结点外，其余结点都只有
一个分支进入。设 B为分支总数，则 n=B+1。
又：分支由度为 1和度为 2的结点射出，
?B=n1+2n2
于是,n=B+1=n1+2n2+1=n0+n1+n2
?n0=n2+1
数据结构
tjm
两类特殊的二叉树
深度为 k,有 n个结点的二叉树当且仅当其每一个
结点都与深度为 k的满二叉树中编号从 1至 n的结
点一一对应时，称为 完全二叉树 。
特点,叶子结点只可能在层次最大的两层上出现。
对任一结点，若其右分支下子孙的最大层次为 L，
则其左分支下子孙的最大层次必为 L或 L+1。
一棵深度为 k的且有 个结点的二叉树叫 满
二叉树 。
特点：每一层上的结点数都是最大结点数。
12 ?k
满二叉树
完全二叉树
数据结构
tjm
1
2 3
11
4 5
8 9 12 13
6 7
10 14 15
1
2 3
11
4 5
8 9 12
6 7
10
1
2 3
4 5
6 7
1
2 3
4 5 6
数据结构
tjm
性质 5：如果对一棵有 n个结点的完全二叉树的结点
按层序编号，则对任一结点 i(1?i?n),有：
(1)如果 i=1,则结点 i是二叉树的根，无双亲；如果
i>1,则其双亲是结点 ?i/2?。
(2)如果 2i>n,则结点 i无左孩子；如果 2i?n,则其
左孩子是 2i。
(3)如果 2i+1>n,则结点 i无右孩子；否则其右孩子
是 2i+1。
性质 4,具有 n个结点 的完全 二 叉树的深度为 。? ? 1lo g
2 ?n
证明：由性质 2和完全二叉树的定义有：
1212 1 ????? kk n kk n 22 1 ???
knk ??? 2l o g1
K是整数
? ? 1l o g 2 ?? nk
数据结构
tjm
证明（ 2）和（ 3）,
对于 i＝ 1，由完全二叉树的定义，其左孩子是结点 2，
若 2>n，即不存在结点 2，结点 i无孩子。结点 i的右孩子也
只能是结点 3，若结点 3不存在，即 3>n，此时结点 i无右孩
子。
对于 i>1，可分为两种情况：
1）设第 j（ 1<=j<= ?log2n? )层的第一个结点的编号为 i，
由二叉树的性质 2和定义知 i＝ 2j-1
结点 i的左孩子必定为 j＋ 1层的第一个结点，其编号为 2j
＝ 2× 2j-1＝ 2i。 如果 2i>n，则无左孩子。其右孩子必定
为第 j＋ 1层的第二个结点，编号为 2i＋ 1。若 2i+1>n，则
无右孩子。
数据结构
tjm
2）假设第 j（ 1<=j<= ?log2n? )层上的某个结点编号为 i
（ 2j-1<=i<=2j-1),且 2i＋ 1<n，其左孩子为 2i，右孩子
为 2i＋ 1，则编号为 i＋ 1的结点是编号为 i的结点的右兄
弟或堂兄弟。若它有左孩子，则其编号必定为 2i＋ 2＝
2× （ i＋ 1）：若它有右孩子，则其编号必定为 2i＋ 3＝
2× （ i＋ 1）＋ 1。
证明（ 1）,
当 i＝ 1时，就是根，因此无双亲，当 i>1时，如果 i为左孩
子，即 2× （ i/2)=i,则 i/2是 i的双亲；如果 i为右孩子，
i＝ 2p+1,i的双亲应为 p,p＝（ i－ 1） /2= ?i/2? 。
数据结构
tjm
6.2.3 二叉树的存储结构
一、顺序存储结构
实现：按满二叉树的结点层次编号，依次存放二叉
树中的数据元素。
数据结构
tjm
a b c d e 0 0 0 0 f g
0 1 2 3 4 5 6 7 8 9 10
a
b c
d e
f g
特点：结点间关系蕴含在其存储位置中。浪费
空间，适于存满二叉树和完全二叉树。
二、链式存储结构
1、二叉链表存储法 lchild data rchild
数据结构
tjm
A
B
C D
E F
G
在 n个结点的二叉链表中，有 n+1个空指针域 。
A
B
C D
E F
G
^
^ ^
^ ^ ^
^ ^
typedef struct BiTNode
{ TelemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
数据结构
tjm
A
B
C D
E F
G
A
B
C D
E F
G
^ ^
^ ^
^ ^ ^
^ ^
lchild data parent rchild
typedef struct TriTNode
{ TelemType data;
struct TriTNode *lchild,*parent,*rchild;
}TriTNode,*TriTree;
2、三叉链表存储法
数据结构
tjm
6.3.1 遍历二叉树
所谓树的遍历，就是按某种次序访问树中的结点，要
求每个结点访问一次且仅访问一次。
对二叉树，可有三条搜索路径：
1、先上后下的按层次遍历
2、先左（子树）后右（子树）的遍历
6.3 遍历二叉树和线索二叉树
D
L R
DLR, LDR,LRD
3、先右（子树）后左（子树）的遍历
数据结构
tjm
D L R
A
D L R
D L R
B
D
C
D L R
A
D
B C
先序遍历序列,A B D C
算法参见 P129
前序遍历二叉树算法是,
若二叉树为空，则空操作；
否则
访问根结点 (D)；
前序遍历左子树 (L)；
前序遍历右子树 (R)。
前序遍历
数据结构
tjm
中序遍历二叉树算法：
若二叉树为空，则空操作；
否则,
中序遍历左子树 (L)；
访问根结点 (D)；
中序遍历右子树 (R)。
中序遍历
A
D
B C
L D R
B
L D R
L D R
A
D
C
L D R
中序遍历序列,B D A C
数据结构
tjm
后序遍历二叉树算法是,
若二叉树为空，则空操
作；
否则
后序遍历左子树 (L)；
后序遍历右子树 (R)；
访问根结点 (D)。
后序遍历
A
D
B C
L R D
L R D
L R D
A
D
C
L R D
B
后序遍历序列,D B C A
数据结构
tjm
-
+ /
a *
b -
e f
c d
先序遍历：
中序遍历：
后序遍历：
层次遍历：
- + a * b - c d/e f
-+a *b -c d /e f
-+ a* b-cd/ ef
-+a *b -c d /e f
数据结构
tjm
A
B
C D
E F
G
p
P->A
p A
B
C D
E F
G
P->A
P->B
A
B
C D
E F
G
p
P->A
P->B
P->C p=NULL
A
B
C D
E F
G
P->A
P->B
访问,C
中序遍历二叉树的非递归算法
数据结构
tjm
p A
B
C D
E F
G
P->A
访问,C B
p
A
B
C D
E F
G
P->A
P->D
访问,C B
p
A
B
C D
E F
G
P->A
P->D
P->E
访问,C B
p
A
B
C D
E F
G
P->A
P->D
访问,C B E
数据结构
tjm
A
B
C D
E F
G
P->A
P->D
P->G
访问,C B E
P=NULL
A
B
C D
E F
G
P->A
访问,C B E G D
p
A
B
C D
E F
G
P->A
P->F
访问,C B E G D
p
A
B
C D
E F
G
P->A
P->D
访问,C B E G
p
数据结构
tjm
A
B
C D
E F
G
P->A
访问,C B E G D F
p=NULL
A
B
C D
E F
G 访问,C B E G D F A
p
只知道先序或后序序列都无法唯一地确定一棵二
叉树。若给定先序和后序序列则可唯一地确定一
棵二叉树。
算法 参见 P131
数据结构
tjm
A
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^
按先序遍历序列建立二叉树的二叉链表
例：已知先序序列为：
A B C ? ? D E ? G ? ? F ? ? ?
遍历算法的应用
算法 参见 P131
