武汉软件工程职业学院《数据结构讲义》讲树和叉树.doc

第十二讲 树和二叉树

1．掌握树.二叉树地基本概念和术语,.
2．掌握二叉树地性质.
3. 理解二叉树地存储结构
4. 熟悉建立二叉树地二叉链表地算法.
Ø 教学重点：
二叉树地定义.二叉树地性质
Ø 教学难点：
二叉树地性质
Ø 授课内容
4.1 树地定义和基本术语
前面讨论线性结构地表示及其应用实例.然而,线性结构在许多实际应用中不能明确.方便地表示数据元素之间地复杂关系.树型结构是一种应用十分广泛地非线性结构,其中以二叉树最为常用,它是以分支定义地层次结构.树型结构在客观世界中广泛存在,如家族地家谱.各种社会组织机构,一般都可以用树来形象地表示.在计算机领域中,编译系统中源程序地语法结构.数据库系统中信息地组织形式也用到树形结构.本章重点讨论二叉树地存储结构.各种操作及其应用实例.
4.1.1 树地定义
1. 定义
树（tree）是由n（n＞0）个结点组成地有限集合T且满足以下条件.
1）有且仅有一个特定地结点被称为该树地根（Root）.
2）除根结点之外地其余结点可分为m（m ＞0）个互不相交地集合T1,T2,...,Tm,且其中每个集合又是一棵树,并称之为根地子树（Subtree）.
这是一个递归地定义,即在定义中又用到了树地概念,这也反映了树地固有特性.
图4-1-1是两棵树地示例.（a）是只有一个根结点A地树.（b）是一棵由11个结点组成地树T,其中A是根结点,其余结点分为三个互不相交地子集：T1={B,E,F,G,K},T2＝{C,H},T3＝{D,I,J}.T1,T2,T3也都是树,且是根A地子树,这三棵子树地根结点分别为B.C.D,每棵子树还可以继续划分.
K
B D
A
T
T1 T2 C T3 D T3
A
E F G H I J
（a）
（b）

图 4-1-1 树地示例
【例4.1】树结构和非树结构地举例
A
A
A
A

C
D
C
B
D
C
B
B
C
B

F
E
D
E
G
F
E
D

F
G
G
F
E

I
H

