计算机软件基础：14第四章数据结构二叉树

《计算机软件基础》多媒体教程

第十四讲

第四章数据结构

4.树

4.5二叉树

※二叉树的定义

在一棵二次树中，若规定后件是有序的，即对于任何一个结

点，规定它的第一后件称为左子（左后件，左件），第二后件称为右

子（右后件，右件），那么这是一棵二次有序树，并被称为二叉树

（BinaryTree）。

二叉树的结点可以既有左子又有右子，也可以只有左子，或

者只有右子，甚至没有后件。

用图形表示时，左子画在左下方，右子画在右下方。

※二叉树的括号表示

。定义

根（左子树，右子树）或根（左子树,）或根（，右子树）或根

例如，图示二叉树的括号表示：

A为根的二叉树：A（B（,D（GH））,C（E（,F）,））

A的后件A(B,C)

B的后件B(,D)

C的后件C(E,)

D的后件D(G,H)

E的后件E(,F)

◎Backus描述形式之一◎Backus描述形式之二

〈二叉树〉::=〈根〉〈二叉树〉＜根＞

I〈根〉〈子树〉|〈根〉（〈子树〉）

〈子树＞：：=（〈左子树〉，〈右子树〉）v子树〉::=〈左子树,，〈右子树〉

I（〈左子树〉，）|〈左子树〉，

I（,〈右子树〉）|,v右子树＞

〈左子树〉::=〈左子〉〈左子树＞：：=〈左子〉

|v左子〉v子树〉|＜左子〉（V子树》）

〈右子树〉::=v右子〉〈右子树〉::=〈右子〉

|v右子〉〈子树〉I〈右子〉（〈子树〉）

4.5.1二叉树的存储形式

※标准形式

设置两个指针场分量（PLeftk和Pdghtk）,分别指向左子和右子。

ak8kPLeftkPrightk

10A2060

20B①30

30D4050

40G（D（1）

50H

60c70（D

70E（1）100

100F0cD

※逆形式

设置一个指针场分量Pprek,指向父结点。

#defineBINODEstructbinode

BINODE

(

char*s;

BINODE*father,*Left,*right;

);

BINODE*Root;

每个BINODE结构存

放一个结点，根结点由

Root指向，father,Left

和right分别指向父结点和

左右子。

※用数组存储二叉树的扩充标准形式

#defineBINODEstructbinode

BINODE

(

char*s;

shortfather,Left,right;

)；

BINODETree[100];

shortRoot;

每个数组元素Tree[i](i=0，…,n-1)存放一个

结点。用数组下标表示结点地址，用-1表示空

地址。定义变量Root指向根结点。结点成员

father,Left和right分别指向父结点和左右子。

4.5.2二叉树的遍历

※前序遍历

先访问根

按前序遍历左子树

按前序遍历右子树

图示树的前序遍历结果：ABDGHCEF

※后序遍历

按后序遍历左子树

按后序遍历右子树

最后访问根

图示树的后序遍历结果：GHDBFECA

※中序遍历

按中序遍历左子树

访问根

按中序遍历右子树

图示树的中序遍历结果：BGDHAEFC

※中序遍历与投影特性

投影步骤：

1）将所有左子树中的结点都画在结点的左下方

2）将所有右子树中的结点都画在结点的右下方

3）然后垂直投影

将得到二叉树的中序遍历：

BGDHAEFC

【例4-5.1】二叉树标准形式的数组编程

。编程要求

用数组存储树的标准形式，用递归函数实现二叉树的中序遍历

(网络课堂：exe4-5.1BiTree.c)

。程序中的数据定义

#defineBINODEstructbinode

BINODE

chars[10];

shortleft,right;

）；

BINODET[100];

shortn;

每个数组元素T[i]（i=0，…,n-1）存放一个结点。用数组下标表示结点地址，用-1表示空地

址.定义变量root指向根结点。结点成员left和right分别指向左右子。

iT[i].sleftright

0A21

1B4-1

2c-13

3D67

4E-15

5F-1-1

6G-1-1

7H-1-1

。函数实现

voidCreateBitree(short*n,short*root)输入数据为:

80

inti;A21

scanf("%d%d",n,root);B4-1

for(i=0;i<*n;i++)C-13

scanf("%s%d%d",D67

T[i].s,&T[i].Left,&T[i].right);E-15

)F-1-1

main()G-1-1

H-1-1

shortroot;

CreateBitree(&n,&root);/*输入并生成二叉树*/

