当前位置: 首页 > >

数据结构第7章_树和二叉树_图文

发布时间:

第7章 树和二叉树
线性结构主要反映了数据元素之间的线性顺序, 很难说明数据之间的层次关系。树是一种重要的非线 性数据结构,它能很好地描述结构的分支关系和层次 关系,所以在文件管理系统和数据库系统中,树结构 是信息的重要组织形式之一。

7.1 树的基本概念(教材第8章)
7.1.1 树的定义
树(Tree)是n(n≥0)个结点的有限集合。在任意 一棵非空树中:
(1)有且仅有一个特定的称为根(Root)的结点; (2)当n?1时,其余结点可分为m(m?0)个互不相交 的有限集合T1,T2,…,Tm,其中每一个集合本身又是 一棵树,并且称为根的子树(Subtree)。

树形结构示例

A

B

C

D

A
只有一个根结点的树

E F GH I J

KL

M

这是一个有13个结点的树,其中A是根结点,其
余结点分成三个互不相交的结点的子集:
T1={B,E,F,K,L}, T2={C,G}, T3={D,H,I,J,M}。 T1、T2、T3都是A的子树,且它们本身也是一棵树

树的基本术语

结点的度:
一个结点所拥有的子树的 个数。
例:结点A的度为3,结点 E的度为2,结点M的度为0。
树的度:

A

B

C

D

E F GH I J

树中所有结点的度的最大 值。即MAX{结点的度}。

K

L

M

例:右图所示树的度为3。

树的基本术语

叶子结点: 度为0的结点称为叶子
结点或终端结点。 例:右图所示树中的
结点K、L、F、G、M、I、J 为叶子结点。
分支结点:

A

B

C

D

E F GH I J

度不为0的结点称为非 K L

M

终端结点或分支结点。除

根结点外,分支结点也称

为内部结点。

树的基本术语

孩子结点和父结点(双亲结点):

一个结点的子树的根称为该结

A

点的孩子(Child)。相应的,该

结点称为孩子的双亲(Parents) B

C

D

或父结点。

兄弟结点:

E F GH I J

同一个双亲的孩子之间

互称为兄弟(Sibling)。 K L

M

树的基本术语

祖先结点:
从根到一个结点的路径上的所 有结点称为该结点的祖先结点。
子孙结点:
以某结点为根的子树中的所有 结点都是该结点的子孙。

A

B

C

D

E F GH I J

KL

M

树的基本术语

结点的层次:

一棵树从根开始定义,根为第
A
一层,根的孩子为第二层,…,依

此类推。若某结点在第i层,则其

子树的根就在第i+1层。

B

C

D

树的深度
树中所有结点的层次的最大

E F GH I J

值称为树的深度或高度。即MAX{结

点的层次}。

KL

M

例:右图所示树的深度为4 。

树的基本术语

森林(Forest): m(m≥0)棵互不相交的

B

C

D

树的集合称为森林。对树中每 个结点而言,其子树的集合即 E F G H I J

为森林。

KL

M

课堂思考

? 判断右边(a)、(b) 所示图形是否树?

B EF

D

H

J

KL

M

G

C

(a)

(b)

? 下面两个叙述是否正确?

1. 根结点也可以是叶子结点。 √

2. 度为0的结点就是叶子结点。 √

7.2 树的存储结构(教材第8章)
因为树是一种非线性结构,所以不能简单地用一维数组或单链 表来存储树。为了存储树,必须把树中每个结点之间存在的关系反 映在存储结构之中,才能如实的表现一棵树。
树的存储结构有多种表示方法,下面介绍常用的三种。
7.2.1 双亲表示法
这种表示法要求用一维数组来存储树的有关信息,每个结点 对应一个数组元素,它包含两个域:一个是数据域(data),存 放该结点所包含的数据;一个是指针域(parent),指出该结点 的双亲结点的位置(整数)。

R

A

B

DE

G

C F HK

数据域 指针域

0R

-1

1A

0

2B

0

3C

0

4D

1

5E

1

6F

3

7G

6

8H

6

9K

6

在树的双亲表示法 中,求某个结点的双 亲结点是非常容易的, 但求某个结点的孩子 结点比较困难,需要 遍历整个结构。

7.2.2 孩子表示法
方法之一:把每个结点的孩子结点排列起来,构成一个单链表, 则n个结点有n个孩子链表(叶子结点的孩子链表为空)。而n个头 指针又组成一个线性表,采用顺序存储结构存储。每个结点只要掌 握了这个单链表的表头,就容易找到它的全部孩子。

0R
R
1A

A

B