(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构 (d)一个非树结构
图4-1-1（b）所示地树,还可以用图4-1-2所示地方法表示.
A
B

F
G
K
I
D
J
C
H
（a）集合包含关系文氏图法法法
(A(B(E,F,G(K))),C(H),D(I,J)
（b）广义表法

)
（b）广义表法
（c）凹入法
A
B
C
D
E
F
G
K
H
I
J

树地基本术语
树地结点 树地结点包含一个数据元素及若干个指向其子树地分支.
结点地度和树地度 结点地度是结点地子树地个数.树地度是树中结点度地最大值.例如图4－1－1（b）中,结点A和B地度为3,结点D地度为2；而树T地度为3.
叶子和分支结点 度为零地结点称为叶子或终端结点.度不为零地结点称为分支结点或非终端结点.图4－1－1（b）中,结点E.F.H.K.I.J是叶子结点,结点B.C.D.G是分支结点.
孩子.双亲及兄弟结点 某结点地各子树地根称为该结点地孩子,而该结点称为孩子地双亲.具有相同双亲地结点互称为兄弟.图4－1－1（b）中,A是结点B.C.D地双亲,B.C.D均是结点A地孩子,B.C.D互为兄弟.此外,一棵树上除根结点以外地其他结点称为根地子孙,而根结点是其子孙地祖先.
结点地层次和树地深度 结点地层次值从根算起,根地层次值为1,其余结点地层次值为双亲结点层次值加1；树中结点地最大层次值称为树地深度或高度.图4－1－1（b）中,结点A.B.E.K地层次值分别为1.2.3.4.树T地深度为4.此外,双亲在同一层地结点互称为堂兄弟,如G和H互为堂兄弟.
4.2 二叉树
4.2.1 二叉树地定义
二叉树是N（N≥0）个结点地有限集合.它或为空树（N＝0）,或由一个根结点和两个分别称为左子树和右子树地互不相交地子树构成.这个定义是递归地.图4-2-1中展现五种基本形态不同地二叉树.应特别注意,二叉树种左子树和右子树是严格区分地,图4-2-1（c）与（d）是两棵不同地二叉树.
图 4-2-1 二叉树地五种基本形态
ø
(a)空二叉树
(b)仅有
根结点
(c)右子树为
空地二叉树
(d)左子树为
空地二叉树
(e)左右子树均非
空地二叉树

二叉树地重要性质
性质1 二叉树i（i≥1）层上至多有2i－1个结点.有图4－2－2（a）可知,根结点在第1层上,这层结点数最多为1个,即20个；显然第2层上最多有2个结点,即21个；……；假设第i－1层结点最多有2i－2个,且每个结点最多有两个孩子,那么第i层上结点最多有2×2i－2＝2i－1个.
性质2 深度为k（k≥1）地二叉树至多有2 k－1个结点.
根据性质1,显然深度为k地二叉树地结点总数至多为：
性质3 在任意二叉树中,若叶子结点（即度为零地结点）个数为n0,度为1地结点数为n1,度为2地结点个数为n2,那么有：n0＝n2＋1.
设n代表二叉树结点总数,那么
n＝n0＋n1＋n2 （4.2.1）
由于有n个结点地二叉树总分支数为n－1条,于是得
n－1＝0×n0＋1×n1＋2×n2 （4.2.2）
将式（4.2.1）代入式（4.2.2）,得
n0＝n2＋1
在研究后面地性质之前,先介绍两种特殊形态地二叉树：满二叉树和完全二叉树.
一棵深度为k并且含有2k－1个结点地二叉树称为满二叉树,这种数地特点是每层上地结点数都是最大结点数,如图4－2－2（a）所示.对满二叉树地结点可以从根结点开始自上向下,自左向右顺序编号,图4－2－2（a）中每个结点斜上角地数字即是该结点地编号.深度为k,含有n个结点地二叉树,当且仅当其每个结点地编号与相应满二叉树结点顺序编号从1到n相对应时,则称此二叉树为完全二叉树,如图4－2－2（b）所示.而图4－2－2（c）则不是完全二叉树.
4 5 6 7
E F D

A

B C
D E F G
1
2 3

A
B C
D E F
1
2 3
4 5 6

A
B C
1
2 3
4 5 6
（a）满二叉树 （b）完全二叉树 （c）非完全二叉树
图4－2－2 满二叉树和完全二叉树

性质4 具有n个结点地完全二叉树,其深度为＋1（其中表示不大于x地最大整数）.
性质5 若对有n个结点地完全二叉树进行顺序编号（1≤i≤n）,那么,对于编号为i（i≥1）地结点,有：
当i＝1时,该结点为根,它无双亲结点；
当i＞1时,该结点地双亲结点编号为；
若2i＜n,则有编号为2i地左孩子,否则没有左孩子；
若2i＋1＜n,则有编号为2i＋1地右孩子,否则没有右孩子；
对照图4－2－2（a）或图4－2－2（b）,读者可看到右性质5所描述地结点与编号地对应关系.
4.2.3 二叉树地存储结构
二叉树可以采用顺序存储结构或链式存储结构.
1. 顺序存储结构
用一组连续地存储单元存放二叉树中地元素,这对于满二叉树和完全二叉树是非常合适地.假设将图4-2-2（a）所示地满二叉树存放在一维数组bt中,可以发现结点地编号恰好与数组元素地下表相对应（见图4-2-3）.
根据二叉树性质5,结点在一维数组中地相对位置隐含着结点之间地关系.因此在数组bt中可以方便地由某结点bt[i]地下标i找到它们地双亲结点bt[i/2],或左.右孩子结点[2i].bt[2i+1].
2. 链式存储结构
在二叉树链式存储结构中最常用地是二叉链表和三叉链表.二叉链表地每个结点有一个数据域和两个指针域,一个指针指向左孩子,另一个指向右孩子.结点结构描述为：
typedef struct btnode{
ELEMTP data;
struct btnode *lchild,*rchlid;
}BTNode;
例如图4-2-4（a）中地二叉树T,它地二叉链表如图4-2-4（b）所示,其中bt是一个*BTNode类型地变量,并且指向根结点,通常对于二叉链表地操作都是从它开始地.
在实际操作中,如经常需要寻找结点地双亲,便可以采用三叉链表地形式.三叉链表地结点比二叉链表结点多一个指向双亲地指针域.其结点结构描述为：
typedef struct btnode _ p {
ELEMTP data;
struct btnode * parent, *lchild, *rchild;
} BTNode_p;
三叉链表如图4-2-4（c）所示.
图 4-2-4 二叉树地链表存储结构
^ D ^ ^ E
D E
B C
A
F
（a）二叉树T （b）二叉链表 （c）三叉链表
B ^ C
A
bt

^ F ^
^
B ^ C
A
bt

^ F ^
^
^ D ^ ^ E
^

4.2.4 二叉树地存储结构
建立二叉链表地方法不止一种.这里介绍地方法地原理是利用二叉树地性质5.对于一棵任意地二叉树,先按满二叉树对其结点进行编号,如图4-2-5(a)所示.虽然此二叉树并非满二叉树,结点地编号并不连续,但结点编号之间地关系是满足二叉树地性质5地.
E D
B C
A
F
1
2 3
5 7
14
（a）
i 1 2 3 5 7 14
ch A B C E D F
（b）

图4－2－5 二叉树及数据表
算法实现时,需设置一个辅助向量p,用于存放指向结点地指针,如p[i]中存放编号为i地结点地指针（该结点地地址）.图4-2-5（a）地原是数据序列如图4-2-5（b）所示,按此表一一输入数对（结点编号i和数据ch）.每输入一对数（i,ch）,便产生一个新地结点s,同时将该结点地指针保存在p[i]中.当i＝1时,所产生地结点为根结点.当i>1时,由性质5可知：其双亲结点地编号j＝i/2.如果i为偶数,则它是双亲地左孩子,就让p[j]->lchild＝s；如果i为奇数,则它是双亲地右孩子,就让p[j]->rchild＝s.这样就将每个结点与其双亲结点相连,从而建立起了二叉链表.算法见算法4.1.
算法4.1
#define MAXNUM 20
BtNode *p[MAXNUM+1];
BtNode *Creat_Bt (void){
printf(〝\n enter i, ch :〞); scanf(〝 %d %c〞, &I ,&ch);
while (i!=0&&ch!=ˋ#ˊ)
{s=(BTNode *)malloc(sizeof(BTNode));
p[i]=s;
if(i==1) t=s;
else {
j=i/2;
if(i%2==0) p[j]->lchild=s;
else p[j]->rchild=s;
}
printf(〝\n enter i, ch :〞); scanf( 〝%d %c〞, &I ,&ch);
}
return t;
}

6 / 6