symOrder(root);/*中序遍历函数7

)

。中序遍历函数及运行过程示例

symOrder(shortnode)

(

if(node==-1)

return;

symOrder(T[node].Left);

u,,

printf(%s\nJT[node].s);

symOrder(T[node].right);

CsymOrder(-l)

Gprint'G'

DsymOper(-l)

H

AsymOrder(-l)

Eprint'H'

FsymOrder(-l)

B

r>symOrder(-1)

print'F'

|symOQer(-1)

【例4・5.2】二叉树标准形式的链接编程

G）编程要求

输入用括号表示的二叉树，例如:

A(C(,D(G,H),B(E(,F),))

用链接的结构存储树的标准形式

用递归函数实现二叉树的后序遍历

(网络课堂：exe4-5.2BiTree.c)

。程序实现

#defineBINODEstructbinode

BINODE

(FF20

char*key;

BINODE*Left,*right;

)；

BINODE*Root;

voidpostOrder(BINODE*node)

(

if(Inode)

return;

postOrder(node->Left);

postOrder(node->right);

printf(“node=%s\n"，node・>key);

)

voidCreateBitree(void){见：exe5-5.2BiTree.c}

main()

(

CreateBitree();/*输入并生成二叉树*/

postOrder(Root);/*后序遍历*/

}

4.5.3二叉树的顺序存储

※二叉树的顺序存储

根据树的定义，每个结点的后件不止一个。严格地说，不能采取顺序存储的方式来存储

树，或者说不能用直接用数组实现树的存储，因为无法满足ak'=ak+s(k是k'的前件)，而只

能用链接方式进行存储。

但是如果采用某种约定，例如根据某种遍历方式，可以实现树的顺序存储。因为遍历是

一种线性的关系，当结点k是结点k'关于某种遍历的前件时，可以满足ak'=ak+S。在二叉

树的存储中，往往采用这种修正的顺序存储方式。例如，按照前序遍历实现二叉树的顺序存

储，可以满足前序遍历的前后件关系，但是二叉树中每个结点还有另外一个结点，必须采取

一定的约定，或者说需要附加某种存储关系。

※采用flag约定的前序遍历顺序存储

。约定顺序存储的定义

修正树的存储单元定义，例如，将卜=以正纵邛倒扩充为k={ak,瓯pk,flag},即增加一

个flag标志，以说明结点另外一个后件(非遍历后件)的存储信息。由于二叉树中结点的后件

最多是两个，因此可以用pk和flag来存储结点的后件。

假定采用以下的flag约定的存储定义：