C

2B ^ 3C

4D

DE

5E ^
F
6F

7G ^

G H K 8H ^

9K ^

1 4
6^

2 5^

3^

7

8

9^

7.2.2 孩子表示法
在树的孩子表示法中,寻找任意结点的孩子是比较容易的, 但寻找它的双亲却比较困难。我们可以将双亲表示法和孩子表示 法合在一起。

R

0 -1 R

10 A

A

B

C

20 B ^ 30 C

41 D ^

DE

F

51 E ^

63 F

76 G ^

G H K86 H ^

96 K ^

1 4
6^

2 5^

3^

7

8

9^

7.2.3 孩子兄弟表示法
又称为二叉链表表示法 (或二叉树表示法)。即以二 叉链表作为树的存储结构, 链表中每个结点设有两个链 域,一个指向该结点的第一 个孩子,一个指向该结点的 下一个兄弟结点。结点类型 定义如下:
struct node { anytype data;
struct node *firstchild,*nextsibling; };

7.3 二叉树
二叉树(Binary tree)是树形结构中一种最典型、最常用的 结构,处理起来也比一般树简单,因此,在实际应用中,通常将 一般树形结构转化为二叉树进行处理。
7.3.1 二叉树的定义和性质
1.二叉树的定义
二叉树的特点是每个结点至多只有两棵子树(即二叉树中不 存在度大于2的结点),并且,二叉树的子树有左右之分,其次序 不能任意颠倒。二叉树有五种基本形态:

2.二叉树的基本性质

? 性质1 在二叉树的第i层上至多有2i-1个结点(i≥1)。

A

B

C

D

EF

K

第一层 21-1 第二层 22-1 第三层 23-1

2.二叉树的基本性质
? 性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。

A

B

C

D

EF

K

深度1 21-1 深度2 22-1 深度3 23-1

2.二叉树的基本性质

? 性质3 对任何一棵二叉树T,设n0、n2分别是叶子结点个数 和度为2的结点个数,则:n0=n2+1。

A

B

C

D

EF

n0:3 n2:2

证明: 在二叉树中有 n0=n2+1。
从结点的度来看,二叉树中只有三种结点:度为0、1、2的结点。 假设二叉树中,度为0的结点有n0个, 度为1的结点有n1个,度为2的 结点有n2个,则结点总数: n=n0+n1+n2 --------------- (1) 二叉树中除根结点外,其余结点都由分支引入,则
n=1+分支总数 --------------- (2) 分支总数与结点的度有关:度为0的结点不发出分支;一个度为1的结 点发出1条分支,则度为1的结点共发出分支n1*1条。一个度为2的结点发 出2条分支,则度为2的结点共发出分支n2*2条。
分支总数=n1*1+n2 *2 --------------- (3)
由(2)、(3)得: n= 1+ n1*1+n2 *2 ---------- (4) 由(1)、(4)得: n0+n1+n2 = 1+ n1*1+n2 *2
即: n0= n2+1

课堂练*
设树T的度为4,其中度为1、2、3、4 的结点个数分别为4、2、1、1。问T中有 多少个叶子结点?
答案 ∵ 树的分支数为15,结点数=分支数+1=16 ∴ 叶子结点的个数=16-8=8个

满二叉树与完全二叉树
? 一棵深度为k且有2k-1个结点的二叉树称为满二叉树。
A

B

C

D

EF

K

m(深度):3 ,结点数: 2m-1=7

满二叉树的特点:每一层上的结点数都是最大结点数。

满二叉树与完全二叉树

? 深度为k的、有n个结点的二叉树,当且仅当其每一个结 点都与深度为k的满二叉树中编号从1至n的结点一一对应 时,称之为完全二叉树。

1 A

2

3

B

C

4

5

6

7

D

EF

K

完全二叉树的特点: 1)叶子结点只可能在层次最大 的两层上出现。 2)对任一结点,若其右分支的 子孙的最大层次为L,则其左 分支的子孙的最大层次为L或 L+1。 3)满二叉树一定是完全二叉树, 反之不成立。

2.二叉树的基本性质
? 性质4 具有n个结点的完全二叉树的深度为?log2n?+1。
假设二叉树的深度为k,则根据性质2和完全二叉 树的定义有:
2k-1-1<n≤2k-1 或 2k-1≤n<2k 于是 k-1≤log2n<k 因为k是整数,所以k= ?log2n?+1

2.二叉树的基本性质
? 性质5
教材 P109

