第六章树和二叉树

红楼梦贾家家谱6.1树的类型定义6.2二叉树6.3

遍历二叉树和线索二叉树6.4树和森林6.6哈夫曼树及其应用第6章树和二叉树6.1树的类型定义数据对象D：D是具有相同特性的数据元素的集合。

若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。

数据关系R：ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根例如:树形图表示的例子ABKELFDHMJICG嵌套集合表示法ABCDEKLFGHIJM凹入表示法（A(B(E(K,L),F),C(G),D(H(M),I,J)))广义表表示法ABCDEFGHIJMKL对比树型结构和线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素

(无前驱)

根结点

(无前驱)最后一个数据元素

(无后继)多个叶子结点

(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)基本术语结点:结点的度:树的度:叶子结点:分支结点:一个数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。任何一棵非空树是一个二元组

Tree=（root，F）其中：root被称为根结点

F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF6.2

二叉树的类型定义

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树

的重要特性

性质1：

在二叉树的第i

层上至多有2i-1个结点。(i≥1)用归纳法证明：

i=1

层时，只有一个根结点：

2i-1=20=1；二叉树中第5层上的结点个数最多为____A.8 B.15

C.16 D.32性质2：

深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：

基于上一条性质，深度为k的二叉树上的结点数至多为

20+21+

+2k-1=2k-1

。深度为5的二叉树至多有（

）结点。A．64 B．32C．31 D．63

性质3：

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为

2

的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。度为1的结点1、一棵二叉树有67个结点,这些结点的度要么是0，要么是2。这棵二叉树中度数为2的结点有

个。两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij

性质4：

具有n个结点的完全二叉树的深度为

log2n+1。证明：设完全二叉树的深度为k则根据第二条性质得2k-1-1<n≤2k

-1计算得出：2k-1≤n<2k即

k-1≤log2n<k

因为k只能是整数，因此，k=log2n

+1。性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1

至n

的编号，则对完全二叉树中任意一个编号为i

的结点：