Dk=fakR结点k有右子kj,=f1结点k有左子k(.

口一1①结点k无右子kRyLo结点k无左子k(_

规定结点k的右子kR地址用指针场pk表示。而左子h的地址信息用flag说明，如果

结点有左子h，则必定是前序遍历的后件。因此若flag为1,表示结点k有左子L，即

aki_=ak+s,否则表示结点k没有左子h。

◎flag约定的存储单元示例⑴

根据约定，pk和什ag的取值有四种情况，分别是：

(1)结点k有左件h，有右件kR织2)

则flag=1,pk=akR,aki_=ak+s,如结点A和D。MD⑵

(2)结点k无左件h，有右件kR

则flag=O,pk=akn，如结点B和E。(4)⑼(4)(HJ(4)(F

(3)结点k有左件ku无右件kR

则flag=1,pk=-1,akL=ak+s,如结点C。情况ak8kpkflag

(4)结点k无左件ki_,无右件KR(1)0A51

则flag=0,pk=-1,如结点G,H和F。(2)1B20

Oflag约定的顺序存储示例(1)2D41

3-10

数据定义(4)G

(4)4H-10

#defineM100

5-11

#defineBITREEstructbitree(3)c

E7

BITREE(2)60

(4)7F-10

char*s;

shortp,flag;

)；

BITREEtree[M];

shortn;

。前序遍历函数

voidpreOrder(BITREE*tree)

(

inti;

for(i=0;i<n;i++)

printf(**node=%s\n",tree[i].s);

)

。打印左件的程序(取决于flag)

根据结点k的地址j,打印其左件。

if(tree[j].flag==0)

printf(unoLeftchiLd'n");

eLse

printffLeftchiLdis%s\n",tree[j+1].s);

。打印右件的程序(取决于pk)

根据结点k的地址j,打印其右件。

if(tree[j].p==-1)

printf(HnorightchiLd'n");

eLse

H,,

printf(rightchiLdis%s\n)tree[tree[j].p].s);

。打印前序前件的程序(数组前一元素)

根据结点k的地址j,打印其前序前件。

if(j==O)

printf(*,nopredecessor\nn);

eLse

printf(upredecessoris%s\n"，tree[j-1].s);

※采用一个指针场的前序遍历顺序存储

。数据定义

设存储单元为k={ak,bk,pk},存放结点的数组定义为

#defineM100

#defineABS(x)(x>0)?(x):(-x)

#defineBITREEstructbitree

BITREE

char*s;

shortp;

);

BITREEtree[M];情况ak5kPk

shortn;/*结点数n<=M7(1)0A5

Opk的定义(2)1B-2

(1)结点k有左件有右件kR,则pk=akR(1)2D4

(4)3G-100

(2)结点k无左件kL,有右件kR,则pk=-akR

(3)结点k有左件k,无右件k,则pk=M(4)4H-100

LR5c100

(4)结点k无左件ki_,无右件kR,则pk=-M(3)

(2)6E-7

。确定结点k的左件和右件地址的法则

(4)7F-100

若pk>0,则结点k有左件，且akL=ak+s。

若pk<0,则结点k无左件。

若|pk|!=M,则结点k有右件,fiakR=|pk|«

若|pk|==M,则结点k无右件。

。前序遍历函数

voidpreOrder(BITREE*tree)

(

inti;

for(i=0;i<n;i++)

printf(unode=%s\n",tree[i].s);

)

。打印左件的程序(判pk>0)

根据结点k的地址j,打印其左件。

if(tree[j].p<0)

printfC'noLeftchiLd'n")；

eLse

prin廿("LeftchiLdis%s\n",tree[j+1].s);

。打印右件的程序(判绝对值|pk|)

根据结点k的地址j,打印其右件。

if(ABS(tree[j].p)==M)

printfC'norightchiLd\n");

eLse

printf("rightchiLdis%s\n",tree[ABS(tree[j]p)].S);

。打印前序前件的程序(数组前一元素)

根据结点k的地址j,打印其前序前件。

if(j==O)

printf("nopredecessor\n");

eLse

printf("predecessoris%s\n",tree[j-1].s);

4.5.4穿线树

※穿线树

考察采用标准形式存储二叉树的情况。若有n个结点，共2n个指针场分量。因为根结

点没有前件，其他每个结点只有一个父结点，因而共有n-1个指针场分量被利用，而n+1

个被空置(浪费)。为了提高指针的利用率，我们引入穿线树的概念。

※利用空闲指针场形成穿线树的方法

对空闲的左子指针，用于指向其中序前件。

对空闲的右子指针，用于指向其中序后件。

这样被利用的指针有n-1个，则最后只有两个

指针指向空，而不能再少.其中一个为中序始结点，

另一个为中序终结点。

用虚线表示弓器树的前后件关系，以便与二叉

树的前后件关系有所区别。

※穿线树的存储单元定义

#defineM100

#defineABS(x)(x>0)?(x):(-x)

#defineTHstructthread

TH

(

shortnum,pL,pR;

)；

THth[M];

shortn;/*结点数*/ak8kPLpR

按标准形式用结构数组存放穿线树。11026

其中，用th⑴〜th[n]存放n个结点，用th[0].num22003

存放根结点的地iit,本例中th⑼.num=1。34045

用0表示空地址。穿线指针场的值(中序前件或460-2-3

者中序后件的地址)用负数表示。对中序始结点tb(如580-3-1

63070

结点B),必定有th[tb].pL==0。对中序终结点te(如

750-18

结点C),必定有th[te].pR==0o

870-7-6

※穿线树的处理函数

。根据结点k的地址i,求其中序前件k，

shortgetPre(TH*th,shorti)

(

if(i<1||i>n)/*非法地址*/

error();

if((i=th[i].pL)>0)/*有左子*/

whiLe(th[i].pR>0)/*有右子*/

i=th[i].pR;

return(ABS(i));

)

。例如已知i=4,求结点60的中序前件k'：

th[4].pL(=-2)<0,无左子，得ak'T-2|=2,

则5k'=20(th[2].num).

ak5kPLPR

11026

22003

405

D60-2-3

580-3-1

63070

750-18

870-7-6

函数调用为：

if(k=getPre(th,i=4))

printf(uprevnodeof%dis%d\n",th[i].num,th[k].num);

else

printf("noprevnodefor%d.\n",th[i],num);

。例如已知i=1,求结点10的中序前件k'：

th[1].pL(=2)>0,有左子，令i=2；

th[2].pR(=3)>0,有右子，令i=3；

th[3].pR(=5)>0,有右子，令i=5；

th[5].pR(=-1)<0,无右子，得ak'=5,

则8k'=80(th[5].num)o_______

ak3kpR

1026

22003

34045

460-2

580-3D

63070

750-18

870-7-6

函数调用为：

if(k=getPre(th,i=1))

printf(uprevnodeof%dis%d\n",th[i].num,th[k].num);

eLse

printf(unoprevnodefor%d.\n",th[i].num);

0根据结点k的地址i,求其中序后件k'

shortgetSuc(TH*th,shorti)

(

if(i<1||i>n)/*非法地址*/

error();

if((i=th[i].pR)>0)/*有右子*/

whiLe(th[i].pL>0)/*有左子*/

i=th[i].pL;

return(ABS(i));

)

。例如已知i=8,求结点70的中序后件k'：

th[8].pR(=-6)<0,无右子，得ak'=k6|=6,

则3k'=30(th[6].num),,

函数调用为：

if(k=getSuc(th,i=8))

printf(usucnodeof%dis%d\n",th[i].num,th[k].num);

eLse

printf("nosuenodefor%d.\n",th[i].num);

ak5kpLPR

11026

22003

34045

460-2-3

580-3-1

63070

750-18

870-7Bra

。例如已知i=1,求结点10的中序后件k'：

th[1].pR(=6)>0,有右子，令i=6；

th[6].pL(=7)>0,有左子，令i=7；

th[7].pL(=-1)<0,无左子，得ak'=7,

则8k'=50(th[7].num)1,

函数调用为：

k=getSuc(th,i=1);

ak8kPLPR

D1026

22003

34045

460-2-3

580-3-1

67

750-1

KI■a

。求中序的始结点指针akfirst

shortgetFirst(TH*th)

(

shorti;

if((i=th[0].num)==0)/*空树*/

return(i);

whiLe(th[i].pL!=0)/*有左子7

i=ABS(th[i].pL);

return(i);

}

。例如，总是从1=叼0].011171=1开始，

th[1].pL(=2)!=0,有左子，令i=2,

th[2].pL==0,无左子，得ak'=2,

则5k'=20(th[2].num)«

ak5kpLPR

11026

22003

34045

460-2-3

580-3-1

63070

750-18

函数调用为:870-7-6

if(k=getFirst(th))

printf("firstnodeforthreadtreeis%d.\n",th[k].num);

eLse

printf("nonodeinthetreeAn");

。中序遍历

voidsymOrder(TH*th)

(

shortp;

if((p=getFirst(th)==0)/*求树根*/

error();/*空树*/

do

printf("node=%d\n",th[p].num);

while(p=getSuc(th,p))

;/*求中序后件*1

ak3kPLPR

11026

22003

34045

460-2-3

580-3-1

63070

750-18

函数调用为：870-7-6

symOrder（th）;

4.6二叉树的线性表示及生成

4.6.1二叉树的层号表示

※二叉树的层号及层号表示

。图示二叉树的层号

层号=1：A

层号=2：B,G

层号=3：E,F,K

层号=4：H,J,L

。前序遍历的层次表示

1A,2B,3E,4H,3F,2G,3K,4J,4L

。后序遍历山层次表示

4H,3E,3F,2B,4J,4L,3K,2G,1A

。中序遍历的层次表示

3E,4H,2B,3F,1A,4J,3K,4L,2G

派二叉树层号表示的唯一性问题

。前序遍历的层号表示

一个结点的前序遍历后件可为左子（如G）,也可为右子（如E）。

所以，前序遍历的层号表示不能唯一地确定一棵二叉树。

。后序遍历的层号表示

一个结点的后序遍历前件可为左子（如G）,也可为右子（如E）。

所以，后序遍历的层号表示也不能唯一地确定一棵二叉树。

。中序遍历的层次表示

一个结点如果有左子，左子在中序遍历中的位置一定在该结点前方；一个结点如果有右

子，右子在中序遍历中的位置一定在该结点后方。

所以，中序遍历的层次表示可以唯一地确定一棵二叉树。

4.6.2括号表示和二叉树的生成

※二叉树的括号表示

如果二叉树T只有一个结点，此结点就是它的括号表示。

如果二叉树由根结点R和左子树TL和右子树TR组成，则树T的括号表示就是:

R（TL的括号表示,TR的括号表示）。

由于二叉树的左子树TL和右子树TR可能只出现任意一支，所

以二叉树的括号表示可以是：

R（TL的括号表示,）或者R（,TR的括号表示）或者

R（TL的括号表示,TR的括号表示）或者R

图示树的二叉树的括号表示

A（B（E（,H）,F）,C（,K（L,）））

根据二叉树的括号表示，可以唯一地确定一棵二叉树。

二叉树的括号表示和层号表示可以相互转换。

【例4-6.2］二叉树的生成算法（exe4-6.2BiTree.c）

※根据输入的括号表示字符序列，生成并存储二叉树

采用结构数组存储二叉树的结点，结点值为字母。例如输入的括号表示字符序列为:

A(B(D,E),C(F(,G),))

※二叉树的生成算法及程序实现

。程序中的数据定义

#defineM1000

#defineEMPTY-1

#defineNODEstructnode

NODE

charkey;/*结点字符*/

shortLeft,right;/*左右子地址*/

)；

NODETree[M];/*二叉树*/

shortRoot;/*根地址*/

shortN=EMPTY;/*结点数目*/

charString[M];1*输入字符串*/

shortPtr=EMPTY;/*字符数组指针*/

ak8kLeftright

0A14

1B23

2D-1-1

3E-1-1

4c5-1

5F-17

6G-1-2

。算法思路

初始化：输入二叉树的括号表示，存入字符串数组String}

生成二叉树的根；

然后调用生成二叉树子树的函数，按“（左子树，右子树）”的格式，递归生成子树。

。递归生成子树的算法描述

1.取左括号（如果省略，表示空子树）

2.取左子（可以省略）

2.1.生成并存储左子

2.2.连接左子

2.3.递归生成左子树

3.取逗号（不可省略）

4.取右子（可以省略）

4.1.生成并存储右子

4.2.连接右子

4.3.递归生成右子树

5.取右括号(不可省略)

※函数设计

OGetData()获取结点值

从String中取一个结点字符，成功时返回1,否则返回0。

0GetSymboL()获取有效符号

从String中取一个符号：“(”左括号，了右括号，或者逗号

成功时返回1,否则返回0

OCreateNode()生成并存储结点

生成结点，令左子和右子指向空，将结点存入数组Tree中。

OCreateSubTree()生成子树

按"(左子树，右子树)”的格式，调用GetData()和GetSymboL()获取结点值和有效符号。

若左子树或右子树非空，递归调用CreateSubTree()生成子树。

OCreateBiTree()生成二叉树

生成根结点，调用CreateSubTree。生成子树。

Omain()

1.输入括号表示的字符串

2.调用CreateBiTree生成二叉树

3.输出存储的二叉树

※函数实现

OGetData()获取结点值OGetSymboL()获取有效符号

从String中取一个字母，从String中取一个指定的符号：

成功时返回1,否则返回0。T，T，或者

shortGetData(char*key)成功时返回1,否则返回0

(shortGetSymboL(charsymboL)

if(Sring[Ptr+1]=='\0')(

return(0);/*无字符*1if(Sring[Ptr+1]=='\0')

/*从String中取一个字符*/return(O);/*无字符*/

*key=Sring[++Ptr];/*从String中取一个符号*1

if(isaLpha(*key))/*判字母*1if(Sring[++Ptr]==symboL)

return(1);return(1);

Ptr-;/*非字母，回退7Ptr-;I*非符号，回退*1

return(O);return(O);

)

OCreateNodeO生成并存储结点

生成结点，令左子和右子指向空，将结点存入数组Tree中。

shortCreateNode(charkey)

(

Tree[++N].key=key;/*存储结点值*/

Tree[N].Left=EMPTY;/*左子树置空*/

Tree[N].right=EMPTY;/*右子树置空*/

return(N);/*返回结点地址*/

ak8kLeftright

0A14

1B23

2D-1-1

3E-1-1

OCreateSubTree()生成子树

按“(左子树，右子树)”的格式，调用GetData。和GetSymboL。获取结点值和有效符号,

并递归调用CreateSubTree()生成子树。

voidCreateSubTree(shortroot)

(

shortkey,Left,right;

/*1.取左括号(可以省略)*/

if(GetSymboL('(,)==0)

return;

/*2.取左子(可以省略)*1

if(GetData(&key)!=0)

(

1*2.1.生成并存储左子*/

Left=CreateNode(key);

/*2.2.连接左子*1

Tree[root].Left=Left;

/*2.3.生成左子树7

CreateSubTree(Left);

)

/*3.取逗号(不可省略)*1

if(!GetSymboL(V))

error();

r4.取右子(可以省略)7

if(GetData(&key))

(

/*41生成并存储右子*/

right=CreateNode(key);

r4.