课堂练*
设一棵完全二叉树具有1000个结点。问该完 全二叉树有多少个叶子结点?有多少个度为2的结 点?有多少个度为1的结点?
答案: ∵ 结点数为1000时,树共有10层,若第10层全满则
树共有210-1=1023个结点,∴该树的第10层有结点512 (210-1)-23=489个,第九层有29-1=256个结点,其中有11 个叶子结点。
∴ 叶子结点有489+11=500个,度为1的结点有1个, 度为2的结点有1000-500-1=499个。

课堂练*

设一棵完全二叉树具有1000个结点。问该完

全二叉树有多少个叶子结点?有多少个度为2的结

点?有多少个度为1的结点?
答案:

若完全二叉树具有 1001个结点呢?

∵ 结点数为1000时,树共有10层,若第10层全满则 树共有210-1=1023个结点。

1023-1000=23,可推出n1=1。则n0+n1+n2= n2+1+1+n2=1000可推出n2=499

则n0=500

7.3.2 二叉树的存储结构
二叉树的存储结构也有顺序和链式两种。
1.顺序存储结构
用一组连续的存储单元存储二叉树的数据元素。 可用一维数组实现,即将完全二叉树上编号为i的结点 元素存储在一维数组下标为i 的数组元素中。

7.3.2 二叉树的存储结构
二叉树的存储结构也有顺序和链式两种。
1.顺序存储结构 对一般二叉树,为了体现结点之间的关系,也必须按完 全二叉树的形式来存储。
由此可见,这种顺序存储结构比较适用于完全二叉树或 满二叉树的存储,对于一般二叉树会造成存储空间的浪费。 因为,在最坏的情况下,一个深度为k且只有k个结点的单支 树(树中不存在度为2的结点)需要一维数组的长度为2k-1。

二叉树的顺序存储结构

A

B

C

D

EF

ABCDE F

A

B

C

F

ABC 0 0 F

2.链式存储结构
对于一般二叉树,最适合于使用二叉链表结构(非线性链表)来存 储它。在这种链表中,每个结点至少包含三个域,即:数据域和左、右 指针域,分别用data,lchild和rchild表示。其中数据域存放该结点所 包含的数据,左、右指针域分别指向该结点的左孩子和右孩子,当孩子 结点不存在时,相应的指针域为空。
有时为了便于找到 结点的双亲,可再设一 个指向该结点双亲的指 针域parent,这就变为
三叉链表了。

(a)

(b)

(c)

3.二叉链表的生成
二叉链表的生成,是指根据给定的二叉树在计算机中建 立该树的链式存储结构,这是对树进行处理的第一步。即对 二叉树进行处理时,第一步先要建立该树的存储结构,然后 才能进行各种处理。
假设按如下顺序依次输入给定二叉树中的各结点值: (1)输入根结点的值; (2)若左子树不空,则输入左子树,否则输入一个结束 符(可用空格表示); (3)若右子树不空,则输入右子树,否则输入一个结束 符;

3.二叉链表的生成

例如,要创建下图所示的二叉树,按上述原则输入的

字符顺序应为:

ABC□□DE□G□□F□□□

其中“□”表示空格。

A

二叉链表的结点类型定义为:
struct node { char data;
struct node *lchild; struct node *rchild; };

B

C

D

E

F

G

生成二叉树链表的算法:
struct node * creattree( ) { struct node *t ;
char ch ;

scanf(“%c”,&ch); /*依次输入二叉树中结点的值(一个字符),#字符表示空树 */

if (ch==‘#‘)

t=NULL;

else

{ t=(struct node *)malloc(sizeof(struct node));

if (t==NULL)

{ printf("out of memory\n"); exit(0); }

t->data=ch;

t->lchild=creattree();

/*建立它的左子树的二叉链表*/

t->rchild=creattree();

/*建立它的右子树的二叉链表*/

}

return t;

}

7.4 二叉树的遍历
所谓遍历二叉树(Traversing Binary Tree), 就是指按一定的规则和次序访问树中的每个结点,使每 个结点被访问且仅只被访问一次。
遍历二叉树是以一定规则将二叉树中的结点排列成 一个线性序列。实质上是对一个非线性结构进行线性化 操作,使每个结点(除第一个和最后一个之外)在这些 线性序列中有且仅有一个直接前趋和直接后继。

7.4.1 二叉树的先根遍历(先序法)
若二叉树为空,则返回。否则: (1)访问根结点; (2)先根遍历左子树; (3)先根遍历右子树; (4)返回。
例如,对下图(a)所示的二叉树进行先根遍历所得到的先根次序 的结点序列是ABCDEF。
同一先根序列可对应多棵二叉树。例如,图(b)所示的二叉树的 先根序列仍然是ABCDEF。可见,由先根序列不能唯一确定二叉树。

先根遍历的递归算法如下:
void preorder(struct node *t) /* t为指向二叉树根结点的指针 */ { if (t!=NULL)
{ visit ( t->data );/* printf(“%c ”, t->data ) ;*/ preorder( t->lchild ); preorder( t->rchild );
} }

void preorder(struct node *bt ) 遍历算法

bt { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); }

