Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 1页第 6章 二叉树和树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 2页树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，
它非常类似于自然界中的树。树结构在客观世界中是大量存在的。例如家谱、行政组织机构都可用树形象地表示。
树结构在计算机领域中也有着广泛的应用，
例如在编译程序中，用树结构来表示源程序的语法结构；在数据库系统中，可用树结构来组织信息；在分析算法的行为时，可用树结构来描述其执行过程等等。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 3页
6.1 二叉树二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 4页
6.1.1 二叉树的定义
二叉树（ Binary Tree） 是由 n(n≥0) 个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。
这是一个 递归 定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 5页基本术语
结点 (node)——表示树中的元素，
包括数据项及若干指向其子树的分支
结点的度 (degree)——结点拥有的子树数
叶子 (leaf)——度为 0的结点
孩子 (child)——结点子树的根称为该结点的孩子
双亲 (parents)——孩子结点的上层结点叫该结点的 ~
1
2 3
11
4 5
8 9 12
6 7
10
兄弟 (sibling)——同一双亲的孩子
树的度 ——一棵树中最大的结点度数
结点的层次 (level)——从根结点算起，根为第一层，它的孩子为第二层 ……
深度 (depth)——树中结点的最大层次数
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 6页二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二差树的 5种基本形态，图 (C) 和图（ d）是不同的两棵二叉树。
(a)
空二叉树
A A
B
A
B
A
CB
(b)
根和空的左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树二叉树的 5种形式示意二叉树的 5种形式
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 7页
1、满二叉树 (Full Binary Tree)
一棵深度为 k且由 2k-1个结点组成的二叉树称为满二叉树。下图就是一棵满二叉树，对结点进行了顺序编号。
满二叉树示例
2
4 5
3
6 7
1
特殊形态的二叉树：满二叉树、完全二叉树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 8页
2、完全二叉树 (Complete Binary Tree)
如果一棵二叉树各层都是,满的,,只是最下一层从右边起连续缺少几个结点，称此二叉树为 完全二叉树 。
可见，满二叉树是完全二叉树的特例。
1
2 3
5 6
完全二叉树示例
4
1
2 3
4 5 7
1
2 3
6 7
非完全二叉树示例满二叉树：
完全二叉树：
1
2
4 5
8 9 10 11
3
6 7
12 13 14 15
1
2
4 5
8 9 10 11
3
6 7
12
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 10页二叉树的操作
1、建立一棵空二叉树,InitialBTree(BT)
初始条件：无；
操作结果：构造一棵空树 BT。
2、按某种规则建立一棵二叉树,CreateBTree(BT)
初始条件：无；
操作结果：按某种规则构造一棵二叉树 BT。
3、求二叉树 BT的树根结点,RootBTree(BT)
初始条件：二叉树 BT已存在；
操作结果：返回二叉树 BT的根结点。
4、求二叉树 BT中结点 p的双亲,ParentBTree(BT,p)
初始条件：二叉树 BT已经存在，且 p是二叉树 BT中的一个结点；
操作结果：若结点 p不是二叉树 BT的根结点，则返回结点 p的双亲结点；
否则，返回 NULL。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 11页
5、求二叉树 BT中结点 p的左孩子结点,LeftChildBTree(BT,p)
初始条件：二叉树 BT已经存在，且 p是二叉树 BT中的一个结点；
操作结果：若结点 p不是二叉树 BT的叶子结点，则返回结点 p的左孩子结点；否则，返回 NULL。
6、求二叉树 BT中结点 p的右孩子结点,RightChildBTree(BT,p)
初始条件：二叉树 BT已经存在，且结点 p是二叉树 BT中的一个结点；
操作结果：若结点 p不是二叉树 BT的叶子结点，则返回结点 p的右孩子结点；否则，返回 NULL。
7、判断二叉树 BT是否为空,EmptyBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：若二叉树 BT为空，则返回 True；否则，返回 False。
8、求二叉树 BT的深度,DepthBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：返回二叉树 BT的深度。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 12页
9、将结点 p作为二叉树 BT中结点 q的左子树插入：
InsertLeftBTree(BT,p,q)
初始条件：二叉树 BT已经存在，且结点 q是二叉树 BT中的结点；
操作结果：将结点 p作为二叉树 BT中结点 q的左子树插入 。
10、将结点 p作为二叉树 BT中结点 q的右子树插入：
InsertRightBTree(BT,p,q)
初始条件：二叉树 BT已经存在，且结点 q是二叉树 BT中的结点；
操作结果：将结点 p作为二叉树 BT中结点 q的右子树插入。
11、在二叉树 BT中删除结点 p的左子树,DeleteLChBTree(BT,p)
初始条件：二叉树 BT已经存在，结点 p是二叉树 BT中的结点；
操作结果：在二叉树 BT中删除结点 p的左子树。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 13页
12、在二叉树 BT中删除结点 p的右子树,DeleteRChBTree(BT,p)
初始条件：二叉树 BT已经存在，结点 p是二叉树 BT中的结点；
操作结果：在二叉树 BT中删除结点 p的右子树。
13、给二叉树 BT中结点 p赋值,AssignNodeBTree(BT,p,x)
初始条件：二叉树 BT已经存在，且结点 p是二叉树 BT中的结点；
操作结果：将 x赋值给二叉树 BT中的结点 p。
14、求二叉树 BT中结点 p的左子树,GetLChBTree(BT,p)
初始条件：二叉树 BT已经存在，结点 p是二叉树 BT中的结点；
操作结果：若 p是非叶子结点，则返回结点 p的左子树，否则返回 NULL。
15、求二叉树 BT中结点 p的右子树,GetRChBTree(BT,p)
初始条件：二叉树 BT已经存在，结点 p是二叉树 BT中的结点；
操作结果：若 p是非叶子结点，则返回结点 p的右子树，否则返回 NULL。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 14页
16、按前序遍历方式遍历二叉树 BT,PreOrderTraverseBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：按前序遍历方式遍历二叉树 BT，返回前序遍历序列。
17、按中序遍历方式遍历二叉树 BT,InOrderTraverseBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：按中序遍历方式遍历二叉树 BT，返回中序遍历序列。
18、按后序遍历方式遍历二叉树 BT,PostOrderTraverseBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：按后序遍历方式遍历二叉树 BT，返回后序遍历序列。
19、按层次遍历方式遍历二叉树 BT：
LevelOrderTraverseBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：按层次遍历方式遍历二叉树 BT，返回层次遍历序列。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 15页
6.1.2 二叉树的性质性质 1,在二叉树的第 i层上至多有 2i-1个结点 (i>=1)。
证明：
采用归纳法证明此性质。
当 i=1时，只有一个根结点,2i-1=20 =1,命题成立。
现在假定对所有的 j,1≤j<i,命题成立，即第 j层上至多有 2j-1个结点，那么可以证明 j＝ i时命题也成立。由归纳假设可知，第 i－ 1层上至多有 2i-2个结点。
由于二叉树每个结点的度最大为 2，故在第 i层上最大结点数为第 i-
1层上最大结点数的二倍，
即 2× 2i-2＝ 2i-1。
命题得到证明。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 16页性质 2：深度为 k的二叉树至多有 2k－ 1个结点（ k≥1) 。
证明：
深度为 k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质 1得到每层上的最大结点数。
122
1
1
k
k
i
i
1
2
4 5
8 9 10 11
3
6 7
12 13 14 15
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 17页性质 3,对任何一棵二叉树，如果其终端结点数为 n0，度为 2的结点数为 n2，则 n0＝ n2＋ 1。
证明：
设二叉树中度为 1的结点数为 n1，二叉树中总结点数为 n，
则有,n＝ n0＋ n1＋ n2 (6-1)
再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设 B为二叉树中的分支总数，则有,n＝ B＋ 1
由于这些分支都是由度为 1和 2的结点产生的，则有：
B＝ n1+2*n2
n＝ B＋ 1＝ n1＋ 2× n2＋ 1 （ 6－ 2)
由式（ 6－ 1）和（ 6－ 2）得到：
n0+n1+n2=n1+2*n2+1
n0＝ n2＋ 1
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 18页性质 4,具有 n个结点的完全二叉树的深度为：
log2n? + 1。
证明：假设完全二叉树的深度为 k。
由性质 2和完全二叉树的定义可知：
或者对上式取对数则有：
由于 k是整数，则,k =?log2n? + 1
1212 1 kk n kk n 22 1
knk 2l o g1
1
2
4 5
8 9 10 11
3
6 7
12
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 19页性质 5,具有 n个结点的完全二叉树，如果从根结点开始，
从上到下为每一个结点从左到右进行编号，那么就有：
⑴ 若 i=1，则结点为二叉树的根，无双亲结点。否则，若
i>1，则 i结点父结点的编号为?i/2?；
⑵ 若 2i≤n,则结点的左孩子结点的编号为 2i；否则结点 i
无左孩子（叶子结点）
⑶ 若 2i+1≤n,则结点的左孩子结点的编号为 2i+1；否则无有孩子证明：可以采用数学归纳法。
正是由于完全二叉树具有如此特点，所以完全或满二叉树可以采用一个一维数组来存储。
1
2
4 5
8 9 10 11
3
6 7
12
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 20页
6.1.3 二叉树的存储结构
1.顺序存储方法：
它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法。
#define maxsize 100
typedef telemtype sqbitree[maxsize];
Sqbitree bt；
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 21页从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为 H
且只有 H个结点的右单支树确需要 2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好的！
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 22页
a b c d e f g h i j k l
1 2 3 4 5 6 7 8 9 10 11 12
完全二叉树的顺序存储过程示例
a
b c
d e f g
h i j k l
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 23页
A
B C
D E
F G
表示该处没有元素存在仅仅为了好理解
A B C D E F G
一般二叉树的顺序存储过程示例
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 24页
2.二叉链表法存储二叉树经常用二叉链表表示法。
lchild data rchild
A
B
C D
E
G
F
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 25页二叉树的二叉链表的数据结构：
Typedef struct BiTNode {
TElemType data;
struct BiTNode *LChild,*RChild;
}BiTnode,*BiTree;
有时也可用数组的下标来模拟指针,即开辟三个一维数组 Data,lchild,rchild 分别存储结点的元素及其左、右指针域 ;
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 26页
3.三叉链表法有时，为了便于找到结点的双亲结点，人们经常采用三叉链表来表示给定的二叉树。
Parent RchildDataLchild 三叉链表结点结构图三叉链表存储结构图
A
B^ ^C
D E^
^F^ ^G^ ^H^
^
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 27页二叉树的三叉链表的数据结构：
Typedef struct BTTNode {
TElemType data;
struct BTTNode *Parent,*LChild,*RChild;
}*BTTree;
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 28页
6.2 二叉树遍历在二叉树的一些应用中，常常要求在二叉树中查找具有某种特征的结点，或者对二叉树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访二叉树中的每一个结点，使得 每一个结点均被访问一次，
而且仅被访问一次 。
遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 29页假如以 L,D,R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有 DLR,LDR,LRD,DRL,RDL、
RLD六种遍历方案。若我们规定以根为中心，先左子树后右子树的原则，则只有前三种情况，分别规定为：
DLR——先（根）序遍历；
LDR——中（根）序遍历；
LRD——后（根）序遍历。
L R
D (根结点 )
(右子树 )
(左子树 )
由二叉树的递归定义，
二叉树的三个基本组成单元是：根结点、左子树和右子树。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 30页
1、先序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）访问根结点；
（ 2）先序遍历左子树；
（ 3）先序遍历右子树。
2、中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）中序遍历左子树；
（ 2）访问根结点；
（ 3）中序遍历右子树。
3、后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）后序遍历左子树；
（ 2）后序遍历右子树；
（ 3）访问根结点。
当然二叉树具有层次的概念，所以，二叉树还有一种按方式，就是按层次遍历二叉树，即从二叉树的根开始，按从上到下、从左到右的顺序遍历二叉树。
L R
D (根结点 )
(右子树 )
(左子树 )
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 31页遍历二叉树的三种方法：
先序遍历二叉树
（ 1）访问根结点
（ 2）先序遍历左子树
（ 3）先序遍历右子树
^
A ^
B
^ C ^ D
^ E ^ F
^ G ^
A B C D E G F
中序遍历二叉树
（ 1）中序遍历左子树
（ 2）访问根结点
（ 3）中序遍历右子树
^
A ^
B
^ C ^ D
^ E ^ F
^ G ^
C B E G D F A
后序遍历二叉树
（ 1）后序遍历左子树
（ 2）后序遍历右子树
（ 3）访问根结点
^
A ^
B
^ C ^ D
^ E ^ F
^ G ^
C G E F D B A
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 34页遍历算法先序遍历,D L R
中序遍历,L D R
后序遍历,L R D
A
D
B C
T1
T2
T3
D L R
A
D L R
D L R
B
D
C
D L R
以先序遍历 D L R
为例演示遍历过程
ABDC
BDAC
DBCA
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 35页
-
*
A B
C
－
* C
A B
-
*
A B
C
先 序遍历 - * A B C
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 36页
-
*
A B
C
－
* C
A B
-
*
A B
C
中序遍历 A * B - C
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 37页
-
*
A B
C
－
* C
A B
-
*
A B
C
后序遍历 A B * C -
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 38页
6.2.2 遍历算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 39页算法 6.1
void Preorder(BiTree T,void(*visit)( BiTree )){
// 先序遍历以 T为根指针的二叉树
if (T) { // T=NULL时，二叉树为空树，不做任何操作
visit(T);
// 通过函数指针 *visit访问根结点，以便灵活完成相应的操作
Preorder(T->lchild,visit); // 先序遍历左子树
Preorder(T->rchild,visit); // 先序遍历右子树
}
}
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 40页
void Preorder (BiTree T,void(*visit)( BiTree )){
if (T) {
visit(T);
Preorder(T->lchild,visit);
Preorder(T->rchild,visit); }
}
主程序
Pre( T )
返回返回
pre(T R);
返回返回
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
返回
T
左是空返回
pre(T R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T R);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 41页
typedef enum{Travel=1,Visit=0} TaskType;
typedef struct{
BiTree ptr; //指向结点的指针
TaskType task; //当前的任务
}SElemType;
算法 6.2（采用非递归方式中序遍历）
void InOrder_iter( BiTree BT,void(*visit)( BiTree ) ) {
//利用栈实现中序遍历二叉树,BT为指向二叉树的根结点的头指针
InitStack(S);
e.ptr=BT; e.task=Travel; // e为栈元素
if(BT) Push(S,e); // 布置初始任务
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 42页算法 6.2
while(!StackEmpty(S)) { // 每次处理一项任务
Pop(S,e);
if(e.task==Visit) visit(e.ptr); // 处理访问任务
else
if(e.ptr){ // 处理非空树的遍历任务
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
// 最不迫切任务 (遍历右子树 )进栈
e.ptr=p; e.task=Visit; Push(S,e);
//处理访问任务的工作状态进栈
e.ptr=p->lchild; e.task=Travel; Push(S,e);
// 迫切任务 (遍历左子树 )进栈
}//if
}//while
}//InOrder_iter
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 43页
A T
A Te
A
B
D
C
E ^
^
^
^
^ ^
P
A VC TB T
e.ptr=BT; e.task=Travel;
if(BT) Push(S,e); // 布置初始任务
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 44页
A
B
D
C
E ^
^
^
^
^ ^
B Te
A VC TB T A VC T
P
D TA V
C T
B V^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 45页
A
B
D
C
E ^
^
^
^
^ ^
^ Te
P
P
D TA V
C T
B V^ T D T
A VC T
B V
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 46页
A
B
D
C
E ^
^
^
^
^ ^
e
P
P
D TA V
C T
B V D T
A VC T
B V
输出 B
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 47页
A
B
D
C
E ^
^
^
^
^ ^
e
P
D TA V
C T
D T
A VC T
输出 B
A VC T^ T
D VE T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 48页
A
B
D
C
E ^
^
^
^
^ ^
e
P
E T
输出 B
A VC T^ T
D VE T
A VC T^ T
D V
A VC T^ T
D V^ T
E V^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 49页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
输出 B
A VC T^ T
D V^ T
E V^ T
A VC T^ T
D V^ T
E V
e
A VC T^ T
D V^ T
E V
输出 E
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 50页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
A VC T^ T
D V^ T
A VC T^ T
D V
e
A VC T^ T
D V
输出 D
输出 BE
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 51页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
A VC T^ T
e
C TA VC T
A V
输出 A
输出 BED
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 52页
A
B
D
C
E ^
^
^
^
^ ^
e
P
C T
C T
输出 BEDA
^ TC V
^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 53页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
输出 BEDA
^ TC V
^ T
^ TC V
C Ve
^ T
输出 C
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 54页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
输出 BEDAC
^ T OVER
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 55页建立二叉链表树以字符串的形式 (根 左子树 右子树 )定义一棵二叉树例如,
A
B
C
D
以字符,#” 表示
A(B(#,C(#,#)),D(#,#))
空树只含一个根结点的二叉树 A 以字符串,A##” 表示以下列字符串表示
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 56页算法 6.3
void CreatebiTree(BiTree &T){
// 在先序遍历二叉树过程中输入结点字符，建立二叉链表存储结
//构，指针 T指向所建二叉树的根结点
cin >> ch ；
if (ch=='#') T=NULL; // 建空树
else {
T = new BiTNode ; // "访问 "操作为生成根结点
T->data = ch;
CreateBiTree(T->lchild); // 递归建 (遍历 )左子树
CreateBiTree(T->rchild); // 递归建 (遍历 )右子树
}//else
}//CreateBiTree
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 57页
AT
ch=A
T
T
A
creat(T L)
Λ
T= Λ,Creat(T) 返回
creat(T R) T
ch=#
DΛ
||
=
返回
creat(T R)
D
=T
ch=#
ΛΛ
返回
ch=D
T
T
D
creat(T L)
=||
Φ
Φ
creat(T R)
ch=C
T
T
C
creat(T L)
– +
ch=B
T
T
B
creat(T L)
T
ch=#
BΛ
T
CΛ
ch=#
–
+
返回
creat(T R) T
CΛ
ch=#
Λ
+
返回
A
BΛ
A
BΛ
D|| =
A
DΛ Λ
A
BΛ
DΛ Λ
C– +Λ Λ
输入,A B # D # # C # #
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 58页算法 6.4 求二叉树树深（先序）
void BiTreeDepth(BiTree T,int h,int &depth){
// h为 T指向的结点所在层次,T指向二叉树的根，则 h的初
//值为 1,depth为当前求得的最大层次,其初值为 0
if (T){
if (h>depth) depth=h;
BiTreeDepth(T->lchild,h+1,depth);
BiTreeDepth(T->rchild,h+1,depth);
}
}//BiTreeDepth
主函数调用：
d=0
BiTreeDepth(r,1,d)
A
B
D
C
E ^
^
^
^
^ ^
T
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 59页算法 6.5 求二叉树树深（后序）
int BiTreeDepth(BiTree T) {
// 后序遍历求 T所指二叉树的深度
if (!T) return 0;
else {
hL=BiTreeDepth(T->lchild);
hR=BiTreeDepth(T->rchild);
if (hL>=hR) return hL+1;
else return hR+1;
}
}//BiTreeDepth
A
B
D
C
E ^
^
^
^
^ ^
T
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 60页算法 6.6 复制一棵二叉树
BiTNode *CopyTree(BiTNode *T){
// 已知二叉树的根指针为 T，本算法返回它的复制品的根指针
if (!T ) return NULL; // 复制一棵空树
if (T->lchild )
newlptr = CopyTree(T->lchild); // 复制 (遍历 )左子树
else newlptr = NULL;
if (T->rchild )
newrptr = CopyTree(T->rchild); // 复制 (遍历 )右子树
else newrptr = NULL;
newnode = GetTreeNode(T->data,newlptr,newrptr); //生成根结点
return newnode;
}
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 61页生成一个二叉树的结点
BiTNode *GetTreeNode(TElemType item,BiTNode *lptr,
BiTNode *rptr ){
//生成一个二叉树的结点,其数据域为 item,
//左指针域为 lptr,右指针域为 rptr)
T = new BiTNode;
T-> data = item;
T-> lchild = lptr; T-> rchild = rptr;
return T;
}
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 62页
A
B
C
D
E
F
G
H K
A
例如，下列二叉树的复制过程如下：
newT
^ B E ^
C ^
^ D ^
F ^
G
^ H ^ ^ K ^
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 63页
a+b
(a+b)× c – d/ea+b× c
表达式的二叉树的表示,
a b
+
a
b c
×
+
a b
c
×
+
(a+b)× c
a b
c d e
-
×
+
/
特点,
操作数 为叶子结点运算符 为分支结点
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 64页例右图所示的二叉树表达式
(a+b*(c-d))-e/f
若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：
-+a*b-cd/ef （前缀表达式）
按中序遍历,其中序序列为：
a+b*c-d-e/f （中缀表达式）
按后序遍历,其后序序列为：
abcd-*+ef/- （后缀表达式）
－
＋
*a
/
b -
dc
fe
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 65页计算表达式的值 (a+b*(c-d))-e/f
－
＋
*a
/
b -
dc
fe
-2
-1
-30
-4
1 -2
32
54
3.1 4.2 2.4 3.8 7.2 2.4abcd-*+ef/- （后缀表达式） opnd
0 1 2 3 4 5
数据结构的表示
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 66页算法 6.7
double value(BiTree T,float opnd[]){
// 对以 T为根指针的二叉树表示的算术表达式求值，
// 操作数的数值存放在一维数组 opnd中
if (!T) return 0; // 空树的值为 0
if (T->data>=0) return opnd[T->data];
Lv = value(T->lchild,opnd); // 遍历左子树求第一操作数
Rv = value(T->rchild,opnd); // 遍历右子树求第二操作数
switch (T->data){
case PLUS,v = Lv + Rv;
case MINUS,v = Lv - Rv;
case ASTERISK,v = LV * Rv;
case SLANT,v = Lv / Rv;
default,ERROR("不合法的运算符 ");
}//switch
return v;
}//value
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 67页由二叉树的先序和中序序列建树仅知二叉树的先序序列,abcdefg” 不能唯一确定一棵二叉树，
如果同时已知二叉树的中序序列,cbdaegf”,则会如何？
二叉树的先序序列二叉树的中序序列左子树左子树 右子树右子树根根
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 68页
a b c d e f g
c b d a e g f
例如,b f
a
b
c d
e
f
g
^ ^ ^ ^
^
^ ^
^
先序序列中序序列
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 69页性质 7,通过一棵二叉树的前序遍历序列和中序遍历序列，能够构造出唯一的一棵二叉树 BT。
性质 6,对于给定一棵二叉树 BT，它的前序遍历序列、中序遍历序列及后序遍历序列是唯一的。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 70页例如：已知二叉树 BT的后序遍历序列为,CBEHGIFDA，中序遍历序列为,BCAEDGHFI，请构造这棵二叉树 T。
A
BC DEF
GHI
A
DEF
GHI
B
C FGHI
A
B
C
D
E
GH
A
B
C
D
E F
I
A
B
C
D
E F
H
G I
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 71页
6.2.4 线索二叉树
遍历二叉树的结果是，求得结点的一个线性序列。
例如,
先序序列,
A B C D E F G H K
中序序列,
B D C A H G K F E
后序序列,
D C B H K G F E A
A
B
C
D
E
F
G
H K
当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能找到结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 72页指向该线性序列中的,前驱,和
,后继,的指针，称作,线索,
与其相应的二叉树，称作
,线索二叉树,
包含,线索,的存储结构，
称作,线索链表,
A B C D E F G H K
^ D ^
C ^
^ B E ^
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 73页线索二叉树的定义
Typedef struct BiThrNode{
TelemType data;
struct BiThrNode *lchild,*rchild; //左,右孩子指针
struct BiThrNode *pred,*succ; //前驱与后继线索
}BiThrNode,*BiThrTree;
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 74页
-
*
A B
C -
* Λ C Λ
Λ A Λ Λ B Λ
中序线索链表中序遍历 A * B - C
head表示指向孩子表示线索 Λ
左 数据 右前 后
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 75页算法 6.8
void InOrder(BiThrTree H,void(*visit)( BiTree ) ){
// H 为指向中序线索链表中头结点的指针，
// 本算法中序遍历以 H->lchild所指结点为根的二叉树
p = H->succ;
while( p!=H ) {
visit(p);
p = p-> succ;
}
}//InOrder
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 76页算法 6.9
void InOrderThreading(BiThrTree &H,BiThrTree T){
// 建立根指针 T所指二叉树的中序全线索链表,H指向该线索链表的头结点
H = new BiThrNode; // 创建线索链表的头结点
H->lchild = T; H->rchild = NULL;
if (!T) {
H->pred = H;
H->succ = H;}// 空树头结点的线索指向头结点本身
else {
pre = H;
// 对二叉树进行中序遍历，在遍历过程中进行线索化
InThreading(T,pre);
pre->succ = H; H->pred = pre;
}
}//InOrderThreading
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 77页算法 6.10
void InThreading(BiThrTree p,BiThrTree &pre){
// 对以根指针 p所指二叉树进行中序遍历，在遍历过程中进行线索化
// p为当前指针,pre是跟随指针，比 p慢一拍遍历全二叉树
if (p) {
InThreading(p->lchild,pre); // 左子树线索化
pre->succ = p; p->pred = pre; // 建立线索
pre = p; // 保持 pre指向 p的前驱
InThreading(p->rchild,pre); // 右子树线索化
}
}//InThreading
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 78页二叉树性质：
n个结点的二叉树存在 n+1个空链域。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 79页暂停，继续
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 80页为了避免混淆，必须增加两个标志位：
ltag data rchildrtaglchild
0 lchild域指向结点的左孩子
ltag=
1 lchild域指向结点的前驱
0 rchild域指向结点的右孩子
rtag=
1 rchild域指向结点的后继概念：线索链表，线索，线索二叉树，线索化
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 81页
-
*
A B
C 0 - 0
0 * 0 1 C 1
1 A 1 1 B 1
中序线索链表中序遍历 A * B - C
0 1
head
最后结点右指针指向头结点头结点左指针指向首结点 头结点右指针指向最后结点表示指向孩子表示线索
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 82页
typedef struct BiThrNod {
TElemType data;
struct BiThrNode *lchild,*rchild; // 左右指针
PointerThr LTag,RTag; // 左右标志
} BiThrNode,*BiThrTree;
线索链表 的类型描述：
typedef enum { Link,Thread } PointerThr;
// Link==0:指针,Thread==1:线索
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 83页线索链表的遍历算法,
由于在线索链表中添加了遍历中得到的“前驱”和
“后继”的信息，从而简化了遍历的算法。
for ( p = firstNode(T); p; p = Succ(p) )
Visit (p);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 84页
Status InOrderTraverse_Thr(BiThrTree T,(*Visit)(TElemType e))
{
// T指向头结点，头结点的左链 lchild指向根结点，头结点的右链
//lchild指向中序遍历的最后一个结点。中序遍历二叉线索链表表示
//的二叉树，对每个数据元素调用函数 Visit。
p = T->lchild; // p指向根结点
while (p != T) { // 空树或遍历结束时,p==T
while (p->LTag==Link) p = p->lchild;
Visit(p->data) // 访问其左子树为空的结点
while (p->RTag==Thread && p->rchild!=T) {
p = p->rchild; Visit(p->data); // 访问后继结点
}
p = p->rchild; // p进至其右子树根
}
return OK;
} // InOrderTraverse_Thr
-
*
A B
C
T
0 1
LTag RTag
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 85页在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针 pre,并始终保持指针 pre指向当前访问的、指针 p所指结点的前驱。
如何建立线索链表
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 86页
Status InOrderThreading(BiThrTree &Thrt,BiThrTree T) {
// 中序遍历二叉树 T，并将其中序线索化,Thrt指向头结点。
if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
exit (OVERFLOW);
Thrt->LTag = Link; Thrt->RTag =Thread; // 建头结点
Thrt->rchild = Thrt; // 右指针回指
if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指
else {
Thrt->lchild = T; pre = Thrt;
InThreading(T); // 中序遍历进行中序线索化
pre->rchild = Thrt; pre->RTag = Thread;
// 最后一个结点线索化
Thrt->rchild = pre;
}
return OK;
} // InOrderThreading
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 87页
void InThreading(BiThrTree p) {
if (p) {
InThreading(p->lchild); // 左子树线索化
if (!p->lchild) {
p->LTag = Thread;
p->lchild = pre;
} // 建前驱线索
if (!pre->rchild) {
pre->RTag = Thread;
pre->rchild = p;
} // 建后继线索
pre = p; // 保持 pre指向 p的前驱
InThreading(p->rchild); // 右子树线索化
}
} // InThreading
1 1
p
0 1
pre
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 1页第 6章 二叉树和树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 2页树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，
它非常类似于自然界中的树。树结构在客观世界中是大量存在的。例如家谱、行政组织机构都可用树形象地表示。
树结构在计算机领域中也有着广泛的应用，
例如在编译程序中，用树结构来表示源程序的语法结构；在数据库系统中，可用树结构来组织信息；在分析算法的行为时，可用树结构来描述其执行过程等等。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 3页
6.1 二叉树二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 4页
6.1.1 二叉树的定义
二叉树（ Binary Tree） 是由 n(n≥0) 个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。
这是一个 递归 定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 5页基本术语
结点 (node)——表示树中的元素，
包括数据项及若干指向其子树的分支
结点的度 (degree)——结点拥有的子树数
叶子 (leaf)——度为 0的结点
孩子 (child)——结点子树的根称为该结点的孩子
双亲 (parents)——孩子结点的上层结点叫该结点的 ~
1
2 3
11
4 5
8 9 12
6 7
10
兄弟 (sibling)——同一双亲的孩子
树的度 ——一棵树中最大的结点度数
结点的层次 (level)——从根结点算起，根为第一层，它的孩子为第二层 ……
深度 (depth)——树中结点的最大层次数
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 6页二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二差树的 5种基本形态，图 (C) 和图（ d）是不同的两棵二叉树。
(a)
空二叉树
A A
B
A
B
A
CB
(b)
根和空的左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树二叉树的 5种形式示意二叉树的 5种形式
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 7页
1、满二叉树 (Full Binary Tree)
一棵深度为 k且由 2k-1个结点组成的二叉树称为满二叉树。下图就是一棵满二叉树，对结点进行了顺序编号。
满二叉树示例
2
4 5
3
6 7
1
特殊形态的二叉树：满二叉树、完全二叉树
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 8页
2、完全二叉树 (Complete Binary Tree)
如果一棵二叉树各层都是,满的,,只是最下一层从右边起连续缺少几个结点，称此二叉树为 完全二叉树 。
可见，满二叉树是完全二叉树的特例。
1
2 3
5 6
完全二叉树示例
4
1
2 3
4 5 7
1
2 3
6 7
非完全二叉树示例满二叉树：
完全二叉树：
1
2
4 5
8 9 10 11
3
6 7
12 13 14 15
1
2
4 5
8 9 10 11
3
6 7
12
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 10页二叉树的操作
1、建立一棵空二叉树,InitialBTree(BT)
初始条件：无；
操作结果：构造一棵空树 BT。
2、按某种规则建立一棵二叉树,CreateBTree(BT)
初始条件：无；
操作结果：按某种规则构造一棵二叉树 BT。
3、求二叉树 BT的树根结点,RootBTree(BT)
初始条件：二叉树 BT已存在；
操作结果：返回二叉树 BT的根结点。
4、求二叉树 BT中结点 p的双亲,ParentBTree(BT,p)
初始条件：二叉树 BT已经存在，且 p是二叉树 BT中的一个结点；
操作结果：若结点 p不是二叉树 BT的根结点，则返回结点 p的双亲结点；
否则，返回 NULL。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 11页
5、求二叉树 BT中结点 p的左孩子结点,LeftChildBTree(BT,p)
初始条件：二叉树 BT已经存在，且 p是二叉树 BT中的一个结点；
操作结果：若结点 p不是二叉树 BT的叶子结点，则返回结点 p的左孩子结点；否则，返回 NULL。
6、求二叉树 BT中结点 p的右孩子结点,RightChildBTree(BT,p)
初始条件：二叉树 BT已经存在，且结点 p是二叉树 BT中的一个结点；
操作结果：若结点 p不是二叉树 BT的叶子结点，则返回结点 p的右孩子结点；否则，返回 NULL。
7、判断二叉树 BT是否为空,EmptyBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：若二叉树 BT为空，则返回 True；否则，返回 False。
8、求二叉树 BT的深度,DepthBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：返回二叉树 BT的深度。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 12页
9、将结点 p作为二叉树 BT中结点 q的左子树插入：
InsertLeftBTree(BT,p,q)
初始条件：二叉树 BT已经存在，且结点 q是二叉树 BT中的结点；
操作结果：将结点 p作为二叉树 BT中结点 q的左子树插入 。
10、将结点 p作为二叉树 BT中结点 q的右子树插入：
InsertRightBTree(BT,p,q)
初始条件：二叉树 BT已经存在，且结点 q是二叉树 BT中的结点；
操作结果：将结点 p作为二叉树 BT中结点 q的右子树插入。
11、在二叉树 BT中删除结点 p的左子树,DeleteLChBTree(BT,p)
初始条件：二叉树 BT已经存在，结点 p是二叉树 BT中的结点；
操作结果：在二叉树 BT中删除结点 p的左子树。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 13页
12、在二叉树 BT中删除结点 p的右子树,DeleteRChBTree(BT,p)
初始条件：二叉树 BT已经存在，结点 p是二叉树 BT中的结点；
操作结果：在二叉树 BT中删除结点 p的右子树。
13、给二叉树 BT中结点 p赋值,AssignNodeBTree(BT,p,x)
初始条件：二叉树 BT已经存在，且结点 p是二叉树 BT中的结点；
操作结果：将 x赋值给二叉树 BT中的结点 p。
14、求二叉树 BT中结点 p的左子树,GetLChBTree(BT,p)
初始条件：二叉树 BT已经存在，结点 p是二叉树 BT中的结点；
操作结果：若 p是非叶子结点，则返回结点 p的左子树，否则返回 NULL。
15、求二叉树 BT中结点 p的右子树,GetRChBTree(BT,p)
初始条件：二叉树 BT已经存在，结点 p是二叉树 BT中的结点；
操作结果：若 p是非叶子结点，则返回结点 p的右子树，否则返回 NULL。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 14页
16、按前序遍历方式遍历二叉树 BT,PreOrderTraverseBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：按前序遍历方式遍历二叉树 BT，返回前序遍历序列。
17、按中序遍历方式遍历二叉树 BT,InOrderTraverseBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：按中序遍历方式遍历二叉树 BT，返回中序遍历序列。
18、按后序遍历方式遍历二叉树 BT,PostOrderTraverseBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：按后序遍历方式遍历二叉树 BT，返回后序遍历序列。
19、按层次遍历方式遍历二叉树 BT：
LevelOrderTraverseBTree(BT)
初始条件：二叉树 BT已经存在；
操作结果：按层次遍历方式遍历二叉树 BT，返回层次遍历序列。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 15页
6.1.2 二叉树的性质性质 1,在二叉树的第 i层上至多有 2i-1个结点 (i>=1)。
证明：
采用归纳法证明此性质。
当 i=1时，只有一个根结点,2i-1=20 =1,命题成立。
现在假定对所有的 j,1≤j<i,命题成立，即第 j层上至多有 2j-1个结点，那么可以证明 j＝ i时命题也成立。由归纳假设可知，第 i－ 1层上至多有 2i-2个结点。
由于二叉树每个结点的度最大为 2，故在第 i层上最大结点数为第 i-
1层上最大结点数的二倍，
即 2× 2i-2＝ 2i-1。
命题得到证明。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 16页性质 2：深度为 k的二叉树至多有 2k－ 1个结点（ k≥1) 。
证明：
深度为 k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质 1得到每层上的最大结点数。
122
1
1
k
k
i
i
1
2
4 5
8 9 10 11
3
6 7
12 13 14 15
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 17页性质 3,对任何一棵二叉树，如果其终端结点数为 n0，度为 2的结点数为 n2，则 n0＝ n2＋ 1。
证明：
设二叉树中度为 1的结点数为 n1，二叉树中总结点数为 n，
则有,n＝ n0＋ n1＋ n2 (6-1)
再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设 B为二叉树中的分支总数，则有,n＝ B＋ 1
由于这些分支都是由度为 1和 2的结点产生的，则有：
B＝ n1+2*n2
n＝ B＋ 1＝ n1＋ 2× n2＋ 1 （ 6－ 2)
由式（ 6－ 1）和（ 6－ 2）得到：
n0+n1+n2=n1+2*n2+1
n0＝ n2＋ 1
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 18页性质 4,具有 n个结点的完全二叉树的深度为：
log2n? + 1。
证明：假设完全二叉树的深度为 k。
由性质 2和完全二叉树的定义可知：
或者对上式取对数则有：
由于 k是整数，则,k =?log2n? + 1
1212 1 kk n kk n 22 1
knk 2l o g1
1
2
4 5
8 9 10 11
3
6 7
12
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 19页性质 5,具有 n个结点的完全二叉树，如果从根结点开始，
从上到下为每一个结点从左到右进行编号，那么就有：
⑴ 若 i=1，则结点为二叉树的根，无双亲结点。否则，若
i>1，则 i结点父结点的编号为?i/2?；
⑵ 若 2i≤n,则结点的左孩子结点的编号为 2i；否则结点 i
无左孩子（叶子结点）
⑶ 若 2i+1≤n,则结点的左孩子结点的编号为 2i+1；否则无有孩子证明：可以采用数学归纳法。
正是由于完全二叉树具有如此特点，所以完全或满二叉树可以采用一个一维数组来存储。
1
2
4 5
8 9 10 11
3
6 7
12
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 20页
6.1.3 二叉树的存储结构
1.顺序存储方法：
它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法。
#define maxsize 100
typedef telemtype sqbitree[maxsize];
Sqbitree bt；
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 21页从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为 H
且只有 H个结点的右单支树确需要 2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好的！
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 22页
a b c d e f g h i j k l
1 2 3 4 5 6 7 8 9 10 11 12
完全二叉树的顺序存储过程示例
a
b c
d e f g
h i j k l
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 23页
A
B C
D E
F G
表示该处没有元素存在仅仅为了好理解
A B C D E F G
一般二叉树的顺序存储过程示例
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 24页
2.二叉链表法存储二叉树经常用二叉链表表示法。
lchild data rchild
A
B
C D
E
G
F
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 25页二叉树的二叉链表的数据结构：
Typedef struct BiTNode {
TElemType data;
struct BiTNode *LChild,*RChild;
}BiTnode,*BiTree;
有时也可用数组的下标来模拟指针,即开辟三个一维数组 Data,lchild,rchild 分别存储结点的元素及其左、右指针域 ;
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 26页
3.三叉链表法有时，为了便于找到结点的双亲结点，人们经常采用三叉链表来表示给定的二叉树。
Parent RchildDataLchild 三叉链表结点结构图三叉链表存储结构图
A
B^ ^C
D E^
^F^ ^G^ ^H^
^
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 27页二叉树的三叉链表的数据结构：
Typedef struct BTTNode {
TElemType data;
struct BTTNode *Parent,*LChild,*RChild;
}*BTTree;
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 28页
6.2 二叉树遍历在二叉树的一些应用中，常常要求在二叉树中查找具有某种特征的结点，或者对二叉树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访二叉树中的每一个结点，使得 每一个结点均被访问一次，
而且仅被访问一次 。
遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 29页假如以 L,D,R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有 DLR,LDR,LRD,DRL,RDL、
RLD六种遍历方案。若我们规定以根为中心，先左子树后右子树的原则，则只有前三种情况，分别规定为：
DLR——先（根）序遍历；
LDR——中（根）序遍历；
LRD——后（根）序遍历。
L R
D (根结点 )
(右子树 )
(左子树 )
由二叉树的递归定义，
二叉树的三个基本组成单元是：根结点、左子树和右子树。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 30页
1、先序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）访问根结点；
（ 2）先序遍历左子树；
（ 3）先序遍历右子树。
2、中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）中序遍历左子树；
（ 2）访问根结点；
（ 3）中序遍历右子树。
3、后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）后序遍历左子树；
（ 2）后序遍历右子树；
（ 3）访问根结点。
当然二叉树具有层次的概念，所以，二叉树还有一种按方式，就是按层次遍历二叉树，即从二叉树的根开始，按从上到下、从左到右的顺序遍历二叉树。
L R
D (根结点 )
(右子树 )
(左子树 )
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 31页遍历二叉树的三种方法：
先序遍历二叉树
（ 1）访问根结点
（ 2）先序遍历左子树
（ 3）先序遍历右子树
^
A ^
B
^ C ^ D
^ E ^ F
^ G ^
A B C D E G F
中序遍历二叉树
（ 1）中序遍历左子树
（ 2）访问根结点
（ 3）中序遍历右子树
^
A ^
B
^ C ^ D
^ E ^ F
^ G ^
C B E G D F A
后序遍历二叉树
（ 1）后序遍历左子树
（ 2）后序遍历右子树
（ 3）访问根结点
^
A ^
B
^ C ^ D
^ E ^ F
^ G ^
C G E F D B A
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 34页遍历算法先序遍历,D L R
中序遍历,L D R
后序遍历,L R D
A
D
B C
T1
T2
T3
D L R
A
D L R
D L R
B
D
C
D L R
以先序遍历 D L R
为例演示遍历过程
ABDC
BDAC
DBCA
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 35页
-
*
A B
C
－
* C
A B
-
*
A B
C
先 序遍历 - * A B C
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 36页
-
*
A B
C
－
* C
A B
-
*
A B
C
中序遍历 A * B - C
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 37页
-
*
A B
C
－
* C
A B
-
*
A B
C
后序遍历 A B * C -
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 38页
6.2.2 遍历算法描述
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 39页算法 6.1
void Preorder(BiTree T,void(*visit)( BiTree )){
// 先序遍历以 T为根指针的二叉树
if (T) { // T=NULL时，二叉树为空树，不做任何操作
visit(T);
// 通过函数指针 *visit访问根结点，以便灵活完成相应的操作
Preorder(T->lchild,visit); // 先序遍历左子树
Preorder(T->rchild,visit); // 先序遍历右子树
}
}
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 40页
void Preorder (BiTree T,void(*visit)( BiTree )){
if (T) {
visit(T);
Preorder(T->lchild,visit);
Preorder(T->rchild,visit); }
}
主程序
Pre( T )
返回返回
pre(T R);
返回返回
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
返回
T
左是空返回
pre(T R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T R);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 41页
typedef enum{Travel=1,Visit=0} TaskType;
typedef struct{
BiTree ptr; //指向结点的指针
TaskType task; //当前的任务
}SElemType;
算法 6.2（采用非递归方式中序遍历）
void InOrder_iter( BiTree BT,void(*visit)( BiTree ) ) {
//利用栈实现中序遍历二叉树,BT为指向二叉树的根结点的头指针
InitStack(S);
e.ptr=BT; e.task=Travel; // e为栈元素
if(BT) Push(S,e); // 布置初始任务
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 42页算法 6.2
while(!StackEmpty(S)) { // 每次处理一项任务
Pop(S,e);
if(e.task==Visit) visit(e.ptr); // 处理访问任务
else
if(e.ptr){ // 处理非空树的遍历任务
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
// 最不迫切任务 (遍历右子树 )进栈
e.ptr=p; e.task=Visit; Push(S,e);
//处理访问任务的工作状态进栈
e.ptr=p->lchild; e.task=Travel; Push(S,e);
// 迫切任务 (遍历左子树 )进栈
}//if
}//while
}//InOrder_iter
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 43页
A T
A Te
A
B
D
C
E ^
^
^
^
^ ^
P
A VC TB T
e.ptr=BT; e.task=Travel;
if(BT) Push(S,e); // 布置初始任务
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 44页
A
B
D
C
E ^
^
^
^
^ ^
B Te
A VC TB T A VC T
P
D TA V
C T
B V^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 45页
A
B
D
C
E ^
^
^
^
^ ^
^ Te
P
P
D TA V
C T
B V^ T D T
A VC T
B V
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 46页
A
B
D
C
E ^
^
^
^
^ ^
e
P
P
D TA V
C T
B V D T
A VC T
B V
输出 B
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 47页
A
B
D
C
E ^
^
^
^
^ ^
e
P
D TA V
C T
D T
A VC T
输出 B
A VC T^ T
D VE T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 48页
A
B
D
C
E ^
^
^
^
^ ^
e
P
E T
输出 B
A VC T^ T
D VE T
A VC T^ T
D V
A VC T^ T
D V^ T
E V^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 49页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
输出 B
A VC T^ T
D V^ T
E V^ T
A VC T^ T
D V^ T
E V
e
A VC T^ T
D V^ T
E V
输出 E
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 50页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
A VC T^ T
D V^ T
A VC T^ T
D V
e
A VC T^ T
D V
输出 D
输出 BE
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 51页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
A VC T^ T
e
C TA VC T
A V
输出 A
输出 BED
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 52页
A
B
D
C
E ^
^
^
^
^ ^
e
P
C T
C T
输出 BEDA
^ TC V
^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 53页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
输出 BEDA
^ TC V
^ T
^ TC V
C Ve
^ T
输出 C
if(e.task==Visit) visit(e.ptr);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 54页
A
B
D
C
E ^
^
^
^
^ ^
e
P
^ T
输出 BEDAC
^ T OVER
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 55页建立二叉链表树以字符串的形式 (根 左子树 右子树 )定义一棵二叉树例如,
A
B
C
D
以字符,#” 表示
A(B(#,C(#,#)),D(#,#))
空树只含一个根结点的二叉树 A 以字符串,A##” 表示以下列字符串表示
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 56页算法 6.3
void CreatebiTree(BiTree &T){
// 在先序遍历二叉树过程中输入结点字符，建立二叉链表存储结
//构，指针 T指向所建二叉树的根结点
cin >> ch ；
if (ch=='#') T=NULL; // 建空树
else {
T = new BiTNode ; // "访问 "操作为生成根结点
T->data = ch;
CreateBiTree(T->lchild); // 递归建 (遍历 )左子树
CreateBiTree(T->rchild); // 递归建 (遍历 )右子树
}//else
}//CreateBiTree
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 57页
AT
ch=A
T
T
A
creat(T L)
Λ
T= Λ,Creat(T) 返回
creat(T R) T
ch=#
DΛ
||
=
返回
creat(T R)
D
=T
ch=#
ΛΛ
返回
ch=D
T
T
D
creat(T L)
=||
Φ
Φ
creat(T R)
ch=C
T
T
C
creat(T L)
– +
ch=B
T
T
B
creat(T L)
T
ch=#
BΛ
T
CΛ
ch=#
–
+
返回
creat(T R) T
CΛ
ch=#
Λ
+
返回
A
BΛ
A
BΛ
D|| =
A
DΛ Λ
A
BΛ
DΛ Λ
C– +Λ Λ
输入,A B # D # # C # #
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 58页算法 6.4 求二叉树树深（先序）
void BiTreeDepth(BiTree T,int h,int &depth){
// h为 T指向的结点所在层次,T指向二叉树的根，则 h的初
//值为 1,depth为当前求得的最大层次,其初值为 0
if (T){
if (h>depth) depth=h;
BiTreeDepth(T->lchild,h+1,depth);
BiTreeDepth(T->rchild,h+1,depth);
}
}//BiTreeDepth
主函数调用：
d=0
BiTreeDepth(r,1,d)
A
B
D
C
E ^
^
^
^
^ ^
T
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 59页算法 6.5 求二叉树树深（后序）
int BiTreeDepth(BiTree T) {
// 后序遍历求 T所指二叉树的深度
if (!T) return 0;
else {
hL=BiTreeDepth(T->lchild);
hR=BiTreeDepth(T->rchild);
if (hL>=hR) return hL+1;
else return hR+1;
}
}//BiTreeDepth
A
B
D
C
E ^
^
^
^
^ ^
T
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 60页算法 6.6 复制一棵二叉树
BiTNode *CopyTree(BiTNode *T){
// 已知二叉树的根指针为 T，本算法返回它的复制品的根指针
if (!T ) return NULL; // 复制一棵空树
if (T->lchild )
newlptr = CopyTree(T->lchild); // 复制 (遍历 )左子树
else newlptr = NULL;
if (T->rchild )
newrptr = CopyTree(T->rchild); // 复制 (遍历 )右子树
else newrptr = NULL;
newnode = GetTreeNode(T->data,newlptr,newrptr); //生成根结点
return newnode;
}
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 61页生成一个二叉树的结点
BiTNode *GetTreeNode(TElemType item,BiTNode *lptr,
BiTNode *rptr ){
//生成一个二叉树的结点,其数据域为 item,
//左指针域为 lptr,右指针域为 rptr)
T = new BiTNode;
T-> data = item;
T-> lchild = lptr; T-> rchild = rptr;
return T;
}
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 62页
A
B
C
D
E
F
G
H K
A
例如，下列二叉树的复制过程如下：
newT
^ B E ^
C ^
^ D ^
F ^
G
^ H ^ ^ K ^
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 63页
a+b
(a+b)× c – d/ea+b× c
表达式的二叉树的表示,
a b
+
a
b c
×
+
a b
c
×
+
(a+b)× c
a b
c d e
-
×
+
/
特点,
操作数 为叶子结点运算符 为分支结点
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 64页例右图所示的二叉树表达式
(a+b*(c-d))-e/f
若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：
-+a*b-cd/ef （前缀表达式）
按中序遍历,其中序序列为：
a+b*c-d-e/f （中缀表达式）
按后序遍历,其后序序列为：
abcd-*+ef/- （后缀表达式）
－
＋
*a
/
b -
dc
fe
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 65页计算表达式的值 (a+b*(c-d))-e/f
－
＋
*a
/
b -
dc
fe
-2
-1
-30
-4
1 -2
32
54
3.1 4.2 2.4 3.8 7.2 2.4abcd-*+ef/- （后缀表达式） opnd
0 1 2 3 4 5
数据结构的表示
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 66页算法 6.7
double value(BiTree T,float opnd[]){
// 对以 T为根指针的二叉树表示的算术表达式求值，
// 操作数的数值存放在一维数组 opnd中
if (!T) return 0; // 空树的值为 0
if (T->data>=0) return opnd[T->data];
Lv = value(T->lchild,opnd); // 遍历左子树求第一操作数
Rv = value(T->rchild,opnd); // 遍历右子树求第二操作数
switch (T->data){
case PLUS,v = Lv + Rv;
case MINUS,v = Lv - Rv;
case ASTERISK,v = LV * Rv;
case SLANT,v = Lv / Rv;
default,ERROR("不合法的运算符 ");
}//switch
return v;
}//value
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 67页由二叉树的先序和中序序列建树仅知二叉树的先序序列,abcdefg” 不能唯一确定一棵二叉树，
如果同时已知二叉树的中序序列,cbdaegf”,则会如何？
二叉树的先序序列二叉树的中序序列左子树左子树 右子树右子树根根
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 68页
a b c d e f g
c b d a e g f
例如,b f
a
b
c d
e
f
g
^ ^ ^ ^
^
^ ^
^
先序序列中序序列
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 69页性质 7,通过一棵二叉树的前序遍历序列和中序遍历序列，能够构造出唯一的一棵二叉树 BT。
性质 6,对于给定一棵二叉树 BT，它的前序遍历序列、中序遍历序列及后序遍历序列是唯一的。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 70页例如：已知二叉树 BT的后序遍历序列为,CBEHGIFDA，中序遍历序列为,BCAEDGHFI，请构造这棵二叉树 T。
A
BC DEF
GHI
A
DEF
GHI
B
C FGHI
A
B
C
D
E
GH
A
B
C
D
E F
I
A
B
C
D
E F
H
G I
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 71页
6.2.4 线索二叉树
遍历二叉树的结果是，求得结点的一个线性序列。
例如,
先序序列,
A B C D E F G H K
中序序列,
B D C A H G K F E
后序序列,
D C B H K G F E A
A
B
C
D
E
F
G
H K
当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能找到结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 72页指向该线性序列中的,前驱,和
,后继,的指针，称作,线索,
与其相应的二叉树，称作
,线索二叉树,
包含,线索,的存储结构，
称作,线索链表,
A B C D E F G H K
^ D ^
C ^
^ B E ^
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 73页线索二叉树的定义
Typedef struct BiThrNode{
TelemType data;
struct BiThrNode *lchild,*rchild; //左,右孩子指针
struct BiThrNode *pred,*succ; //前驱与后继线索
}BiThrNode,*BiThrTree;
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 74页
-
*
A B
C -
* Λ C Λ
Λ A Λ Λ B Λ
中序线索链表中序遍历 A * B - C
head表示指向孩子表示线索 Λ
左 数据 右前 后
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 75页算法 6.8
void InOrder(BiThrTree H,void(*visit)( BiTree ) ){
// H 为指向中序线索链表中头结点的指针，
// 本算法中序遍历以 H->lchild所指结点为根的二叉树
p = H->succ;
while( p!=H ) {
visit(p);
p = p-> succ;
}
}//InOrder
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 76页算法 6.9
void InOrderThreading(BiThrTree &H,BiThrTree T){
// 建立根指针 T所指二叉树的中序全线索链表,H指向该线索链表的头结点
H = new BiThrNode; // 创建线索链表的头结点
H->lchild = T; H->rchild = NULL;
if (!T) {
H->pred = H;
H->succ = H;}// 空树头结点的线索指向头结点本身
else {
pre = H;
// 对二叉树进行中序遍历，在遍历过程中进行线索化
InThreading(T,pre);
pre->succ = H; H->pred = pre;
}
}//InOrderThreading
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 77页算法 6.10
void InThreading(BiThrTree p,BiThrTree &pre){
// 对以根指针 p所指二叉树进行中序遍历，在遍历过程中进行线索化
// p为当前指针,pre是跟随指针，比 p慢一拍遍历全二叉树
if (p) {
InThreading(p->lchild,pre); // 左子树线索化
pre->succ = p; p->pred = pre; // 建立线索
pre = p; // 保持 pre指向 p的前驱
InThreading(p->rchild,pre); // 右子树线索化
}
}//InThreading
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 78页二叉树性质：
n个结点的二叉树存在 n+1个空链域。
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 79页暂停，继续
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 80页为了避免混淆，必须增加两个标志位：
ltag data rchildrtaglchild
0 lchild域指向结点的左孩子
ltag=
1 lchild域指向结点的前驱
0 rchild域指向结点的右孩子
rtag=
1 rchild域指向结点的后继概念：线索链表，线索，线索二叉树，线索化
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 81页
-
*
A B
C 0 - 0
0 * 0 1 C 1
1 A 1 1 B 1
中序线索链表中序遍历 A * B - C
0 1
head
最后结点右指针指向头结点头结点左指针指向首结点 头结点右指针指向最后结点表示指向孩子表示线索
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 82页
typedef struct BiThrNod {
TElemType data;
struct BiThrNode *lchild,*rchild; // 左右指针
PointerThr LTag,RTag; // 左右标志
} BiThrNode,*BiThrTree;
线索链表 的类型描述：
typedef enum { Link,Thread } PointerThr;
// Link==0:指针,Thread==1:线索
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 83页线索链表的遍历算法,
由于在线索链表中添加了遍历中得到的“前驱”和
“后继”的信息，从而简化了遍历的算法。
for ( p = firstNode(T); p; p = Succ(p) )
Visit (p);
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 84页
Status InOrderTraverse_Thr(BiThrTree T,(*Visit)(TElemType e))
{
// T指向头结点，头结点的左链 lchild指向根结点，头结点的右链
//lchild指向中序遍历的最后一个结点。中序遍历二叉线索链表表示
//的二叉树，对每个数据元素调用函数 Visit。
p = T->lchild; // p指向根结点
while (p != T) { // 空树或遍历结束时,p==T
while (p->LTag==Link) p = p->lchild;
Visit(p->data) // 访问其左子树为空的结点
while (p->RTag==Thread && p->rchild!=T) {
p = p->rchild; Visit(p->data); // 访问后继结点
}
p = p->rchild; // p进至其右子树根
}
return OK;
} // InOrderTraverse_Thr
-
*
A B
C
T
0 1
LTag RTag
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 85页在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针 pre,并始终保持指针 pre指向当前访问的、指针 p所指结点的前驱。
如何建立线索链表
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 86页
Status InOrderThreading(BiThrTree &Thrt,BiThrTree T) {
// 中序遍历二叉树 T，并将其中序线索化,Thrt指向头结点。
if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
exit (OVERFLOW);
Thrt->LTag = Link; Thrt->RTag =Thread; // 建头结点
Thrt->rchild = Thrt; // 右指针回指
if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指
else {
Thrt->lchild = T; pre = Thrt;
InThreading(T); // 中序遍历进行中序线索化
pre->rchild = Thrt; pre->RTag = Thread;
// 最后一个结点线索化
Thrt->rchild = pre;
}
return OK;
} // InOrderThreading
Da
ta
Str
uc
tur
e
数据结构——
第
6
章树和二叉树胡建华 2009-7-24计算机教研室第 87页
void InThreading(BiThrTree p) {
if (p) {
InThreading(p->lchild); // 左子树线索化
if (!p->lchild) {
p->LTag = Thread;
p->lchild = pre;
} // 建前驱线索
if (!pre->rchild) {
pre->RTag = Thread;
pre->rchild = p;
} // 建后继线索
pre = p; // 保持 pre指向 p的前驱
InThreading(p->rchild); // 右子树线索化
}
} // InThreading
1 1
p
0 1
pre