(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；

(2)若2i>n，则该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点，

否则，编号为2i+1的结点为其右孩子结点。1.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。A.98 B.99C.50 D.486.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示例如:ABCDEF

ABDCEF

0123456789101112131401326一、二叉树的顺序存储表示二、二叉树的链式存储表示1.二叉链表2．三叉链表ADEBCFrootlchilddatarchild结点结构:1.二叉链表typedefstruct

BiTNode

{//结点结构

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:ADEBCFroot2．三叉链表parent

lchilddatarchild结点结构:

typedefstruct

TriTNode

{//结点结构

TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指针

structTriTNode

*parent;//双亲指针

}TriTNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:6.4二叉树的遍历

顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。一、问题的提出“访问”的含义可以很广，如：输出结点的信息等。

“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，不需要另加讨论。而二叉树是非线性结构。

二叉树每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。二、按层次遍历二叉树

实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。按层次遍历该二叉树的序列为：

ABECFDGHKABCDEFGHK三、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法

若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：四、算法的递归描述voidPreorder(BiTreeT,void(*visit)(TElemType&e)){//

先序遍历二叉树

if(T){

visit(T->data);//访问结点

Preorder(T->lchild,visit);//遍历左子树

Preorder(T->rchild,visit);//遍历右子树

}}ABCDEFGD

L

RTD

L

RD

L

RABED

L

RD

L

RDLRDLRCFDG先序遍历结果:ABCDEFGT

若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：voidInorder(BiTreeT,

void(*visit)(TElemType&e)){//

中序遍历二叉树

if(T){

Inreorder(T->lchild,visit);//遍历左子树

visit(T->data);//访问结点

Inreorder(T->rchild,visit);//遍历右子树

}}ABCDEFGL

D

RTL

D

RL

D

RABEL

D

RLD

RLDRLDRCFDG中序遍历结果:BDCAGFET

若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：voidPostorder(BiTreeT,

void(*visit)(TElemType&e)){//

后序遍历二叉树

if(T){

Postreorder(T->lchild,visit);//遍历左子树

Postreorder(T->rchild,visit);//遍历右子树

visit(T->data);//访问结点

}}ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA练习：设二叉树结点的先序序列为ABDECFGH，中序序列为DEBAFCHG,则二叉树的后序序列是

。

五、中序遍历算法的非递归描述

中序遍历示意图图中序遍历二叉树的非递归算法处理流程

算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)中序遍历非递归算法pABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)ABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)算法一：StatusInorderTraverse(BitreeT,Status(*Visit)(TElemTypee)){

InitStack(S);Push(S,T);//根指针进栈

while(!StackEmpty(S)){

while(GetTop(S,p)&&p)Push(S,p->lchild);

//向左走到尽头

Pop(S,p);

//空指针退栈

if(!StackEmpty(S)){//访问结点，向右一步

Pop(S,p);if(!Visit(p->data))returnERROR; Push(S,p->rchild); }}returnOK;}StatusInorderTraverse(BitreeT,Status(*Visit)(TElemTypee)){

InitStack(S);p=T;while(p||!StackEmpty(S)){

if(p){Push(S,p);p=p->lchild;}

//根指针进栈，遍历左子树

else{//根指针退栈，访问根结点

Pop(S,p);if(!Visit(p->data))returnERROR; p=p->rchild; }}returnOK;}算法二：六、遍历算法的应用举例2、统计二叉树中叶子结点的个数(先序遍历)3、求二叉树的深度(后序遍历)1、输入结点值，构造二叉树(先序遍历）1、输入结点值，构造二叉树算法基本思想:

先序(或中序或后序)遍历二叉树，读入一个字符，若读入字符为空，则二叉树为空,若读入字符非空，则生成一个结点。将算法中“访问结点”的操作改为：生成一个结点，输入结点的值。VoidCreateBiTree

(BiTree*T){charch;scanf(“%c”&ch);if(ch＝＝’’)

（*T）=NULL;

else{if(!(（*T）=(BiTNode*)malloc(sizeof(BiTNode)))

exit(0);

（*T）->data=ch;//生成根结点

CreateBiTree(&（*T）->lchild);//构造左子树

CreateBiTree(&（*T）>rchild);//构造右子树

}}//CreateBiTree2、统计二叉树中叶子结点的个数算法基本思想:

先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。void

CountLeaf

(BiTreeT,int&count){

if(T){

if

((!T->lchild)&&

(!T->rchild))count++;//对叶子结点计数

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);

}}

3、求二叉树的深度(后序遍历)算法基本思想:

从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。

首先分析二叉树的深度和它的左、右子树深度之间的关系。int

Depth(BiTreeT){//返回二叉树的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}6.3.2线索二叉树

何谓线索二叉树？线索链表的遍历算法如何建立线索链表？一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA指向该线性序列中的“前驱”和“后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”ABCDEFGHK^D^

C^^B

E^线索链表的结点结构

ltag和rtag是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前驱或后继的线索。

lchildLTagdataRTagrchild例如：ABCDEABDCET中序序列：BCAED中序线索二叉树00001111^11^ABCDE0A01B00D11C11E1T中序序列：BCAED带头结点的中序线索二叉树

0

1头结点：ltag=0,lchild指向根结点rtag=1,rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点ABDCET中序序列：BCAED中序线索二叉树00001111^11^二、线索链表的遍历算法:由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。例如:

对中序线索化链表的遍历算法

※中序遍历的第一个结点？

※在中序线索化链表中结点的后继？左子树上处于“最左下”（没有左子树）的结点。若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。voidInOrderTraverse_Thr(BiThrTreeT,

void(*Visit)(TElemTypee))

{p=T->lchild;//p指向根结点

while(p!=T){//空树或遍历结束时，p==T

while(p->LTag==Link)p=p->lchild;//先找到中序遍历起点

if(!Visit(p->data))returnERROR;//访问其左子树为空的结点

while(p->RTag==Thread&&p->rchild!=T)

{p=p->rchild;Visit(p->data);}//访问后继结点

p=p->rchild;//当前结点右域不空或已经找好了后继，则一律从结点的右子树开始重复{}的全部过程

}}//InOrderTraverse_Thr

在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。三、如何建立线索链表？线索二叉树的生成算法目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。注解：为方便添加结点的前驱或后继，需要设置两个指针：

p指针→当前结点之指针；pre指针→前驱结点之指针。技巧：当结点p的左/右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。或者说，当前结点的指针p应当送到前驱结点的空右域中。若p->lchild＝NULL,则{p->Ltag=1;p->lchild＝pre;}//p的前驱结点指针pre存入左空域若pre->rchild＝NULL,则{pre->Rtag＝1;pre->rchild=p;}//p存入其前驱结点pre的右空域void

InThreading(BiThrTreep)

{

if(p){//对以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);

//右子树线索化

}//if}//InThreadingStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//构建中序线索链表

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;

}

returnOK;}//InOrderThreading

6.4树和森林树的三种存储结构一、双亲表示法二、孩子链表表示法三、树的二叉链表(孩子-兄弟）存储表示法ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent一、双亲表示法:

typedefstructPTNode{Elemdata;

intparent;//双亲位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:typedefstruct{PTNodenodes[MAX_TREE_SIZE];

int

r,n;//根结点的位置和结点个数

}PTree;树结构:ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4r=0n=7dataparentfirstchild123456二、孩子链表表示法:-1000224typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子结点结构:

childnextC语言的类型描述:

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子链的头指针

}CTBox;双亲结点结构

datafirstchildtypedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//结点数和根结点的位置

}CTree;树结构:三、树的二叉链表(孩子-兄弟）存储表示法ABCDEFGABCEDFGrootABCEDFG

typedefstructCSNode{Elemdata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree;C语言的类型描述:结点结构:

firstchilddatanextsibling树与二叉树转换ACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应存储存储解释解释将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子树与二叉树的转换将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ

由此，树的各种操作均可对应二叉树的操作来完成。

应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：

左是孩子，右是兄弟。6.6哈夫曼树与

哈夫曼编码

最优树(哈夫曼树)的定义

如何构造最优树

前缀编码哈夫曼编码

一、最优树的定义树的路径长度定义为：

树中每个结点的路径长度之和。

结点的路径长度定义为：

从根结点到该结点的路径上分支的数目。

树的带权路径长度定义为：

树中所有叶子结点的带权路径长度之和

WPL(T)=wklk(对所有叶子结点)。

在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。例如：WPL(T)=72+52+22+42=36WPL(T)=71+52+23+43=35WPL(T)=73+53+42+21=46

根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合

F={T1,T2,…,Tn}，其中每棵二叉树Ti中均只含一个带权值为wi的根结点，其左、右子树为空树；二、如何构造最优树(1)(哈夫曼算法)以二叉树为例：

在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(2)

从F中删去这两棵树，同时加入刚生成的新树；

重复

(2)

和

(3)

两步，直至F中只含一棵树为止。这棵树便是哈夫曼树(3)(4)9例如:已知权值W={5,6,2,9,7}562752769767139527952716671329注意：

①n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。

②哈夫曼树是严格的二叉树，没有度数为1的分支结点。前缀编码

在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。

1.等长编码

这种编码方式的特点:

每个字符的编码长度相同。设字符集只含有4个字符A，B，C，D，用两位二进制表示的编码分别为00，01，10，11。若现在电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点:译码简单且具有唯一性，但编码长度并不是最短的。2.不等长编码

在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位。问题：接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。CDBA111000A:0B:10C:110D:111电文为：ABACCDA发送二进制序列：01001101101110

利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。称为哈夫曼编码哈夫曼编码（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。哈夫曼编码的构造方法：例如：

假设有一个电文字符集中有8个字符，每个字符的使用频率分别为{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，现以此为例设计哈夫曼编码。为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到{5,29,7,8,14,23,3,11}；哈夫曼编码设计如下图：115297814233100011558290001118421900011100010011001111110111111010Weightparentlchildrchild12345678910111213141552978142331101234567W529870000000000000000000000000000000000000000000001423311999178101034151111128191414121313151552942581002101161412130HC0cd01234567123456780011↑start00111111111111111000000001求哈夫曼编码过程的实例:HT数组哈夫曼树的存储结构

用一个大小为2n-1的一维数组来存储哈夫曼树中的结点，其存储结构为：

typedefstruct{

//结点类型

intweight；

//权值，不妨设权值均大于零

intlchild，rchild，parent；

//左右孩子及双亲指针

}HTNode，*HuffmanTree;//动态分配数组存储哈夫曼树Typedefchar**Huffmancode;//动态分配数组存储哈夫曼编码表哈夫曼编码的存储结构

if(n<=1)return;

m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用

求哈夫曼编码的算法:for(p=HT+1,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0}

for(;i<=m;++i,++p)

*p={0,0,0,0}

for(i=n+1