^C^

return;

}

void preorder(struct node *bt ) 遍历算法

bt { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild );
}
A
return;

^C^

}

void preorder(struct node *bt ) 遍历算法

bt { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild );
}
A
return;

^C^

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data); bt
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild );
}
A
return;

^C^

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data); bt
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ AB

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data); bt
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ AB

}

void preorder(struct node *bt ) 遍历算法

bt: ^ { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ AB

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data); bt
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ AB

}

void preorder(struct node *bt ) 遍历算法

bt: ^ { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ AB

}

void preorder(struct node *bt ) 遍历算法

bt { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ AB

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

bt
E^

preorder( bt->rchild ); } return;

^C^ AB

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

bt
E^

preorder( bt->rchild ); } return;

^C^ A BE

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

bt
E^

preorder( bt->rchild ); } return;

^C^ A BE

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);

preorder( bt->lchild ); preorder( bt->rchild ); } return;

^B^ ^
A BE

E^
bt
C^

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);

preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild );

bt
^C^

}

return;

A BEC

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);

preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild );

bt
^C^

}

return;

A BEC

}

void preorder(struct node *bt ) 遍历算法

bt: ^ { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ A BEC

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);

preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild );

bt
^C^

}

return;

A BEC

}

void preorder(struct node *bt ) 遍历算法

bt: ^ { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ A BEC

}

void preorder(struct node *bt ) 遍历算法

{ if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

bt
E^

preorder( bt->rchild ); } return;

^C^ A BEC

}

void preorder(struct node *bt ) 遍历算法

bt: ^ { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ A BEC

}

void preorder(struct node *bt ) 遍历算法

bt { if ( bt!=NULL)
A
{ printf(“%d ”,bt->data);
preorder( bt->lchild ); ^ B ^

E^

preorder( bt->rchild ); } return;

^C^ A BEC

}

7.4.2 二叉树的中根遍历(中序法)
若二叉树为空,则返回。否则: (1)中根遍历左子树; (2)访问根结点; (3)中根遍历右子树; (4)返回。
例如,对下图(a)所示的二叉树进行中根遍历所得到的中根序列 是ABCDEF。
同一中根序列可对应多棵二叉树。例如,图(b)所示的二叉树的 中根序列仍然是ABCDEF。可见,由中根序列不能唯一确定二叉树。

7.4.2 二叉树的中根遍历
中根遍历的递归算法:
void inorder(struct node *t)
/* t为指向二叉树根结构的指针*/
{ if ( t ! = NULL ) { inorder (t ->lchild ); visit ( t ->data ); /* printf(“%c ”, t->data ) ;*/ inorder ( t->rchild ) ; }
}

7.4.3 二叉树的后根遍历(后序法)
若二叉树为空,则返回。否则: (1)按后根次序遍历左子树; (2)按后根次序遍历右子树; (3)访问根结点; (4)返回。
例如,对下图(a)所示的二叉树进行后根遍历所得到的后根序列 是ABCDEF。
同一后根序列可对应多棵二叉树。例如,图(b)所示的二叉树的 后根序列仍然是ABCDEF。可见,由后根序列不能唯一确定二叉树。

7.4.3 二叉树的后根遍历
后根遍历的递归算法:
void postorder (struct node *t )
{ if (t!=NULL) { postorder (t->lchild); postorder(t->rchild); visit( t->data) ; /* printf(“%c ”, t->data ) ;*/ }
}

例 已知某二叉树的前根序列为ABCDEFG,中根序列为
CBDAEFG。求该二叉树的后根序列。
由前根序列可以推断:A是二叉树的根结点。 根据中根遍历的规则可知:在中根序列中,A左侧的C、B、D三个结点 构成了A的左子树,而A右侧的E、F、G三个结点构成了A的右子树。
A的左子树:前根序列为BCD,中根序列为CBD。 A的右子树:前根序列为EFG,中根序列为EFG。 此时,确定的二叉树如右图所示。
A的左子树: 根结点:B B的左子树:仅包含C,即C是B的左孩子。 B的右子树:仅包含D,即D是B的右孩子。
A的左子树分析完毕。如右图所示。

