1
? 树形结构是结点之间有分支和层次关系的结构
? 树形结构是一种非线性结构
? 在客观世界中，有许多事物本身就呈现树形结
构
– 家族关系
– 部门机构设置
2
? 非递归定义
树结构 是二元组 (D,R),其中, D是 n个数据元素的有穷
集合 （ n≥0） （ 数据元素称为结点 ）, R是 D上的一个关
系 。 n=0时, 称为 空树 ；否则它满足以下条件：
a) 有且仅有一个结点 d0∈ D,满足：不存在任何 d∈ D，
使 <d,d0>∈ R。 我们称它为树的 根 。
b) 除根结点 d0外,D上每个结点 d（若有的话），总存在
一个唯一的结点 d'∈ D,d≠d'，使得 <d',d>∈ R。
3
【 例 5.1】 设有数据结构 T=(D,R),其
中,
D={a,b,c,d,e,f,g}
R={r}
r={<a,b>,<a,c>,<a,d><c,e>,<c,f>,<f,g>}
a
b c d
e f
g
图 - 一棵树
4
其他几个概念
路径, 通路, 如果存在一个结点序列, 使
得 ∈ R,j= 2,...,k,则这样的结点序列称
为从 到 的一条 路径 或 通路 。 也称从 到 有
通路 。 记为
? 其中的结点个数称为 通路长 。有的文献将通路长定义
为通路中的边的个数。
例如, 图 5.1所示图中, 下列结点序列就是几条通路：
(a,b),(a,c,e),(a,b,c,f),(c,f,g),…,
kiii ddd,.,,,,21
?? ? jj ii dd,1
1id kid
1id kid
kiii ddd,.,,,,21
5
其他几个概念
? 子树,若对上面的树 (D,R)，有 D'∈ D,R'∈ R，
R'是 D'上的关系，则如果 <D',R'>满足上面的树
的定义，则称其为 <D,R>的 子树 。
? 若 <D',R'>的根为 x，且 <d,x>∈ R,d∈ D，则
称 <D',R'>为 d的 子树 。
? 若对某结点 d，不存 x∈ D使在 <d,x>∈ R，则称 d
的子树为 空 （ 空子树 ）。
6
其他几个概念
例如, 图 5.1所示图中, 下列二元组都是子树：
a的子树,（ D1,R1）,D1={b},R1={},根为 b;
a的子树,（ D2,R2）,D2={c,e,f,g},R2={<c,e>,<c,f>,
<f,g>},根为 c
a的子树,（ D3,R3）,D3={ d},R3={},根为 d
c的子树,（ D4,R4）,D4={e},R4={},根为 e
c的子树,（ D5,R5）,D5={h,g},R5={<h,g>},根为 h
f的子树,（ D6,R6）,D6={g},R6={},根为 g
b,d,e,g无子树，或说子树为空。
a
b c d
e f
g
图 - 一棵树
7
其他几个概念
?n叉树,若各结点的后继个数均不超过 n,则称该树为 n
叉树 。 例如, 例 5.1给出的树是个 3叉树 。
?有序树,若二元组 (D,R)中的关系集合 R中含有 n个关系
集合 （ n为各结点的最大后继数目 ）, 且每个关系集合都
不与其他关系集合相交, 则称其为有序树 。 有序树实质
上是后继有序的树, 即每个结点的 n个后继次序相关, 不
同的次序排列, 属于不同的结构 。
? 若一棵树是不是有序的，则称为 无序树 。
8
其他几个概念
?例如, 例 5.1给出的树是个 3叉树, 但 R中只含一个集合 r，
所以是无序树 。 若我们重新定义 R(这里是重组合 R):
R={r1,r2,r3}
r1 = {<a,b>,<c,e>}
r2 = {<a,c>,<c,f>,<f,g>}
r3 = {<a,d>}
?则 {D,R}为三叉有序树, r1,r2,r3分别表示第一, 第二,
第三叉 。
9
树的递归定义
?树 是具有 n个结点的有限集合 T(这里 n≥0),若 n=0
则称为空树, 否则, 它满足：
a)有一个特殊结点 d0,我们称它为根 。
b)若 T-{d0}非空，则 T-{d0}可分成 m个 (m>0)不相
交的集合 T1,T2,...,Tm，而且这些集合中的每一个又
都是满足本定义的树，称作 T的 子树 。若 T-{d0}为
空，称 T无子树（或子树为空）。
10
树的递归定义
【 例 5.2】 设有下列集合：
T={a,b,c,d,e,f,g} a
b c d
e f
g
图 - 一棵树
11
树的递归定义
a
b c d
e f
g
图 - 一棵树
?若 T1,T2,…,Tk是子树 （ T1可以不
是其他树的子树 ）, 它们的根分
别是 a1,a2,…,ak,T1的子树是 T2,T2
的子树是 T3,…,Tk-1的子树是 Tk，
则称 a1到 ak有 路径 （ 通路 ）, 记为：
<a1,a2,…,a k>
12
?树枝 （ 分枝 ）,结点之间的二元关系 （ 序偶 ） 。
?度,结点拥有的子树 （ 后继 ） 的个数称为该结点的度,
这实质上是出度 。
?叶子,无后继 （ 子树 ） 的结点称为叶子 。
?分枝结点,有后继的结点称为分枝结点 。
?儿子,结点 x的子树的根称为 x的儿子 。
?双亲 （ 父亲 ）,结点 x的前趋结点称为 x的双亲 。
?祖先,结点 x的父亲称为该结点的祖先；结点 x的父亲的
祖先也称 x的祖先 。
13
?后代,结点 x的儿子称 x的后代, 结点 x的儿子的后代也称
x的后代 。
?兄弟,同父亲的结点称为兄弟结点 。
?堂兄弟,父亲是兄弟关系的结点称为堂兄弟结点 。
?层次 （ 层号 ）,根为第 1层, 对任何其它结点, 若它父亲
为第 k层结点, 则它为第 (k+1)层结点 (层号为 k+1)。
?深度,树中的具有最大层号的结点的层号, 称为树的深
度 。
14
?结点按层编号 （ 层序编号 ）,将树中结点按从上 （ 层 ）
到下 （ 层 ）, 同层从左到右的次序排成一个线性序列, 依
次给它们编以连续的自然数 。
?祖辈 （ 上层 ）,层号比结点 x小的结点, 称为 x的祖辈
（ 上层 ）
?后辈 （ 下层 ）,层号比结点 x大的结点, 称为 x的后辈
（ 下层 ）
?森林,相互不相交的树的集合称为森林 。
?同构,若对两棵树, 通过适当地重命名其中一棵中的结
点, 就可以使两棵树完全相等 （ 结点对应相等, 对应结点
的相关关系也对应相等 ）, 则称这两棵树同构 。
15
? 【 例 5.3】 具有 3个结点的不同构的有序树有下
列几种：
图 - 结点总数为 3的不同构的有序树
16
?若有序树中每个结点的的子树数目不超过 2,则称该树为
二叉树 。 二叉树是树的特例, 空集称仍称为 空 （ 二叉 ） 树 。
?在树的非递归定义中限制结点的后继个数不超过 2,或在
树的递归定义中将 m的上限定为 2即可得到二叉树的严格
定义 。
?在二叉树中, 通常分别称第 1与第 2子树为 左子树 和 右子
树 。
17
(一 ) 满二叉树,
?只含度为 0与度为 2的结点, 且度为 0的结点只出现在最
后一层的二叉树称为 满二叉树 。
?显然, 满二叉树中的任一层上结点都结满了结点, 无空
缺 。 空树和只含一个结点的树也是满二叉树 。 实例见 图
5-3(a).
(a) 满二叉树
18
(一 ) 顺序二叉树
?对任一棵满二叉树, 从它的最后一层的最右结点起, 按
从下到上, 从左到右的次序, 去掉若干个结点后所成的
树称为 顺序二叉树 。
?显然, 顺序二叉树中可含度为 1的结点, 但它们只连续
出现在倒数第 2层上的最右边 。 空树和只含一个结点的树
也是顺序二叉树 。
(b) 顺序二叉树
19
(一 ) 完全二叉树
?不含度为 1的结点的二叉树称 完全二叉树 。
?显然, 完全二叉树与满二叉树的不同是, 它的度为 0的结
点可出现在任一层上 。
?显然, 空树和只含一个结点的树也是完全二叉树 。
(c) 完全二叉树
20
? 顺序、完全二叉树
(d) 顺序、完全二叉树
21
(一 ) 高度平衡二叉树
?若树中任一结点的任两个子树的深度之差不超过 1,则称
这种树为 高度平衡树, 特别是对二叉树, 则为 高度平衡
二叉树 。
?显然, 空树和只含一个结点的树也是平衡树二叉树 。
(e) 平衡二叉树
22
?有下面的结论：
a) 满二叉树, 顺序二叉树均为高度平衡二叉树 。
b) 满二叉树是顺序二叉树 。
c) 满二叉树是完全二叉树 。
?因此, 对顺序二叉树或完全二叉树或平衡二叉树成立的
结论 （ 定理 ）, 对满二叉树也成立 。 对高度平衡二叉树
成立的结论 （ 定理 ）, 对顺序二叉树也成立 。
23
?性质 1,满二叉树第 i层上恰好有 2i-1个结点 (i≥1).
?证：使用归纳法 。 i=1时, 结论显然成立 。 设 i=k时结论
亦成立, 则考虑 i=k+1的情形 。 由于 (k+1)层上结点是 k层
上结点的儿子, 而且满二叉树每个结点恰好有两个儿子,
故 (k+1)层上结点个数为 k层上结点个数的 2倍, 即
2·2k-1 = 2k = 2(k+1)-1.
?这表明, i=k+1时结论也成立 。 证毕 。
24
性质 2,二叉树的第 i层上结点个数不超过 2i-1.(i≥1).
事实上, 这是性质 1的直接推论, 因为任何二叉树,
只有满二叉树的结点最多 。
25
性质 3：深度为 k的满二叉树有 2k-1个结点 。
证：结点总数＝
＝ （ 性质 1）
＝
＝ 2k-1.
?
?
k
i
i
1
层上结点总数）（第
?
?
?
k
i
i
1
12
12
)12(2 11
?
?? k
26
性质 4：深度为 k的二叉树, 至多有 (2k-1)个结点 。
此乃性质 3的直接推论。
27
性质 5：对任一棵二叉树, 有
n0=n2+1 n=2n0+n1-1
这里, n0与 n2分别为度为 0的结点的数目和度为 2的结点的数目 。
证：用 n表示结点总数, 用 n1表示度为 1的结点的数目, 则有
n=n0+n1+n2
另一方面, 由于二叉树除根外每个结点恰好有一个前趋 （ 分枝 ）, 故有
n=B+1
这里, B为分枝数目 。 又分枝是由度为 1和 2的结点射出的, 故有
B=n1+2n2
结合上面三式，即可导出 n0=n2+1与 n=2n0+n1-1
28
性质 6：具有 n个结点的顺序二叉树的深度为 [log2n]+1（ 这里, 符号 [x]表示不
大于 x的最大整数 ） 。
证：设 k为顺序二叉树的深度, 由性质 4知
n ≤ 2k-1
由于 n与 2k均为整数, 故 n<2k,从而
k>log2n ………… (a）
另一方面, 由于是顺序二叉树, 去掉最后一层后必为满二叉树, 故 (k-1)层上
结点数目为 2k-1-1,因此有 n>2k-1-1。 由于 n与 2k-1均为整数, 故 n≥2k-1,即
k≤log2n+1 …………,.(b)
现在我们已得到 (a)与 （ b） 两式, 即
log2n< k≤log2n+1
由于 k为整数，故必有 k=[log2n]+1
29
1单位 1单位, k所在区间
log2n log2n+1[log2n]
图 - log2n<k≤log2n+1示意图
[log2n]+1
30
性质 7：若对一棵顺序二叉树的结点按层序编号
（ 即从根所在层起, 依次从层号较小的层到层号较大
的层, 同层从左到右, 给各结点依次编以连续的号
码 ）, 则对任一结点 i（ 1≤i≤n,n为结点数目, 1为根
的编号 ）, 有
(a)若 i=1,则结点 i是根, 无父亲, 若 i>1,则其父亲
的编号为 [i/2];
(b)若 2i>n,则结点 i无左儿子 （ 从而也无右儿, 为叶
子 ）, 否则 i的左儿子的编号为 2i。
(c)若 2i+1>n，则结点 i无右孩子，否则它的右孩子结
点的编号为 2i+1。
1
2 3
4
(b) 顺序二叉树
5 6
31
(一 )基本概念
? 遍历 就是无重复无遗漏的访问。对于树的遍历，是指按
一定方式访问树中的结点，使得每个结点恰好被访问一
次。
? 访问 是指读、写、修改或其它种类的加工处理。
? 访问方式是指访问次序。
? 访问的轨迹是被访问结点的线性序列，即遍历的结果是
树中各结点按某种次序的一个线性序列，非线性结构被
映射成了线性结构。
? 二叉树的遍历方式有前序遍历、中序遍历、后序遍历与
层序遍历四种
32
(二 ) 前序遍历
?二叉树前序遍历定义为：
?若树为空, 则不作任何动作, 返
回, 否则, 先访问根结点, 然后
按前序方式分别遍历根的左子树
和右子树
?简言之, 前序遍历是按, 根 ─
左子树 ─ 右子树, 的次序遍历二
叉树 。
1
2 3
4
5
6
7
前序遍历结果：
1 2 4 5 3 6 7
33
1
2 3
4
5
6
7
中序遍历结果：
2 5 4 1 3 7 6
(三 ) 中序遍历
二叉树中序遍历定义为：
?若树为空, 则不作任何动作, 返
回, 否则, 先按中序方式遍历根
的左子树, 然后访问根, 最后再
按中序方式遍历根的右子树 。
?简言之，中序遍历是按, 左子树
─ 根 ─ 右子树, 的次序遍历树。
34
1
2 3
4
5
6
7
后序遍历结果：
5 4 2 7 6 3 1
(四 ) 后序遍历
二叉树后序遍历定义为：
?若根为空, 则不作任何动作, 返
回, 否则, 先分别按后序遍历方
式遍历根的左子树与右子树, 然
后访问根 。
?简言之, 后序遍历是按, 左子树
─ 右子树 ─ 根, 的次序遍历二叉
树 。
35
1
2 3
4
5
6
7
层序遍历结果：
1 2 3 4 6 5 7
(五 )层序遍历
? 是按树的层序编号的次序
访问各结点，即按从上层到
下层，同层内从左到右的次
序访问结点。
36
? 二叉树存贮结构应能体现二叉树的逻辑关系，
即单前趋多后继的关系。
? 在具体的应用中，可能要求从任一结点能直接
访问到它的后继（即儿子），或直接访问到它
的前趋（父亲），或同时直接访问父亲和儿子。
? 存贮结构的设计，要按这些条件进行。
37
(一 )顺序二叉树的顺序存贮结构
? 按结点的层序编号的次序，将结点存贮在一片连续存
贮区域内。
? 在这种存贮结构中，很容易根据结点的相对地址计算
出它的父亲和儿子的相对地址
x的相对地址 ?x的编号 (性质 7)?x的父亲 /儿子的编号 ?x
的父亲 /儿子的相对地址。
? 若不进行插入与删除操作，是一种很经济的存贮方式。
38
a
b f
c e g h
d
1 2 3 4 5 6 7 8
a b f c e g h d …
图 - 顺序二叉树的顺序存储
39
? (二 )一般二叉树的顺序存贮
? 在二叉树中补设一些虚结点，使它成为一棵顺
序二叉树，然后对结点按层序编号，这样处理
后，再按顺序二叉树的顺序存贮方式存贮。
a
bM
cM M M
1 2 3 4 5 6 7 9 …
a x b x x x c …
图 - 一般二叉树的连续存贮 (x表示虚结点的位置 )
40
内容 父指针
(a) 一指针结点
内容左儿指针 右儿指针
(b) 二指针结点
内容 父指针 右儿指针 右儿指针
(c) 三指针结点
图 - 二叉树链式存储方式的结点结构
41
(一 )一指针式
? 为每个结点只设立指向其前驱的指针。
? 已知某结点的指针，很容易找到它的父亲
? 但要找到它的儿子，需从叶子起搜索，很耗时。
? 虽可知道儿子，但不能区分是左儿还是右儿。
为了解决该问题，可在结点上设立左右儿标志
位。
42
? (二 )二指针式
? 为每个结点只设立指向其后继的指针。
? 分别称为左儿指针和右儿指针。
? 已知某结点的指针，很容易找到它的儿子
? 但要找到它的父亲，一般需从根起搜索，很耗
时。
43
? (三 )三指针式
? 每个结点分别设立三个指针，分别指向其前驱
和两个后继。
? 三指针式同时具有一指针和二指针的的优点
? 三指针式在关系存储方面有冗余
44
1
2 3
4
5
(a) 二叉树
1 ^
2 3
4
5
(b) (a)树的一指针存储
1
2^ 3 ^^
4 ^
5 ^^
(c) (a)树的二指针存储
1^
2^ 3 ^^
4 ^
5 ^^
(d) (a)树的三指针存储
图 - 二叉树链式存储结构示例
45
? (四 )存储结构的高级语言描述
? 给出二叉树结点（三指针）的数据部分的 C++描述。
template <class TElem>
struct TBinTreeNode
{
TElem info;
TBinTreeNode *father;
TBinTreeNode *lc,*rc;
};
46
? 下面将二叉树看作一个独立的对象，给出它的
属性和方法（基本操作）接口描述。
? 二叉树对象主要涉及两个类：树结点类
TBinTreeNode0和树类 TBinTree,下面分别介绍。
47
§ 5.4.1二叉树结点对象
? 只设置针对结点本身的内容和关系的操作，对涉及全局的操
作，放到“树类”中。
template <class TElem>
class TBinTreeNode0
{
public:
TElem info;
virtual TElem& GetElem(){return info;};
virtual TBinTreeNode0* SetElem(TElem *e){info=*e; return this;};
virtual TBinTreeNode0* GetSon(char sonNo)=0;
virtual TBinTreeNode0* SetSon(char sonNo,TBinTreeNode0* pSon)=0;
48
§ 5.4.1二叉树结点对象
virtual TBinTreeNode0* GetFather()=0;
virtual TBinTreeNode0* SetFather(char sonNo,TBinTreeNode0* f)=0;
char IsLeaf() {return GetSon(1)==NULL && GetSon(2)==NULL;};
};
49
§ 5.4.1二叉树结点对象
(二 ) 动态三指针结点
template <class TElem>
class TBinTreeNode,public TBinTreeNode0<TElem>
{
public:
TBinTreeNode<TElem> *lc,*rc,*father;
TTBinTreeNode(){lc=rc=father=NULL;};
virtual TBinTreeNode0<TElem>* GetSon(char sonNo)
{if (sonNo==1) return lc; else return rc;};
50
§ 5.4.1二叉树结点对象
virtual TBinTreeNode0<TElem>* SetSon(char sonNo,
TBinTreeNode0<TElem>* pSon)
{sonNo==1? lc=(TBinTreeNode<TElem>*)pSon:
rc=(TBinTreeNode<TElem>*)pSon; return pSon;};
virtual TBinTreeNode0<TElem>* GetFather(){return father;};
virtual TBinTreeNode0<TElem> * SetFather (char sonNo,
TBinTreeNode0<TElem>* f)
{sonNo==1? father=(TBinTreeNode<TElem>*)f:
father=(TBinTreeNode<TElem>*)f; return f;};
};
51
§ 5.4.2 二叉树类
? 该树类对各种具体的树结点都是兼容的。
enum TTraverseMode {PreOrder,InOrder,PostOrder,LevelOrder};
template <class TElem>
class TBinTree
{
public:
TBinTreeNode0<TElem> *root;
long numNodes;
TBinTree();
~TBinTree();
构造函数, 充当初始化操作,
其主要任务是置 root为空, 表
示当前包含的树为空树 。
析 构 函 数, 通 过 调 用
ReleaseSubs将树的各个结点所
占空间释放 。
52
§ 5.4.2 二叉树类
virtual TBinTreeNode0<TElem>* GetRoot(){return root;};
返回根结点指针 。
virtual void SetRoot(TBinTreeNode0<TElem>* rt){root=rt;};
设置根指针 。 以上两个操作用于隐蔽 root。
virtual long GetLevel(TBinTreeNode0<TElem>* pNode);
返回结点 pNode在以 root为根的树中的层号 。 定义根的层号为 1。
virtual long GetHeight(TBinTreeNode0<TElem>* pNode);
返回以 pNode为根的树 （ 或子树, 下同 ） 的高度 （ 深度 ） 。 定义根的
高度为 1,空树的高度为 0.
53
§ 5.4.2 二叉树类
virtual long GetNumSubNodes(TBinTreeNode0<TElem>* pNode);
返回以 pNode为根的树中的结点总数 。
virtual long GetNumSubNodes(void);
返回以 pNode为根的树中的结点总数 。
virtual long GetNumLeaves(TBinTreeNode0<TElem>* pNode);
返回以 pNode为根的树中的叶子结点总数 。
virtual long Cluster(TBinTreeNode0<TElem>* pNode,TElem
**e,TTraverseMode tm);
串行聚集：将以 pNode为根的树中的各结点的内容的地址, 按 tm遍历
次序存入 e中, 并返回树 pNode中结点总数 。
54
§ 5.4.2 二叉树类
virtual long Cluster(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe,TTraverseMode tm);
与上面的 Cluster类似, 不同点是存储 （ 返回 ） 各结点的指针 。
virtual long Cluster2(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe,TTraverseMode tm);
与上面参数对应的 Cluster相同, 只是这里给出另一种实现方法 （ 非递
归 ） 。
55
§ 5.4.2 二叉树类
virtual long ClusterDescendants(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe,TTraverseMode tm = PreOrder,int
startLevel=1,int endLevel=-1);
与上面的 Cluster类似, 不同的是, 这里只遍历以 pNode为根的树的
startLevel层到 endLevel层之间的结点 （ 设 pNode为第一层 ） 。
startLevel和 endLevel为正数时, 层号相对于 pNode(其层号设为 1),为
负数时, 表示, 倒数,, 即最深一层为 -1,其上一层为 -2,余类推 。
56
§ 5.4.2 二叉树类
virtual long ClusterAncestors(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe);
聚集祖先 。 将结点 pNode的各祖先结点的指针, 按前序次序存入数组 pe，
并返回其数目 。 注意, 这里 pNode的, 祖先, 是指 pNode,直系, 前代,
即从根到 pNode的路径上的结点 。 另一个 ClusterAnsesters()类似, 不同
的是存储结点的内容的地址 。
virtual long ClusterAncestors(TBinTreeNode0<TElem>* pNode,TElem
**e);
virtual long ClusterAncestors(TElem &e,TBinTreeNode0<TElem>**
pNodes);
57
§ 5.4.2 二叉树类
virtual long ClusterJuniors(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem>**pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
后辈聚集 。 将 pNode的第 startLevel层到第 endLevel层的后辈结点, 按遍历
次序 tm存入 pe,这里, 层号 startLevel和 endLevel是相对于 pNode结点
（ 其为第 1层 ）, 它们取负数是含义同前解释 。 注意, 这里, x“后辈,
是指所有位于 x之下的结点, 包括非直系结点 。
virtual long ClusterSeniors(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
前辈聚集 。 将 pNode的第 startLevel层到第 endLevel层的前辈结点, 按遍历
次序 tm存入 pe,这里, 层号 startLevel和 endLevel是相对于 pNode结点,
pNode层号为 1,pNode 上一层为 2,余类推 。 startLevel和 endLevel取
负数时, 表示层号从总根 （ pNode所在树的根 ） 算起 。
58
§ 5.4.2 二叉树类
virtual TBinTreeNode0<TElem> *DeleteSubTree(
TBinTreeNode0<TElem>* pNode,char sonNo);
删除结点 。 将 pNode 的儿子号为 sonNo的子树, 连根一同摘取下来, 并
返回其根 。
virtual TBinTreeNode0<TElem> *Locate(TBinTreeNode0<TElem>*
rt,TElem *e);
按内容定位 。 在以 rt为根的树中, 查找元素值为 e的结点, 返回其指针 。
找不到时, 返回 NULL。 这里的查找方式是前序, 即按前序遍历的次
序查找 e。 若值为 e的结点存在多个, 返回其第一个出现 。
59
§ 5.4.2 二叉树类
virtual TBinTreeNode0<TElem> *GListToTree(long *gListExp,TElem
*es,long numElem);
串行化结果的还原 。 根据二叉树的广义表表示, 创建二叉树, 返回所创
建的树的根 。 数组 gListExp中存放二叉树的广义表表达式, 数组 es存
放树结点的内容 。 numElem表示待创建的二叉树的元素个数 。
gListExp中, 结点用编号表示, 它所对应的结点内容在 es[k]中, 这里,
k表示某结点在 gListExp中的编号 。
virtual TBinTreeNode0<TElem> *PreOrderExToTree(TElem *nodes,int
numElem);
virtual TBinTreeNode0<TElem> *PreOrderExToTree(TElem *nodes,
int numElem);
串行化结果的还原 。 根据二叉树的前序遍历结果的扩充, 创建二叉树,
返回其根 。 numElem表示待创建的二叉树的元素个数 。
60
§ 5.4.2 二叉树类
virtual long TreeToGList(TBinTreeNode0<TElem> *rt,TElem *e);
广义表串行化 。 将以 rt为根的二出叉树中各结点的内容的地址, 按广义
表形式输出到 e,返回 g广义表的元素个数 。
virtual void Print(TBinTreeNode0<TElem> *rt,char mode);
61
§ 5.5 二叉树的遍历操作的实现
? (一 )前序递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterPre(TBinTreeNode0<TElem>* pNode,TElem ** e,long& cnt)
{
if (pNode==NULL) return 0;
e[cnt++]=&(pNode->GetElem());
ClusterPre(pNode->GetSon(1),e,cnt);
ClusterPre(pNode->GetSon(2),e,cnt);
return cnt;
}
§ 5.5.1 前序遍历操作的实现
62
? 在 ClusterPre中增加的参数 cnt不属于函数接口，只是为了
函数的实现而引入的，所以参数 cnt的出现，破坏接口的
,友好性, 。
template <class TElem>
long TBinTree<TElem>::
ClusterPre(TBinTreeNode0<TElem>* pNode,TElem ** e)
{
long cnt=0;
return ClusterPre(pNode,e,cnt);
}
§ 5.5.1 前序遍历操作的实现
可避免直接调用
ClusterPre(pNode,e,cnt)。
63
? (二 )递归算法的跟踪
(1) C(a)
(2) O(a)
输出, a
(3) C(a->lc) (13) C(a->rc)
(6) C(b->rc)(4) O(b)
输出, b
(5) C(b->lc) (14) O(c)
输出, c
(7) O(d)
输出, d
(8) C(d->lc) (12) C(d->rc)
(9) O(e)
输出, e
(10) C(e->lc) (11) C(e->rc)
(16) C(c->rc)(15) C(c->lc)
图 - 图 5.10所示二叉树的前序遍历递归算法执行过程
a
b c
d
e
图 - 一棵二叉数
64
(三 )前序遍历非递归算法
? 由前序遍历的定义知，遍历某树时，是从根起，顺左分枝往下搜索，
每搜索到一个结点，就访问该结点，直到遇到没有左分枝的结点为
止。
? 然后，返回到已搜索过的最近一个有右儿子的结点处，按同样的方
法顺着它的左分枝往下搜索（访问），如此一直进行，直到所有结
点均已处理完。
? 在访问完某结点后，不能立即放弃它，因为遍历完它的左子树后，
要从它的右儿子起遍历，所以在访问完某结点后，应保存它的指针。
? 由于较先访问到的结点较后才重新利用，故应将访问到的结点按栈
的方式保存。
§ 5.5.1 前序遍历操作的实现
65
(三 )前序遍历非递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterPre2(TBinTreeNode0<TElem>* pNode,TBinTreeNode0<TElem>
**pNodes)
{
long cnt=0;
long nNodes;
long top=0;
TBinTreeNode<TElem>** sk;
TBinTreeNode<TElem>* p;
§ 5.5.1 前序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
66
nNodes=GetHeight(pNode);
if (nNodes<=0) return 0;
sk =new TBinTreeNode<TElem> *[nNodes+1];
if (sk==NULL) throw TExcepComm(3);
p =(TBinTreeNode<TElem> *) pNode;
while (p!=NULL || top!=0)
{
a
b c
d
e
图 - 一棵二叉数
67
if (p!=NULL) {
pNodes[cnt++]= p;
top++; sk[top]=p;
p = (TBinTreeNode<TElem> *)p->GetSon(1);
}
else {
p = sk[top]; top--;
p = (TBinTreeNode<TElem> *)p->GetSon(2);
}
} //while
delete[] sk;
return cnt;
}
a
b c
d
e
图 - 一棵二叉数
68
该算法的执行过程
表 5-1 二叉树非递归算法执行过程
步骤 p所指 栈中内容 访问到的结点 说明
0 a 空 进入循环前
1 b a a a进栈,p指向 a的左儿 (b)
2 ^ a b b b进栈,p指向 b的左儿 (空 )
3 d a b出栈,p指向 b的右儿 (d)
4 e a d d d进栈,p指向 d的左儿 (e)
5 ^ a d e e e进栈,p指向 e的左儿 (空 )
6 ^ a d e出栈,p指向 e的右儿 (空 )
7 ^ a d出栈,p指向 d的右儿 (空 )
8 c 空 a出栈,p指向 a的右儿 (c)
9 ^ c c c进栈,p指向 c的左儿 (空 )
10 ^ 空 c出栈,p指向 c的右儿 (空 )
11 结束
a
b c
d
e
69
时空复杂度分析：
? 每循环一次,p指向一个结点或空目标，所指向的空目标
是无左儿子或无右儿子的结点的空链域，因此所指向的
空目标的次数为 (n+1),n为结点个数，
? 故循环次数为 n+(n+1)=2n+1，从而算法的时间复杂度为
O(n)。
? 由于每个结点恰好进栈 1次，所以栈空间最大需求量是 n
（当树蜕化为线性链时达到最大）。
70
(一 )递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterIn(TBinTreeNode0<TElem>* pNode,TElem ** e,long& cnt)
{
if (pNode==NULL) return 0;
ClusterIn(pNode->GetSon(1),e,cnt);
e[cnt++]=&(pNode->GetElem());
ClusterIn(pNode->GetSon(2),e,cnt);
return cnt;
}
§ 5.5.2 中序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
71
template <class TElem>
ClusterIn(TBinTreeNode0<TElem>* pNode,TElem ** e)
{
long cnt=0;
return ClusterIn(pNode,e,cnt);
}
§ 5.5.2 中序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
72
(二 )非递归算法
?在中序遍历中, 搜索到结点时并不能立即访问, 只是将它
推进栈, 等到左分枝搜索完后再从栈中弹出并访问之 。
?中序遍历的非递归算法, 只需将访问结点语句调到出栈语
句后即可 。
§ 5.5.2 中序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
73
(二 )非递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterIn2(TBinTreeNode0<TElem>* pNode,TBinTreeNode0<TElem>
**pNodes)
{
long cnt=0;
long nNodes;
long top=0;
TBinTreeNode<TElem>** sk;
TBinTreeNode<TElem>* p;
a
b c
d
e
图 - 一棵二叉数
74
nNodes=GetHeight(pNode);
if (nNodes<=0) return 0;
sk =new TBinTreeNode<TElem> *[nNodes+1];
if (sk==NULL) throw TExcepComm(3);
p =(TBinTreeNode<TElem> *) pNode;
while (p!=NULL || top!=0)
{
if (p!=NULL)
{
top++; sk[top]=p;
p = (TBinTreeNode<TElem> *)p->GetSon(1);
}
a
b c
d
e
图 - 一棵二叉数
75
else
{
p = sk[top]; top--;
pNodes[cnt++]= p;
p = (TBinTreeNode<TElem> *)p->GetSon(2);
}
} //while
delete[] sk;
return cnt;
}
a
b c
d
e
图 - 一棵二叉数
76
(一 )递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterPost(TBinTreeNode0<TElem>* pNode,TElem ** e,long & cnt)
{
if (pNode==NULL) return 0;
ClusterPost(pNode->GetSon(1),e,cnt);
ClusterPost(pNode->GetSon(2),e,cnt);
e[cnt++]=&(pNode->GetElem());
return cnt;
}
§ 5.5.3 后序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
77
template <class TElem>
longTBinTree<TElem>::
ClusterPost(TBinTreeNode0<TElem>* pNode,TElem ** e,long & cnt)
{
long cnt=0;
ClusterPost(pNode,e,cnt);
}
§ 5.5.3 后序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
78
(二 ) 非递归算法
?对任一结点, 应先沿它的左分枝往下搜索, 每搜索到一个结点就进栈,
直到遇到一个无左分枝结点为止
?此时应从该结点的右分枝 （ 若有右分枝 ） 的根起, 按同样的方法沿左
分枝处理 。
?处理完右分枝后才能访问该结点 。
?因此, 对任一结点, 当处理完它的左分枝时 （ 此时它位于栈顶 ） 不能
将它弹出栈, 而应继续处理它的右分枝, 直到右分枝处理完后 （ 此时它
又位于栈顶 ） 才能出栈并访问它 。
§ 5.5.3 后序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
79
?因此, 在后序遍历中, 每一结点都有两次出现在栈顶 （ 不包括刚进栈
时的情况 ）, 这两种情况的含意与处理方法为：
结点 p第 1次出现在栈顶：
含意,p的左子树处理完 （ 遍历完 ）, 右子树尚未遍历 。
操作：不出栈, 利用它找到它的右儿子, 遍历它的右子树 。
结点 p第 2次出现在栈顶：
含意,p的右子树已处理 （ 遍历 ） 完 （ 左子树亦遍历完 ） 。
操作：出栈, 并访问它 。
?为了区分是第几次出现在栈顶, 需为每个进栈的结点设个标志域 isFirst，
刚进栈时, 将它置为 1（, 真, ）, 当它第 1次出现在栈顶后, 将它置为
0（, 假, ） 。
§ 5.5.3 后序遍历操作的实现
80
template <class TElem>
longTBinTree<TElem>::
Cluster2(TBinTreeNode0<TElem>* pNode,TBinTreeNode0<TElem>
**pNodes)
{
long cnt=0;
long nNodes;
long top=0;
TBinTreeNode<TElem>* p;
§ 5.5.3 后序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
81
if (pNode==NULL) return 0;
nNodes=GetHeight(pNode);
if (nNodes<=0) return 0;
struct TPostTraverseStackNode
{
TBinTreeNode<TElem> *pNode;
char isFirst;
} ;
TPostTraverseStackNode *sk2;
a
b c
d
e
图 - 一棵二叉数
82
sk2 =new TPostTraverseStackNode [nNodes+1];
if (sk2==NULL) throw TExcepComm(3);
p =(TBinTreeNode<TElem> *) pNode;
while (p!=NULL || top!=0)
{
if (p!=NULL)
{
top++;
sk2[top].pNode=p;
sk2[top].isFirst = 1;
p = (TBinTreeNode<TElem> *)p->GetSon(1);
}
a
b c
d
e
图 - 一棵二叉数
83
else
if (sk2[top].isFirst)
{
sk2[top].isFirst = 0;
p = (TBinTreeNode<TElem> *)(sk2[top].pNode->GetSon(2));
}
else
{
p = sk2[top].pNode;
top--;
pNodes[cnt++]= p;
p=NULL;
}
} //while
delete [] sk2;
return cnt;
}
a
b c
d
e
图 - 一棵二叉数
84
至于二叉树的层序遍历, 易使用非递归算法 。 具体实现时
需使用队列存放结点 （ 利用队列的 FIFO特点 ） 。 具体的实
现程序, 留作练习 。
a
b c
d
e
图 - 一棵二叉数
85
§ 5.6 二叉树的解析表示与存贮结构
之间的转化
? 二叉树的解析表示，是指二叉树的表达式或文
字信息表示，是串行化结果。这种表示应该是
无二义的。
? 解析表示与存贮结构的相互转化具有很大实用
价值。
86
§ 5.6.1 双遍历结果转化为树
可由某种遍历结果唯一地确定一棵二叉树吗？
?二棵不同构的有序二叉树, 但它们分别有着相同的前序遍历序列和
后序遍历序列：
前序,1 2 4 3
后序,4 2 3 1
?同样方法可以证明, 单由中序遍历结果或层序遍历结果亦不能确定
二叉树 。 1
2 3
4
1
2 3
4
图 - 两棵不同构的有序二叉树
87
§ 5.6.1 双遍历结果转化为树
几种遍历结果结合能否唯一地确定二叉树？
?由前序遍历结果和后序遍历结果的结合也不能单独确定
一棵二叉树 。
?可由中序遍历结果与前序遍历结果, 或者中序遍历结果
与后序遍历结果唯一地确定一棵二叉树 。
88
§ 5.6.1 双遍历结果转化为树
由中序遍历序列与前序遍历序列确定对应的二叉树的基本
思想
?用前序序列识别根, 用中序序列区分左右子树 。
?具体构造方法
从前序遍历序列中找出第 1个结点, 其必为待构造的二叉树的根, 然
后在中序遍历序列中查找该结点, 则它 （ 在中序序列中 ） 的左边为左
子树结点, 右边为右子树结点, 这样, 可在前序遍历序列中找出左子
树结点与右子树结点的分界点,
因此, 在前序与中序遍历序列中均找到了根的左子树结点序列与右子
树结点序列, 从而, 可用相同的方法再处理左子树结点序列与右子树
结点序列 。
89
§ 5.6.1 双遍历结果转化为树
【 例 5.4】 设某二叉树的前序与中序遍历序列分别为
前序,1 2 4 6 3 5 7 8
中序,2 6 4 1 3 7 5 8
转化的实现算法,
90
前序遍历序列
：
左子树结点根 右子树结点
k个结点
p1 p1+1 p1+k p1+k+1 p2
中序遍历序列
：
左子树结点
k个结点
i1 i1+k-1
根
i1+k
右子树结点
i1+k+1 i2
图 - 由中序和前序确定二叉树
前序,1 2 4 6 3 5 7 8
中序,2 6 4 1 3 7 5 8
91
1
前 3 5 7 8
中 3 7 5 8
前 2 4 6
中 2 6 4
(a) 分出根 (1)及其左右子树的
前 /中序列
1
前 3 5 7 8
中 3 7 5 8
2
前 4 6
中 6 4
(b) 确定 1的左子树的根 (2)及其
左右子树, 2无左子树1
前 3 5 7 8
中 3 7 5 8
2
4
6
(c) 确定 2的右子树, 根为 4
左子树为 6,右子树空
1
2
4
6
3
前 5 7 8
中 7 5 8
(d) 确定 1的右子树：根为 3，
3无右子树
前序,1 2 4 6 3 5 7 8
中序,2 6 4 1 3 7 5 8
92
1
2
4
6
3
5
7 8
(e) 确定 3的右子树：根为 5，
左右子树分别为 7和 8
图 - 利用中序与前序遍历序列确定二叉树示例
93
template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>:,
InPreToTree(TElem *pa,TElem *ia,long p1,long p2,long i1,long i2)
{
long k;
TBinTreeNode<TElem> *p;
if (i1>i2) return NULL;
k=0;
94
while (pa[p1]!=ia[i1+k]) k++;
p= new TBinTreeNode<TElem>;
p->SetElem(&pa[p1]);
p->SetSon(1,InPreToTree(pa,ia,p1+1,p1+k,i1,i1+k-1) );
p->SetSon(2,InPreToTree(pa,ia,p1+k+1,p2,i1+k+1,i2) );
if (p->GetSon(1)!=NULL) p->GetSon(1)->SetFather(1,p);
if (p->GetSon(2)!=NULL) p->GetSon(2)->SetFather(2,p);
numNodes=p2-p1+1;
return p;
}
? 树形结构是结点之间有分支和层次关系的结构
? 树形结构是一种非线性结构
? 在客观世界中，有许多事物本身就呈现树形结
构
– 家族关系
– 部门机构设置
2
? 非递归定义
树结构 是二元组 (D,R),其中, D是 n个数据元素的有穷
集合 （ n≥0） （ 数据元素称为结点 ）, R是 D上的一个关
系 。 n=0时, 称为 空树 ；否则它满足以下条件：
a) 有且仅有一个结点 d0∈ D,满足：不存在任何 d∈ D，
使 <d,d0>∈ R。 我们称它为树的 根 。
b) 除根结点 d0外,D上每个结点 d（若有的话），总存在
一个唯一的结点 d'∈ D,d≠d'，使得 <d',d>∈ R。
3
【 例 5.1】 设有数据结构 T=(D,R),其
中,
D={a,b,c,d,e,f,g}
R={r}
r={<a,b>,<a,c>,<a,d><c,e>,<c,f>,<f,g>}
a
b c d
e f
g
图 - 一棵树
4
其他几个概念
路径, 通路, 如果存在一个结点序列, 使
得 ∈ R,j= 2,...,k,则这样的结点序列称
为从 到 的一条 路径 或 通路 。 也称从 到 有
通路 。 记为
? 其中的结点个数称为 通路长 。有的文献将通路长定义
为通路中的边的个数。
例如, 图 5.1所示图中, 下列结点序列就是几条通路：
(a,b),(a,c,e),(a,b,c,f),(c,f,g),…,
kiii ddd,.,,,,21
?? ? jj ii dd,1
1id kid
1id kid
kiii ddd,.,,,,21
5
其他几个概念
? 子树,若对上面的树 (D,R)，有 D'∈ D,R'∈ R，
R'是 D'上的关系，则如果 <D',R'>满足上面的树
的定义，则称其为 <D,R>的 子树 。
? 若 <D',R'>的根为 x，且 <d,x>∈ R,d∈ D，则
称 <D',R'>为 d的 子树 。
? 若对某结点 d，不存 x∈ D使在 <d,x>∈ R，则称 d
的子树为 空 （ 空子树 ）。
6
其他几个概念
例如, 图 5.1所示图中, 下列二元组都是子树：
a的子树,（ D1,R1）,D1={b},R1={},根为 b;
a的子树,（ D2,R2）,D2={c,e,f,g},R2={<c,e>,<c,f>,
<f,g>},根为 c
a的子树,（ D3,R3）,D3={ d},R3={},根为 d
c的子树,（ D4,R4）,D4={e},R4={},根为 e
c的子树,（ D5,R5）,D5={h,g},R5={<h,g>},根为 h
f的子树,（ D6,R6）,D6={g},R6={},根为 g
b,d,e,g无子树，或说子树为空。
a
b c d
e f
g
图 - 一棵树
7
其他几个概念
?n叉树,若各结点的后继个数均不超过 n,则称该树为 n
叉树 。 例如, 例 5.1给出的树是个 3叉树 。
?有序树,若二元组 (D,R)中的关系集合 R中含有 n个关系
集合 （ n为各结点的最大后继数目 ）, 且每个关系集合都
不与其他关系集合相交, 则称其为有序树 。 有序树实质
上是后继有序的树, 即每个结点的 n个后继次序相关, 不
同的次序排列, 属于不同的结构 。
? 若一棵树是不是有序的，则称为 无序树 。
8
其他几个概念
?例如, 例 5.1给出的树是个 3叉树, 但 R中只含一个集合 r，
所以是无序树 。 若我们重新定义 R(这里是重组合 R):
R={r1,r2,r3}
r1 = {<a,b>,<c,e>}
r2 = {<a,c>,<c,f>,<f,g>}
r3 = {<a,d>}
?则 {D,R}为三叉有序树, r1,r2,r3分别表示第一, 第二,
第三叉 。
9
树的递归定义
?树 是具有 n个结点的有限集合 T(这里 n≥0),若 n=0
则称为空树, 否则, 它满足：
a)有一个特殊结点 d0,我们称它为根 。
b)若 T-{d0}非空，则 T-{d0}可分成 m个 (m>0)不相
交的集合 T1,T2,...,Tm，而且这些集合中的每一个又
都是满足本定义的树，称作 T的 子树 。若 T-{d0}为
空，称 T无子树（或子树为空）。
10
树的递归定义
【 例 5.2】 设有下列集合：
T={a,b,c,d,e,f,g} a
b c d
e f
g
图 - 一棵树
11
树的递归定义
a
b c d
e f
g
图 - 一棵树
?若 T1,T2,…,Tk是子树 （ T1可以不
是其他树的子树 ）, 它们的根分
别是 a1,a2,…,ak,T1的子树是 T2,T2
的子树是 T3,…,Tk-1的子树是 Tk，
则称 a1到 ak有 路径 （ 通路 ）, 记为：
<a1,a2,…,a k>
12
?树枝 （ 分枝 ）,结点之间的二元关系 （ 序偶 ） 。
?度,结点拥有的子树 （ 后继 ） 的个数称为该结点的度,
这实质上是出度 。
?叶子,无后继 （ 子树 ） 的结点称为叶子 。
?分枝结点,有后继的结点称为分枝结点 。
?儿子,结点 x的子树的根称为 x的儿子 。
?双亲 （ 父亲 ）,结点 x的前趋结点称为 x的双亲 。
?祖先,结点 x的父亲称为该结点的祖先；结点 x的父亲的
祖先也称 x的祖先 。
13
?后代,结点 x的儿子称 x的后代, 结点 x的儿子的后代也称
x的后代 。
?兄弟,同父亲的结点称为兄弟结点 。
?堂兄弟,父亲是兄弟关系的结点称为堂兄弟结点 。
?层次 （ 层号 ）,根为第 1层, 对任何其它结点, 若它父亲
为第 k层结点, 则它为第 (k+1)层结点 (层号为 k+1)。
?深度,树中的具有最大层号的结点的层号, 称为树的深
度 。
14
?结点按层编号 （ 层序编号 ）,将树中结点按从上 （ 层 ）
到下 （ 层 ）, 同层从左到右的次序排成一个线性序列, 依
次给它们编以连续的自然数 。
?祖辈 （ 上层 ）,层号比结点 x小的结点, 称为 x的祖辈
（ 上层 ）
?后辈 （ 下层 ）,层号比结点 x大的结点, 称为 x的后辈
（ 下层 ）
?森林,相互不相交的树的集合称为森林 。
?同构,若对两棵树, 通过适当地重命名其中一棵中的结
点, 就可以使两棵树完全相等 （ 结点对应相等, 对应结点
的相关关系也对应相等 ）, 则称这两棵树同构 。
15
? 【 例 5.3】 具有 3个结点的不同构的有序树有下
列几种：
图 - 结点总数为 3的不同构的有序树
16
?若有序树中每个结点的的子树数目不超过 2,则称该树为
二叉树 。 二叉树是树的特例, 空集称仍称为 空 （ 二叉 ） 树 。
?在树的非递归定义中限制结点的后继个数不超过 2,或在
树的递归定义中将 m的上限定为 2即可得到二叉树的严格
定义 。
?在二叉树中, 通常分别称第 1与第 2子树为 左子树 和 右子
树 。
17
(一 ) 满二叉树,
?只含度为 0与度为 2的结点, 且度为 0的结点只出现在最
后一层的二叉树称为 满二叉树 。
?显然, 满二叉树中的任一层上结点都结满了结点, 无空
缺 。 空树和只含一个结点的树也是满二叉树 。 实例见 图
5-3(a).
(a) 满二叉树
18
(一 ) 顺序二叉树
?对任一棵满二叉树, 从它的最后一层的最右结点起, 按
从下到上, 从左到右的次序, 去掉若干个结点后所成的
树称为 顺序二叉树 。
?显然, 顺序二叉树中可含度为 1的结点, 但它们只连续
出现在倒数第 2层上的最右边 。 空树和只含一个结点的树
也是顺序二叉树 。
(b) 顺序二叉树
19
(一 ) 完全二叉树
?不含度为 1的结点的二叉树称 完全二叉树 。
?显然, 完全二叉树与满二叉树的不同是, 它的度为 0的结
点可出现在任一层上 。
?显然, 空树和只含一个结点的树也是完全二叉树 。
(c) 完全二叉树
20
? 顺序、完全二叉树
(d) 顺序、完全二叉树
21
(一 ) 高度平衡二叉树
?若树中任一结点的任两个子树的深度之差不超过 1,则称
这种树为 高度平衡树, 特别是对二叉树, 则为 高度平衡
二叉树 。
?显然, 空树和只含一个结点的树也是平衡树二叉树 。
(e) 平衡二叉树
22
?有下面的结论：
a) 满二叉树, 顺序二叉树均为高度平衡二叉树 。
b) 满二叉树是顺序二叉树 。
c) 满二叉树是完全二叉树 。
?因此, 对顺序二叉树或完全二叉树或平衡二叉树成立的
结论 （ 定理 ）, 对满二叉树也成立 。 对高度平衡二叉树
成立的结论 （ 定理 ）, 对顺序二叉树也成立 。
23
?性质 1,满二叉树第 i层上恰好有 2i-1个结点 (i≥1).
?证：使用归纳法 。 i=1时, 结论显然成立 。 设 i=k时结论
亦成立, 则考虑 i=k+1的情形 。 由于 (k+1)层上结点是 k层
上结点的儿子, 而且满二叉树每个结点恰好有两个儿子,
故 (k+1)层上结点个数为 k层上结点个数的 2倍, 即
2·2k-1 = 2k = 2(k+1)-1.
?这表明, i=k+1时结论也成立 。 证毕 。
24
性质 2,二叉树的第 i层上结点个数不超过 2i-1.(i≥1).
事实上, 这是性质 1的直接推论, 因为任何二叉树,
只有满二叉树的结点最多 。
25
性质 3：深度为 k的满二叉树有 2k-1个结点 。
证：结点总数＝
＝ （ 性质 1）
＝
＝ 2k-1.
?
?
k
i
i
1
层上结点总数）（第
?
?
?
k
i
i
1
12
12
)12(2 11
?
?? k
26
性质 4：深度为 k的二叉树, 至多有 (2k-1)个结点 。
此乃性质 3的直接推论。
27
性质 5：对任一棵二叉树, 有
n0=n2+1 n=2n0+n1-1
这里, n0与 n2分别为度为 0的结点的数目和度为 2的结点的数目 。
证：用 n表示结点总数, 用 n1表示度为 1的结点的数目, 则有
n=n0+n1+n2
另一方面, 由于二叉树除根外每个结点恰好有一个前趋 （ 分枝 ）, 故有
n=B+1
这里, B为分枝数目 。 又分枝是由度为 1和 2的结点射出的, 故有
B=n1+2n2
结合上面三式，即可导出 n0=n2+1与 n=2n0+n1-1
28
性质 6：具有 n个结点的顺序二叉树的深度为 [log2n]+1（ 这里, 符号 [x]表示不
大于 x的最大整数 ） 。
证：设 k为顺序二叉树的深度, 由性质 4知
n ≤ 2k-1
由于 n与 2k均为整数, 故 n<2k,从而
k>log2n ………… (a）
另一方面, 由于是顺序二叉树, 去掉最后一层后必为满二叉树, 故 (k-1)层上
结点数目为 2k-1-1,因此有 n>2k-1-1。 由于 n与 2k-1均为整数, 故 n≥2k-1,即
k≤log2n+1 …………,.(b)
现在我们已得到 (a)与 （ b） 两式, 即
log2n< k≤log2n+1
由于 k为整数，故必有 k=[log2n]+1
29
1单位 1单位, k所在区间
log2n log2n+1[log2n]
图 - log2n<k≤log2n+1示意图
[log2n]+1
30
性质 7：若对一棵顺序二叉树的结点按层序编号
（ 即从根所在层起, 依次从层号较小的层到层号较大
的层, 同层从左到右, 给各结点依次编以连续的号
码 ）, 则对任一结点 i（ 1≤i≤n,n为结点数目, 1为根
的编号 ）, 有
(a)若 i=1,则结点 i是根, 无父亲, 若 i>1,则其父亲
的编号为 [i/2];
(b)若 2i>n,则结点 i无左儿子 （ 从而也无右儿, 为叶
子 ）, 否则 i的左儿子的编号为 2i。
(c)若 2i+1>n，则结点 i无右孩子，否则它的右孩子结
点的编号为 2i+1。
1
2 3
4
(b) 顺序二叉树
5 6
31
(一 )基本概念
? 遍历 就是无重复无遗漏的访问。对于树的遍历，是指按
一定方式访问树中的结点，使得每个结点恰好被访问一
次。
? 访问 是指读、写、修改或其它种类的加工处理。
? 访问方式是指访问次序。
? 访问的轨迹是被访问结点的线性序列，即遍历的结果是
树中各结点按某种次序的一个线性序列，非线性结构被
映射成了线性结构。
? 二叉树的遍历方式有前序遍历、中序遍历、后序遍历与
层序遍历四种
32
(二 ) 前序遍历
?二叉树前序遍历定义为：
?若树为空, 则不作任何动作, 返
回, 否则, 先访问根结点, 然后
按前序方式分别遍历根的左子树
和右子树
?简言之, 前序遍历是按, 根 ─
左子树 ─ 右子树, 的次序遍历二
叉树 。
1
2 3
4
5
6
7
前序遍历结果：
1 2 4 5 3 6 7
33
1
2 3
4
5
6
7
中序遍历结果：
2 5 4 1 3 7 6
(三 ) 中序遍历
二叉树中序遍历定义为：
?若树为空, 则不作任何动作, 返
回, 否则, 先按中序方式遍历根
的左子树, 然后访问根, 最后再
按中序方式遍历根的右子树 。
?简言之，中序遍历是按, 左子树
─ 根 ─ 右子树, 的次序遍历树。
34
1
2 3
4
5
6
7
后序遍历结果：
5 4 2 7 6 3 1
(四 ) 后序遍历
二叉树后序遍历定义为：
?若根为空, 则不作任何动作, 返
回, 否则, 先分别按后序遍历方
式遍历根的左子树与右子树, 然
后访问根 。
?简言之, 后序遍历是按, 左子树
─ 右子树 ─ 根, 的次序遍历二叉
树 。
35
1
2 3
4
5
6
7
层序遍历结果：
1 2 3 4 6 5 7
(五 )层序遍历
? 是按树的层序编号的次序
访问各结点，即按从上层到
下层，同层内从左到右的次
序访问结点。
36
? 二叉树存贮结构应能体现二叉树的逻辑关系，
即单前趋多后继的关系。
? 在具体的应用中，可能要求从任一结点能直接
访问到它的后继（即儿子），或直接访问到它
的前趋（父亲），或同时直接访问父亲和儿子。
? 存贮结构的设计，要按这些条件进行。
37
(一 )顺序二叉树的顺序存贮结构
? 按结点的层序编号的次序，将结点存贮在一片连续存
贮区域内。
? 在这种存贮结构中，很容易根据结点的相对地址计算
出它的父亲和儿子的相对地址
x的相对地址 ?x的编号 (性质 7)?x的父亲 /儿子的编号 ?x
的父亲 /儿子的相对地址。
? 若不进行插入与删除操作，是一种很经济的存贮方式。
38
a
b f
c e g h
d
1 2 3 4 5 6 7 8
a b f c e g h d …
图 - 顺序二叉树的顺序存储
39
? (二 )一般二叉树的顺序存贮
? 在二叉树中补设一些虚结点，使它成为一棵顺
序二叉树，然后对结点按层序编号，这样处理
后，再按顺序二叉树的顺序存贮方式存贮。
a
bM
cM M M
1 2 3 4 5 6 7 9 …
a x b x x x c …
图 - 一般二叉树的连续存贮 (x表示虚结点的位置 )
40
内容 父指针
(a) 一指针结点
内容左儿指针 右儿指针
(b) 二指针结点
内容 父指针 右儿指针 右儿指针
(c) 三指针结点
图 - 二叉树链式存储方式的结点结构
41
(一 )一指针式
? 为每个结点只设立指向其前驱的指针。
? 已知某结点的指针，很容易找到它的父亲
? 但要找到它的儿子，需从叶子起搜索，很耗时。
? 虽可知道儿子，但不能区分是左儿还是右儿。
为了解决该问题，可在结点上设立左右儿标志
位。
42
? (二 )二指针式
? 为每个结点只设立指向其后继的指针。
? 分别称为左儿指针和右儿指针。
? 已知某结点的指针，很容易找到它的儿子
? 但要找到它的父亲，一般需从根起搜索，很耗
时。
43
? (三 )三指针式
? 每个结点分别设立三个指针，分别指向其前驱
和两个后继。
? 三指针式同时具有一指针和二指针的的优点
? 三指针式在关系存储方面有冗余
44
1
2 3
4
5
(a) 二叉树
1 ^
2 3
4
5
(b) (a)树的一指针存储
1
2^ 3 ^^
4 ^
5 ^^
(c) (a)树的二指针存储
1^
2^ 3 ^^
4 ^
5 ^^
(d) (a)树的三指针存储
图 - 二叉树链式存储结构示例
45
? (四 )存储结构的高级语言描述
? 给出二叉树结点（三指针）的数据部分的 C++描述。
template <class TElem>
struct TBinTreeNode
{
TElem info;
TBinTreeNode *father;
TBinTreeNode *lc,*rc;
};
46
? 下面将二叉树看作一个独立的对象，给出它的
属性和方法（基本操作）接口描述。
? 二叉树对象主要涉及两个类：树结点类
TBinTreeNode0和树类 TBinTree,下面分别介绍。
47
§ 5.4.1二叉树结点对象
? 只设置针对结点本身的内容和关系的操作，对涉及全局的操
作，放到“树类”中。
template <class TElem>
class TBinTreeNode0
{
public:
TElem info;
virtual TElem& GetElem(){return info;};
virtual TBinTreeNode0* SetElem(TElem *e){info=*e; return this;};
virtual TBinTreeNode0* GetSon(char sonNo)=0;
virtual TBinTreeNode0* SetSon(char sonNo,TBinTreeNode0* pSon)=0;
48
§ 5.4.1二叉树结点对象
virtual TBinTreeNode0* GetFather()=0;
virtual TBinTreeNode0* SetFather(char sonNo,TBinTreeNode0* f)=0;
char IsLeaf() {return GetSon(1)==NULL && GetSon(2)==NULL;};
};
49
§ 5.4.1二叉树结点对象
(二 ) 动态三指针结点
template <class TElem>
class TBinTreeNode,public TBinTreeNode0<TElem>
{
public:
TBinTreeNode<TElem> *lc,*rc,*father;
TTBinTreeNode(){lc=rc=father=NULL;};
virtual TBinTreeNode0<TElem>* GetSon(char sonNo)
{if (sonNo==1) return lc; else return rc;};
50
§ 5.4.1二叉树结点对象
virtual TBinTreeNode0<TElem>* SetSon(char sonNo,
TBinTreeNode0<TElem>* pSon)
{sonNo==1? lc=(TBinTreeNode<TElem>*)pSon:
rc=(TBinTreeNode<TElem>*)pSon; return pSon;};
virtual TBinTreeNode0<TElem>* GetFather(){return father;};
virtual TBinTreeNode0<TElem> * SetFather (char sonNo,
TBinTreeNode0<TElem>* f)
{sonNo==1? father=(TBinTreeNode<TElem>*)f:
father=(TBinTreeNode<TElem>*)f; return f;};
};
51
§ 5.4.2 二叉树类
? 该树类对各种具体的树结点都是兼容的。
enum TTraverseMode {PreOrder,InOrder,PostOrder,LevelOrder};
template <class TElem>
class TBinTree
{
public:
TBinTreeNode0<TElem> *root;
long numNodes;
TBinTree();
~TBinTree();
构造函数, 充当初始化操作,
其主要任务是置 root为空, 表
示当前包含的树为空树 。
析 构 函 数, 通 过 调 用
ReleaseSubs将树的各个结点所
占空间释放 。
52
§ 5.4.2 二叉树类
virtual TBinTreeNode0<TElem>* GetRoot(){return root;};
返回根结点指针 。
virtual void SetRoot(TBinTreeNode0<TElem>* rt){root=rt;};
设置根指针 。 以上两个操作用于隐蔽 root。
virtual long GetLevel(TBinTreeNode0<TElem>* pNode);
返回结点 pNode在以 root为根的树中的层号 。 定义根的层号为 1。
virtual long GetHeight(TBinTreeNode0<TElem>* pNode);
返回以 pNode为根的树 （ 或子树, 下同 ） 的高度 （ 深度 ） 。 定义根的
高度为 1,空树的高度为 0.
53
§ 5.4.2 二叉树类
virtual long GetNumSubNodes(TBinTreeNode0<TElem>* pNode);
返回以 pNode为根的树中的结点总数 。
virtual long GetNumSubNodes(void);
返回以 pNode为根的树中的结点总数 。
virtual long GetNumLeaves(TBinTreeNode0<TElem>* pNode);
返回以 pNode为根的树中的叶子结点总数 。
virtual long Cluster(TBinTreeNode0<TElem>* pNode,TElem
**e,TTraverseMode tm);
串行聚集：将以 pNode为根的树中的各结点的内容的地址, 按 tm遍历
次序存入 e中, 并返回树 pNode中结点总数 。
54
§ 5.4.2 二叉树类
virtual long Cluster(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe,TTraverseMode tm);
与上面的 Cluster类似, 不同点是存储 （ 返回 ） 各结点的指针 。
virtual long Cluster2(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe,TTraverseMode tm);
与上面参数对应的 Cluster相同, 只是这里给出另一种实现方法 （ 非递
归 ） 。
55
§ 5.4.2 二叉树类
virtual long ClusterDescendants(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe,TTraverseMode tm = PreOrder,int
startLevel=1,int endLevel=-1);
与上面的 Cluster类似, 不同的是, 这里只遍历以 pNode为根的树的
startLevel层到 endLevel层之间的结点 （ 设 pNode为第一层 ） 。
startLevel和 endLevel为正数时, 层号相对于 pNode(其层号设为 1),为
负数时, 表示, 倒数,, 即最深一层为 -1,其上一层为 -2,余类推 。
56
§ 5.4.2 二叉树类
virtual long ClusterAncestors(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe);
聚集祖先 。 将结点 pNode的各祖先结点的指针, 按前序次序存入数组 pe，
并返回其数目 。 注意, 这里 pNode的, 祖先, 是指 pNode,直系, 前代,
即从根到 pNode的路径上的结点 。 另一个 ClusterAnsesters()类似, 不同
的是存储结点的内容的地址 。
virtual long ClusterAncestors(TBinTreeNode0<TElem>* pNode,TElem
**e);
virtual long ClusterAncestors(TElem &e,TBinTreeNode0<TElem>**
pNodes);
57
§ 5.4.2 二叉树类
virtual long ClusterJuniors(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem>**pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
后辈聚集 。 将 pNode的第 startLevel层到第 endLevel层的后辈结点, 按遍历
次序 tm存入 pe,这里, 层号 startLevel和 endLevel是相对于 pNode结点
（ 其为第 1层 ）, 它们取负数是含义同前解释 。 注意, 这里, x“后辈,
是指所有位于 x之下的结点, 包括非直系结点 。
virtual long ClusterSeniors(TBinTreeNode0<TElem>* pNode,
TBinTreeNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1);
前辈聚集 。 将 pNode的第 startLevel层到第 endLevel层的前辈结点, 按遍历
次序 tm存入 pe,这里, 层号 startLevel和 endLevel是相对于 pNode结点,
pNode层号为 1,pNode 上一层为 2,余类推 。 startLevel和 endLevel取
负数时, 表示层号从总根 （ pNode所在树的根 ） 算起 。
58
§ 5.4.2 二叉树类
virtual TBinTreeNode0<TElem> *DeleteSubTree(
TBinTreeNode0<TElem>* pNode,char sonNo);
删除结点 。 将 pNode 的儿子号为 sonNo的子树, 连根一同摘取下来, 并
返回其根 。
virtual TBinTreeNode0<TElem> *Locate(TBinTreeNode0<TElem>*
rt,TElem *e);
按内容定位 。 在以 rt为根的树中, 查找元素值为 e的结点, 返回其指针 。
找不到时, 返回 NULL。 这里的查找方式是前序, 即按前序遍历的次
序查找 e。 若值为 e的结点存在多个, 返回其第一个出现 。
59
§ 5.4.2 二叉树类
virtual TBinTreeNode0<TElem> *GListToTree(long *gListExp,TElem
*es,long numElem);
串行化结果的还原 。 根据二叉树的广义表表示, 创建二叉树, 返回所创
建的树的根 。 数组 gListExp中存放二叉树的广义表表达式, 数组 es存
放树结点的内容 。 numElem表示待创建的二叉树的元素个数 。
gListExp中, 结点用编号表示, 它所对应的结点内容在 es[k]中, 这里,
k表示某结点在 gListExp中的编号 。
virtual TBinTreeNode0<TElem> *PreOrderExToTree(TElem *nodes,int
numElem);
virtual TBinTreeNode0<TElem> *PreOrderExToTree(TElem *nodes,
int numElem);
串行化结果的还原 。 根据二叉树的前序遍历结果的扩充, 创建二叉树,
返回其根 。 numElem表示待创建的二叉树的元素个数 。
60
§ 5.4.2 二叉树类
virtual long TreeToGList(TBinTreeNode0<TElem> *rt,TElem *e);
广义表串行化 。 将以 rt为根的二出叉树中各结点的内容的地址, 按广义
表形式输出到 e,返回 g广义表的元素个数 。
virtual void Print(TBinTreeNode0<TElem> *rt,char mode);
61
§ 5.5 二叉树的遍历操作的实现
? (一 )前序递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterPre(TBinTreeNode0<TElem>* pNode,TElem ** e,long& cnt)
{
if (pNode==NULL) return 0;
e[cnt++]=&(pNode->GetElem());
ClusterPre(pNode->GetSon(1),e,cnt);
ClusterPre(pNode->GetSon(2),e,cnt);
return cnt;
}
§ 5.5.1 前序遍历操作的实现
62
? 在 ClusterPre中增加的参数 cnt不属于函数接口，只是为了
函数的实现而引入的，所以参数 cnt的出现，破坏接口的
,友好性, 。
template <class TElem>
long TBinTree<TElem>::
ClusterPre(TBinTreeNode0<TElem>* pNode,TElem ** e)
{
long cnt=0;
return ClusterPre(pNode,e,cnt);
}
§ 5.5.1 前序遍历操作的实现
可避免直接调用
ClusterPre(pNode,e,cnt)。
63
? (二 )递归算法的跟踪
(1) C(a)
(2) O(a)
输出, a
(3) C(a->lc) (13) C(a->rc)
(6) C(b->rc)(4) O(b)
输出, b
(5) C(b->lc) (14) O(c)
输出, c
(7) O(d)
输出, d
(8) C(d->lc) (12) C(d->rc)
(9) O(e)
输出, e
(10) C(e->lc) (11) C(e->rc)
(16) C(c->rc)(15) C(c->lc)
图 - 图 5.10所示二叉树的前序遍历递归算法执行过程
a
b c
d
e
图 - 一棵二叉数
64
(三 )前序遍历非递归算法
? 由前序遍历的定义知，遍历某树时，是从根起，顺左分枝往下搜索，
每搜索到一个结点，就访问该结点，直到遇到没有左分枝的结点为
止。
? 然后，返回到已搜索过的最近一个有右儿子的结点处，按同样的方
法顺着它的左分枝往下搜索（访问），如此一直进行，直到所有结
点均已处理完。
? 在访问完某结点后，不能立即放弃它，因为遍历完它的左子树后，
要从它的右儿子起遍历，所以在访问完某结点后，应保存它的指针。
? 由于较先访问到的结点较后才重新利用，故应将访问到的结点按栈
的方式保存。
§ 5.5.1 前序遍历操作的实现
65
(三 )前序遍历非递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterPre2(TBinTreeNode0<TElem>* pNode,TBinTreeNode0<TElem>
**pNodes)
{
long cnt=0;
long nNodes;
long top=0;
TBinTreeNode<TElem>** sk;
TBinTreeNode<TElem>* p;
§ 5.5.1 前序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
66
nNodes=GetHeight(pNode);
if (nNodes<=0) return 0;
sk =new TBinTreeNode<TElem> *[nNodes+1];
if (sk==NULL) throw TExcepComm(3);
p =(TBinTreeNode<TElem> *) pNode;
while (p!=NULL || top!=0)
{
a
b c
d
e
图 - 一棵二叉数
67
if (p!=NULL) {
pNodes[cnt++]= p;
top++; sk[top]=p;
p = (TBinTreeNode<TElem> *)p->GetSon(1);
}
else {
p = sk[top]; top--;
p = (TBinTreeNode<TElem> *)p->GetSon(2);
}
} //while
delete[] sk;
return cnt;
}
a
b c
d
e
图 - 一棵二叉数
68
该算法的执行过程
表 5-1 二叉树非递归算法执行过程
步骤 p所指 栈中内容 访问到的结点 说明
0 a 空 进入循环前
1 b a a a进栈,p指向 a的左儿 (b)
2 ^ a b b b进栈,p指向 b的左儿 (空 )
3 d a b出栈,p指向 b的右儿 (d)
4 e a d d d进栈,p指向 d的左儿 (e)
5 ^ a d e e e进栈,p指向 e的左儿 (空 )
6 ^ a d e出栈,p指向 e的右儿 (空 )
7 ^ a d出栈,p指向 d的右儿 (空 )
8 c 空 a出栈,p指向 a的右儿 (c)
9 ^ c c c进栈,p指向 c的左儿 (空 )
10 ^ 空 c出栈,p指向 c的右儿 (空 )
11 结束
a
b c
d
e
69
时空复杂度分析：
? 每循环一次,p指向一个结点或空目标，所指向的空目标
是无左儿子或无右儿子的结点的空链域，因此所指向的
空目标的次数为 (n+1),n为结点个数，
? 故循环次数为 n+(n+1)=2n+1，从而算法的时间复杂度为
O(n)。
? 由于每个结点恰好进栈 1次，所以栈空间最大需求量是 n
（当树蜕化为线性链时达到最大）。
70
(一 )递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterIn(TBinTreeNode0<TElem>* pNode,TElem ** e,long& cnt)
{
if (pNode==NULL) return 0;
ClusterIn(pNode->GetSon(1),e,cnt);
e[cnt++]=&(pNode->GetElem());
ClusterIn(pNode->GetSon(2),e,cnt);
return cnt;
}
§ 5.5.2 中序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
71
template <class TElem>
ClusterIn(TBinTreeNode0<TElem>* pNode,TElem ** e)
{
long cnt=0;
return ClusterIn(pNode,e,cnt);
}
§ 5.5.2 中序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
72
(二 )非递归算法
?在中序遍历中, 搜索到结点时并不能立即访问, 只是将它
推进栈, 等到左分枝搜索完后再从栈中弹出并访问之 。
?中序遍历的非递归算法, 只需将访问结点语句调到出栈语
句后即可 。
§ 5.5.2 中序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
73
(二 )非递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterIn2(TBinTreeNode0<TElem>* pNode,TBinTreeNode0<TElem>
**pNodes)
{
long cnt=0;
long nNodes;
long top=0;
TBinTreeNode<TElem>** sk;
TBinTreeNode<TElem>* p;
a
b c
d
e
图 - 一棵二叉数
74
nNodes=GetHeight(pNode);
if (nNodes<=0) return 0;
sk =new TBinTreeNode<TElem> *[nNodes+1];
if (sk==NULL) throw TExcepComm(3);
p =(TBinTreeNode<TElem> *) pNode;
while (p!=NULL || top!=0)
{
if (p!=NULL)
{
top++; sk[top]=p;
p = (TBinTreeNode<TElem> *)p->GetSon(1);
}
a
b c
d
e
图 - 一棵二叉数
75
else
{
p = sk[top]; top--;
pNodes[cnt++]= p;
p = (TBinTreeNode<TElem> *)p->GetSon(2);
}
} //while
delete[] sk;
return cnt;
}
a
b c
d
e
图 - 一棵二叉数
76
(一 )递归算法
template <class TElem>
longTBinTree<TElem>::
ClusterPost(TBinTreeNode0<TElem>* pNode,TElem ** e,long & cnt)
{
if (pNode==NULL) return 0;
ClusterPost(pNode->GetSon(1),e,cnt);
ClusterPost(pNode->GetSon(2),e,cnt);
e[cnt++]=&(pNode->GetElem());
return cnt;
}
§ 5.5.3 后序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
77
template <class TElem>
longTBinTree<TElem>::
ClusterPost(TBinTreeNode0<TElem>* pNode,TElem ** e,long & cnt)
{
long cnt=0;
ClusterPost(pNode,e,cnt);
}
§ 5.5.3 后序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
78
(二 ) 非递归算法
?对任一结点, 应先沿它的左分枝往下搜索, 每搜索到一个结点就进栈,
直到遇到一个无左分枝结点为止
?此时应从该结点的右分枝 （ 若有右分枝 ） 的根起, 按同样的方法沿左
分枝处理 。
?处理完右分枝后才能访问该结点 。
?因此, 对任一结点, 当处理完它的左分枝时 （ 此时它位于栈顶 ） 不能
将它弹出栈, 而应继续处理它的右分枝, 直到右分枝处理完后 （ 此时它
又位于栈顶 ） 才能出栈并访问它 。
§ 5.5.3 后序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
79
?因此, 在后序遍历中, 每一结点都有两次出现在栈顶 （ 不包括刚进栈
时的情况 ）, 这两种情况的含意与处理方法为：
结点 p第 1次出现在栈顶：
含意,p的左子树处理完 （ 遍历完 ）, 右子树尚未遍历 。
操作：不出栈, 利用它找到它的右儿子, 遍历它的右子树 。
结点 p第 2次出现在栈顶：
含意,p的右子树已处理 （ 遍历 ） 完 （ 左子树亦遍历完 ） 。
操作：出栈, 并访问它 。
?为了区分是第几次出现在栈顶, 需为每个进栈的结点设个标志域 isFirst，
刚进栈时, 将它置为 1（, 真, ）, 当它第 1次出现在栈顶后, 将它置为
0（, 假, ） 。
§ 5.5.3 后序遍历操作的实现
80
template <class TElem>
longTBinTree<TElem>::
Cluster2(TBinTreeNode0<TElem>* pNode,TBinTreeNode0<TElem>
**pNodes)
{
long cnt=0;
long nNodes;
long top=0;
TBinTreeNode<TElem>* p;
§ 5.5.3 后序遍历操作的实现
a
b c
d
e
图 - 一棵二叉数
81
if (pNode==NULL) return 0;
nNodes=GetHeight(pNode);
if (nNodes<=0) return 0;
struct TPostTraverseStackNode
{
TBinTreeNode<TElem> *pNode;
char isFirst;
} ;
TPostTraverseStackNode *sk2;
a
b c
d
e
图 - 一棵二叉数
82
sk2 =new TPostTraverseStackNode [nNodes+1];
if (sk2==NULL) throw TExcepComm(3);
p =(TBinTreeNode<TElem> *) pNode;
while (p!=NULL || top!=0)
{
if (p!=NULL)
{
top++;
sk2[top].pNode=p;
sk2[top].isFirst = 1;
p = (TBinTreeNode<TElem> *)p->GetSon(1);
}
a
b c
d
e
图 - 一棵二叉数
83
else
if (sk2[top].isFirst)
{
sk2[top].isFirst = 0;
p = (TBinTreeNode<TElem> *)(sk2[top].pNode->GetSon(2));
}
else
{
p = sk2[top].pNode;
top--;
pNodes[cnt++]= p;
p=NULL;
}
} //while
delete [] sk2;
return cnt;
}
a
b c
d
e
图 - 一棵二叉数
84
至于二叉树的层序遍历, 易使用非递归算法 。 具体实现时
需使用队列存放结点 （ 利用队列的 FIFO特点 ） 。 具体的实
现程序, 留作练习 。
a
b c
d
e
图 - 一棵二叉数
85
§ 5.6 二叉树的解析表示与存贮结构
之间的转化
? 二叉树的解析表示，是指二叉树的表达式或文
字信息表示，是串行化结果。这种表示应该是
无二义的。
? 解析表示与存贮结构的相互转化具有很大实用
价值。
86
§ 5.6.1 双遍历结果转化为树
可由某种遍历结果唯一地确定一棵二叉树吗？
?二棵不同构的有序二叉树, 但它们分别有着相同的前序遍历序列和
后序遍历序列：
前序,1 2 4 3
后序,4 2 3 1
?同样方法可以证明, 单由中序遍历结果或层序遍历结果亦不能确定
二叉树 。 1
2 3
4
1
2 3
4
图 - 两棵不同构的有序二叉树
87
§ 5.6.1 双遍历结果转化为树
几种遍历结果结合能否唯一地确定二叉树？
?由前序遍历结果和后序遍历结果的结合也不能单独确定
一棵二叉树 。
?可由中序遍历结果与前序遍历结果, 或者中序遍历结果
与后序遍历结果唯一地确定一棵二叉树 。
88
§ 5.6.1 双遍历结果转化为树
由中序遍历序列与前序遍历序列确定对应的二叉树的基本
思想
?用前序序列识别根, 用中序序列区分左右子树 。
?具体构造方法
从前序遍历序列中找出第 1个结点, 其必为待构造的二叉树的根, 然
后在中序遍历序列中查找该结点, 则它 （ 在中序序列中 ） 的左边为左
子树结点, 右边为右子树结点, 这样, 可在前序遍历序列中找出左子
树结点与右子树结点的分界点,
因此, 在前序与中序遍历序列中均找到了根的左子树结点序列与右子
树结点序列, 从而, 可用相同的方法再处理左子树结点序列与右子树
结点序列 。
89
§ 5.6.1 双遍历结果转化为树
【 例 5.4】 设某二叉树的前序与中序遍历序列分别为
前序,1 2 4 6 3 5 7 8
中序,2 6 4 1 3 7 5 8
转化的实现算法,
90
前序遍历序列
：
左子树结点根 右子树结点
k个结点
p1 p1+1 p1+k p1+k+1 p2
中序遍历序列
：
左子树结点
k个结点
i1 i1+k-1
根
i1+k
右子树结点
i1+k+1 i2
图 - 由中序和前序确定二叉树
前序,1 2 4 6 3 5 7 8
中序,2 6 4 1 3 7 5 8
91
1
前 3 5 7 8
中 3 7 5 8
前 2 4 6
中 2 6 4
(a) 分出根 (1)及其左右子树的
前 /中序列
1
前 3 5 7 8
中 3 7 5 8
2
前 4 6
中 6 4
(b) 确定 1的左子树的根 (2)及其
左右子树, 2无左子树1
前 3 5 7 8
中 3 7 5 8
2
4
6
(c) 确定 2的右子树, 根为 4
左子树为 6,右子树空
1
2
4
6
3
前 5 7 8
中 7 5 8
(d) 确定 1的右子树：根为 3，
3无右子树
前序,1 2 4 6 3 5 7 8
中序,2 6 4 1 3 7 5 8
92
1
2
4
6
3
5
7 8
(e) 确定 3的右子树：根为 5，
左右子树分别为 7和 8
图 - 利用中序与前序遍历序列确定二叉树示例
93
template <class TElem>
TBinTreeNode0<TElem> *TBinTree<TElem>:,
InPreToTree(TElem *pa,TElem *ia,long p1,long p2,long i1,long i2)
{
long k;
TBinTreeNode<TElem> *p;
if (i1>i2) return NULL;
k=0;
94
while (pa[p1]!=ia[i1+k]) k++;
p= new TBinTreeNode<TElem>;
p->SetElem(&pa[p1]);
p->SetSon(1,InPreToTree(pa,ia,p1+1,p1+k,i1,i1+k-1) );
p->SetSon(2,InPreToTree(pa,ia,p1+k+1,p2,i1+k+1,i2) );
if (p->GetSon(1)!=NULL) p->GetSon(1)->SetFather(1,p);
if (p->GetSon(2)!=NULL) p->GetSon(2)->SetFather(2,p);
numNodes=p2-p1+1;
return p;
}