A的右子树: 根结点:E E的左子树:空。 E的右子树:前序序列为FG,中序序列为FG。如下左图所示。 根结点:F F的左子树:空。 F的右子树:仅包含G,即G是F的右孩子。 E的右子树分析完毕。
A的右子树分析完毕。如下右图所示。
二叉树的后根序列:CBDGFEA

7.4.4 二叉树操作实例

#include "alloc.h"

#include "stdio.h"

struct node

{ char data;

struct node *lchild;

struct node *rchild;

};

struct node *creattree()

/*建立二叉链表*/

{ char ch;

struct node *t;

scanf("%c",&ch);

if (ch==‘#') t=NULL;

else

{ t=(struct node *)malloc(sizeof(struct node));

if (t==NULL)

{ printf("out of memory\n"); exit(0); }

t->data=ch; t->lchild=creattree(); t->rchild=creattree();

}

return t;

}

void preorder(struct node *t) { if (t!=NULL)
{ printf("%3c",t->data); preorder(t->lchild);
} }

/*前根遍历二叉树*/ preorder(t->rchild);

void inorder(struct node *t) { if (t!=NULL)
{ inorder(t->lchild); inorder(t->rchild);
} }

/*中根遍历二叉树*/ printf("%3c",t->data);

void postorder(struct node *t)

/*后根遍历二叉树*/

{ if (t!=NULL)

{ postorder(t->lchild); postorder(t->rchild);

printf("%3c",t->data);

}

}

void main() {
struct node *root; printf("建立二叉树,按先根次序输入结点序列\n"); root= creattree(); printf("\n先根遍历次序为:\n"); preorder(root); getchar(); printf("\n中根遍历次序为:\n"); inorder(root); printf("\n后根遍历次序为:\n"); postorder(root); getchar(); }

7.5 线索树
7.5.1 线索树的结构
一个有n个结点的二叉树,其二叉链表共有2n个指针域,其中 用于指向孩子结点(左、右子树)的指针域只有n-1个,而另外2n(n-1)=n+1个指针域是空(NULL)的,可以利用这些空指针域来指 向结点在遍历序列的前趋或后继结点。其中,用树中空的左指针指 向该结点的前趋结点,空的右指针指向该结点的后继结点。
线索:指向遍历序列中的前趋结点或后继结点的指针。 线索化:对二叉树以某种次序进行遍历并加上线索的过程称为 线索化。 线索二叉树:经过线索化后生成的二叉树称为线索二叉树。

为了区分结点指针是线索指针还是子树指针,在每个

结点的指针中增加两个标志域 Lt 和 Rt:

0 Lt(或Rt)=
1

指向子树(孩子)的指针 指向前趋或后继结点的线索

Lt lchild data rchild Rt
线索树的结点结构
线索树的二叉链表的结点类型定义为: struct node { anytype data;
struct node *lchild; struct node *rchild; int Lt, Rt; };

BT
0A0

1B 0

1 C0

0 D1

1 E1 ^

1 F1
前根线索树示例 前根遍历序列:ABDFCE

BT
0A0

^ 1B 0

1 C0

0 D1

1E1 ^

1 F1
中根线索树示例 中根遍历序列: BFDACE

BT
0A0

1B 0

1C 0

0D 1

1E1

^1F 1
后根线索树示例 后根遍历序列: FDBECA

7.5.2 中序线索树的建立
线索树的建立实质是将二叉链表中的空指针指向遍历 序列的前趋结点、后继结点。
建立中根线索树,实际上是在中根遍历的过程中修改 空指针,即在访问结点的同时,将空指针域逐个用线索替 代,并将其标志位置1。

建立中根线索树的非递归算法为:

inthread (struct node *T)

{ struct node *p,*pr;

/* pr指向p的前趋结点 */

int top;

/* top为栈指针 */

struct node *s[MAX_TREE_SIZE];

pr =NULL;top=-1;p=T;

do

{ while( p!=NULL )

/*沿左孩子指针将结点依次入栈*/

{ top=top+1; s[top]=p; p=p->lchild;}

if ( top!=-1 )

{ p=s[top];top=top-1; visit(p->data );
if (p->lchild==NULL ) { p->Lt=1;p->lchild=pr;}

/*弹出栈顶结点,访问该结点*/
/*该结点无左孩子*/ /* 建左线索,使左指针指向前趋*/

else p->Lt=0;

}

if (pr!=NULL )

{ if (pr->rchild ==NULL )

{ pr->rchild= p;

/*建右线索,使前趋结点的右指针指向p*/

pr->Rt=1;

}

else

pr->Rt=0;

}

pr=p;

p=p->rchild;

} while (p!=NULL || top!=-1);

pr->Rt=1;

}

7.5.3 在中序线索树中检索结点的前趋或后继
1.求结点Q的前趋
若给定结点Q的左标志位Lt=1,则Q的左指针所指的 是Q的前趋结点,若Lt=0,则取Q的左子树的根(左孩 子),设为P,并作如下讨论:
(1)若P没有右子树,即Rt=1,则P为Q的前趋结点。 (2)若P有右子树,则必须连续不断地沿着右子树的 右指针,查询右孩子的标志位,若Rt=0,则通过右指针 找下一个结点(右孩子),若Rt=1,则该结点就是Q的 前趋结点。注意:在连续不断地向右子树查询中,不能 转向左子树。

BT
0A0

中根遍历序列: BFDACE

^ 1B 0

1 C0

0 D1
1 F1
?结点F的Lt=1,其左指针指向 的结点B即为它的前趋结点。

1E1 ^
?结点A的Lt=0,取其左子树的根结点 B,B有右子树,沿着B的右指针查询 到D结点的Rt=1,则D结点即为A的前 趋结点。
?结点D的Lt=0,取其左子树的根结点 F,F没有右子树,则F结点即为D的前 趋结点。

2.求结点Q的后继
若给定结点Q的右标志位Rt=1,则Q的右指针所指的 是Q的后继结点;若Rt=0,则取Q的右子树的根(右孩 子),设为P。
(1)若P没有左子树,即Lt=1,则P是Q的后继结点。
(2)若P有左子树,则必须连续不断地沿着左子树的 左指针,查询左孩子的标志位,若Lt=0,则通过左指针 找下一个结点(左孩子),若Lt=1,则该结点就是Q的 后继结点。注意:在连续不断地向左子树查询中,不能 转向右子树。

BT
0A0

中根遍历序列: BFDACE

^ 1B 0

1 C0

0 D1
1 F1
?结点F的Rt=1,其右指针指向 的结点D即为它的后继结点。

1E1 ^
?结点A的Rt=0,取其右子树的根结点 C,C没有左子树,则C结点即为A的后 继结点。
?结点B的Rt=0,取其右子树的根结点 D,D有左子树,沿着D的左指针查询 到F结点的Lt=1,则F结点即为B的后 继结点。

7.6 树、森林与二叉树的关系(教材第8章)
在实际应用中,树的形态多种多样,其中每个结点的 度都可以是任意的,这就给一般树的存储与研究带来了一 定的复杂性。为了处理的方便,通常需将一般树转化为二 叉树进行处理。
1.树与二叉树的转化
将一棵树T转化为二叉树BT的规则如下: (1)若T为空,则BT为空; (2)树T的根作为二叉树BT的根; (3)将树T中结点的第一个子结点(即最左边的子结点), 作为二叉树BT中对应结点的左子结点;T中该结点的其他子结 点,则依次作为前一结点的右子结点出现在BT中。

2.森林转化为二叉树
设F={T1,T2,…,Tm}是森林,可按如下规则将其转换 成一棵二叉树BT=(root,LB,RB)。
(1)若F为空,即m=0,则BT为空; (2)若F非空,则BT的根root即为森林中第一棵树的根; BT的左子树LB是从T1中根结点的子结点转换而成的二叉树; 其右子树RB是从森林F中除去T1以后的子森林转换而成的。

7.7 哈夫曼树及其应用
7.7.1 什么是哈夫曼树

结点的路径长度:从二叉树的根结点到该结点之间的所 有分支数目。
例如,下图(a)所示的二叉树中,a、b、c三个叶子结点 的路径长度分别为1、2、2。
结点的带权路径长度:指该结点的路径长度与该结点的 权值的乘积。
例如,图(a)中结点c的带权路径长度是2×7=14。
有时我们为二叉树的结点分 配一个数值,称为结点的权值。 例如,左图(a)中,a、b、c三个 结点的权值分别为9、3、7。

二叉树的带权路径长度:是指所有叶子结 点的带权路径长度之和,记为WPL。

n

WPL

? ? wk

p k

k ?1

其中,n为叶子结点的个数,wk为第k个叶子结点的权值,pk 为第k个叶子结点的路径长度。例如,图(a)中的二叉树共有三个
叶子结点,其带权路径长度计算如下:
WPL=w1×p1+ w2×p2+ w3×p3 =9×1+3×2+7×2=29

哈夫曼树(最优二叉树)
在具有n个带权叶子结点的所有二叉树中,带权路径长度 WPL最小的二叉树称为哈夫曼树(或最优二叉树)。
例如,下图所示的三棵二叉树,都有三个权值相同的带权 叶子结点。经计算,它们的带权路径长度分别为29、38、44。 其中(a)树的WPL最小。可以验证,它恰好是最优二叉树,即在 具有三个权值分别为9、3、7的带权叶子结点的所有二叉树中, 它是带权路径长度最小的二叉树。

7.7.2 哈夫曼树的构造
假设给定了n个结点dk(k=1,2,…,n),其权值分别为 {w1,w2,…,wn},构造哈夫曼树的过程如下:
(1) 根据给定的n个权值{w1,w2,…,wn}构造n棵二叉树的 集合F={ T1,T2,…,Tn },其中每棵二叉树Ti中只有一个带权 为wi的根结点,其左右子树均为空;
(2) 在F中选取两棵根结点的权值最小的树作为左右子树构 造一棵新的二叉树,且置新二叉树的根结点的权值为其左、右子 树上根结点的权值之和;
(3) 在F中删除这两棵树,同时将新得到的二叉树加入F中。 (4) 重复(2)和(3),直到F只含一棵树为止。这棵树就是哈 夫曼树。

例: 假设给定了5个结点a、b、c、d、e,其权值分别为4、
8、4、2、7。试构造以这5个结点为叶子结点的哈夫曼树,并计 算它的带权路径长度。要求左子树根结点的权值不大于右子树 根结点的权值。
下图展示了此哈夫曼树的构造过程:
带权路径长度为:WPL=(7+8)×2+5×2+(2+4)×3 =58

7.7.3 哈夫曼编码
哈夫曼树可用于编码问题。在进行远距离快速通信时, 通常要将需要传送的文字转换成由二进制数字组成的字符串。 假设需要传送电文“ABACCDA”,这其中只用到A、B、C、D四 种字符,可以用两位二进制数字分别对字符A、B、C、D编码 为00、01、10、11,则实际传送的电文为 “00010010101100” ,总长14位,在接收端可按两位一分进 行译码。
在实际应用中,总是希望电文的总长度尽可能短,这就 需要对电文中的各种字符设计长度不等的编码,并对电文中 出现次数较多的字符采用尽可能短的编码。

设电文中共有n种不同的字符,每种字符在电文中

出现的频率为wi ,其编码长度为pk,则电文总长为:

n

? wk

p k

k ?1

对应到二叉树上,若n种字符为二叉树的叶子结点,

wk为叶子结点的权值,pk为叶子结点的路径长度,则

n

? wk

p k

恰好为二叉树的带权路径长度。因此,设计电文总长

k ?1

最短的二进制编码的问题,实际上就是设计哈夫曼树

的问题。

利用哈夫曼树设计编码
设电文中共有n种不同的字符,每种字符在电文中出现的频 率为wi。将这n个字符作为二叉树的叶子结点,构造一棵具有n 个叶子结点的哈夫曼树,然后对叶子结点进行编码,便可满足 以上编码的要求。
在对哈夫曼树上的叶子结点进行编码时,有如下约定: 所有左分支表示二进制数字“0”,右分支表示二进制数字 “1”,则从根结点到叶子结点的路径上各分支的二进制数字顺 序组成的串称为该叶子结点的编码。
设电文为“ABACCDA”, 则利用哈夫曼树设计的电文 中各字符的编码如右图所示。

7.8 二叉查找树
我们知道,对树或二叉树进行遍历,可以搜索到其中任何 一个结点。那么,能否将记录组织成某种树型结构,然后将查 找工作在树上进行呢?答案是肯定的,可以利用二叉查找树 (也称二叉排序树)来实现。
7.8.1 二叉查找树的定义及其结构
二叉查找树若非空,则是具有以下性质的二叉树: (1)若根结点的左子树不空,则左子树上所有结点的值 均小于它的根结点的值; (2)若根结点的右子树不空,则右子树上所有结点的值 均大于或等于它的根结点的值; (3)根结点的左、右子树也分别为二叉查找树。

二叉查找树示例

60

50

80

40

52

中序遍历序列?

90 85

7.8.2 二叉查找树的建立

当给出一组无序的数据序列后,依次输入每一个元 素,每输入一个元素,就建立一个新结点,然后按下列 原则把结点插入到已建立的二叉查找树中去:

(1) 若二叉查找树是空树,则该结点成为二叉查找 树的根结点;

(2) 若二叉查找树非空,则将新结点中的关键值与

根结点比较,若小于根结点的值,则插入到左子树中;

否则插入到右子树中去。 <=根结点值

>根结点值

例如,有一组无序的数据序列{ 60,50,80,90,52,40, 85 },试构造相应的二叉查找树.

例如,有一组无序的数据序列{ 60,50,80,90,52,40, 85 },试构造相应的二叉查找树.
60

60

60

60

50

50

50

80

80 90

60

60

60

50

80

50

80

50

80

52

90

40

52

90

40

52

90

85

插入值为87的结点后,该二叉查找树会如何变化?

60

50

80

40

52

90 85

87

每次插入一个结点的算法 :
struct node { anytype data;
struct node *lchild; struct node *rchild; }*root; void insnode(struct node *t, Elemtype d)
/* 在以t为根结点的二叉查找树中插入关键字为d的结点*/
{ struct node *r,*p; r=(struct node *)malloc(sizeof(struct node)); if (r==NULL) { printf("out of memory\n"); exit(0);} else { r->data=d; r->lchild=NULL; r->rchild=NULL; }

if (t==NULL)

/*该结点为第一个结点*/

root=r;

else

while (t!=NULL)

if (d<t->data)

if (t->lchild==NULL)

{ t->lchild=r; t=NULL; }

else t=t->lchild;

else

if (t->rchild==NULL)

{ t->rchild=r; t=NULL; }

else t=t->rchild;

}

下面是调用插入一个结点的算法insnode(t,d),建 立一棵具有n个结点的二叉查找树的算法:
void creat() { int i,n,d;
root=NULL; printf("\n input n\n"); scanf("%d",&n); for(i=1;i<=n;i++) {
scanf("%d",&d); insnode(root,d); } }

7.8.3 在二叉查找树上进行查找
在二叉排序树中查找一个关键字值为k的结点的基本思路: 用给定值k与根结点关键字比较,如果k小于根结点的值,则要 找的结点只可能在左子树中,转而在左子树中查找;否则在右 子树中继续查找,依此类推一步步查找下去,直到查找成功或 查找失败为止。
查找过程描述如下:
(1)若二叉树为空,则查找失败; (2)若 K=根结点的关键字值,则查找成功,结束;
(3)若 K﹤根结点的关键字值,则在左子树中继续查找;
(4)若 k≥根结点的关键字值,则在右子树中继续查找。

二叉查找树查找的递归算法:

struct node *searchbst(struct node *T,Elemtype key)

/*在根指针T所指二叉查找树中递归查找某关键字等于key的结点,若 查找成功,则返回指向该结点的指针,否则返回空指针*/

{ if ((T==NULL) || (key==T->data))

return(T);

/*查找结束*/

else

if (key<T->data)

/*在左子树中继续查找*/

return (searchbst( T->lchild,key));

else

/*在右子树中继续查找*/

return (searchbst (T->rchild,key ));

}

二叉查找树查找的非递归算法:

struct node *searchbst(T,key)

struct node *T; anytype key;
/*在根指针T所指二叉查找树中递归查找某关键字等于key的结点,若 查找成功,则返回指向该结点的指针,否则返回空指针*/

{ struct node *p;

p=T;

while((p!=NULL) &&(key!=p->data))

{ if (key<p->data)

/*在左子树中继续查找*/

p=p->lchild;

else

/*在右子树中继续查找*/

p=p->rchild;

}

return(p);

}

7.8.5 二叉查找树的查找分析及评价
在二叉排序树的查找过程中,每进行一次关键字比较, 要么查找成功,要么确定到左子树或右子树中继续查找,关 键字的比较次数等于被查找结点所在的层次,因此二叉排序 树查找的*均比较次数与二叉排序树的深度有关。
从另一角度分析,在二叉树排序树查找过程中,通过与 根结点的一次比较,就可以抛弃一棵子树中的所有结点,因 此,二叉排序树查找的效率与折半查找类似。但是,由于同 一批元素所构成的二叉排序树不是唯一的,它与元素插入的 顺序有关。在最坏情况下,如果构成的二叉排序树实际上是 单支树,则查找效率与顺序查找的效率是一样的。最好的情 况是,二叉查找树各结点的左右子树的深度相差不超过1(称 之为*衡二叉树),,其*均查找长度和log2n成正比,与折 半查找相同。为了做到这一点,可以在生成二叉查找树的过 程中进行适当的调整,使之成为*衡二叉树。

本章小结
要点: 二叉树的相关术语及相关性质。 二叉树的遍历和线索化。 树、森林与二叉树的转化。 哈夫曼树和哈夫曼编码。 二叉排序树。




友情链接: