数据结构(C／C++描述)第6章 树与二叉树

第6章树和二叉树6.1树的定义及其存储结构6.2

二叉树6.3

遍历二叉树和线索化二叉树6.4

树、森林和二叉树的关系6.5哈夫曼树及其应用

6.1树的定义及其存储结构数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。

数据关系R：6.1.1树的定义及基本术语ABCDEFGHIJMKLA()T1T3T2树根例如:B(E,F(K,L)),

C(G),

D(H,I,J(M))(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。基本术语结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：孩子结点、双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMF对比树型结构和线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)6.1.2树的存储结构一、双亲数组表示法二、孩子链表表示法三、树的二叉链表(孩子-兄弟）存储表示法ABCDEFGr=0n=70

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、双亲表示法:

typedefstructPTNode

{TElemTypedata;

int

parent;//双亲位置域}PTNode;

dataparent#defineMaxTreeSize100结点结构:C语言的类型描述:typedefstruct{

PTNode

nodes[MaxTreeSize];

int

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

}

PTree;树结构:r=0n=7dataparentfirstchildABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4645123二、孩子链表表示法:-1000224typedefstructCTNode

{

int

child;//数组下标

structCTNode

*nextchild;}*ChildPtr;孩子结点结构:

childnextchildC语言的类型描述:

typedefstruct{TElemTypedata;//结点的值ChildPtrfirstchild;//孩子链的头指针

}

CTBox;双亲结点结构

datafirstchildtypedefstruct{

CTBox

nodes[MaxTreeSize];//双亲结点结构数组

int

n,r;

//结点数和根结点的位置}

CTree;树结构:ABCDEFGrootABCEDFGABCEDFG

三、树的二叉链表(孩子-兄弟）存储表示法root森林的二叉链表表示typedefstruct

CSNode{

TElemType

data;

struct

CSNode

*firstchild,*nextsibling;}

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

firstchilddata

nextsibling6.2

二叉树6.2.1

二叉树的定义

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

二叉树的性质

性质1：

在二叉树的第i层上至多有2i-1

个结点。(i≥1)用归纳法证明：

归纳基：

归纳假设：

归纳证明：i=1

层时，只有一个根结点，

2i-1

=20

=1；假设对所有的j，1≤j

i，命题成立;二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-2

2=2i-1

。性质2：

深度为k的二叉树上至多含2k-1

个结点（k≥1）证明：基于上一条性质，深度为k的二叉树上的结点数至多为

20+21+

+2k-1=2k-1

性质3：

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

个度为

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

+2n2而b=n-1=n0+n1+n2-1由此，n0=n2

+1两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；

A

E

D

C

B

G

A

E

D

C

B(a)(c)(b)、(b)完全二叉树(c)不是完全二叉树

A

G

F

E

D

C

B

性质4：

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

2k即k-1

≤log2

n<k

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

+1性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为

i

的结点：

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

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

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

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

否则，编号为2i+1

的结点为其右孩子结点。6.2.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示#define

MaxTreeSize100

//二叉树的最大结点数typedefTElemTypeSqBiTree[MaxTreeSize

+1];

//0号单元存储根结点SqBiTreebt;一、二叉树的顺序存储表示顺序存储结构:按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。T[0]一般不用讨论：不是完全二叉树怎么办？答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺点：①浪费空间；②插入、删除不便

例如:

ABDCEF

1234567891011121314ABCDEF2511437相应完全二叉树

n=15二、二叉树的链式存储表示1.二叉链表2．三叉链表3．双亲链表4．线索链表ADEBCFrootlchilddatarchild结点结构:1.二叉链表typedefstruct

BiTNode

{

//结点结构TElemTypedata;

structBiTNode*lchild,*rchild;

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

lchilddatarchild结点结构:

typedefstruct

TriTNode//结点结构

{TElemTypedata;

struct

TriTNode

*lchild,*rchild;

//左右孩子指针

structTriTNode

*parent;//双亲指针

}

TriTNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:6.3遍历二叉树和线索化二叉树一、遍历的概念二、先左后右的遍历算法三、算法的递归描述四、中序遍历算法的非递归描述五、遍历算法的应用举例6.3.1二叉树的遍历

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

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

每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。对“二叉树”而言，可以有三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历。遍历二叉树（TraversingBinaryTree）遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

遍历方法——牢记一种约定，对每个结点的查看都是“先左后右”。二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法根左子树右子树根根根根根

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

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

若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序遍历算法（LRD）ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A三、算法的递归描述void

PreOrderTraverse(BiTreeT){//

先序遍历二叉树

if(T){

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

PreOrderTraverse

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

PreOrderTraverse

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

}}void

InOrderTraverse(BiTreeT){//

中序遍历二叉树

if(T){

①InOrderTraverse(T->lchild);//遍历左子树

②VisitElement

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

③InOrderTraverse

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

}}void

PostOrderTraverse

(BiTreeT){//

后序遍历二叉树

if(T){

①PostOrderTraverse(T->lchild);//遍历左子树

②PostOrderTraverse(T->rchild);//遍历右子树

③VisitElement(T->data);//访问根结点

}}对遍历的分析：1.从前面的三种遍历算法可以知道：如果将visit语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O(n)

//每个结点只访问一次空间效率:O(n)

//栈占用的最大辅助空间（精确值：树深为k的递归遍历需要k+1个辅助单元！）对遍历的分析：从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历中序序列：DBFEGACint

InOrderTraverse(BiTreeT){BiTNode*p;InitStack(S);p=T;

while(p||!StackEmpty(S)){if

(p) {

Push(S,p);p=p->lchild;} //根结点进栈，遍历左子树else

{Pop(S,p);//根结点退栈，访问根结点，遍历右子树VisitElement(p->data);p=p->rchild;}//else}//whilereturn

OK;}

//InOrderTraverse四、中序遍历算法的非递归描述五、遍历算法的应用举例1、统计二叉树中叶子结点的个数2、建立二叉树的存储结构1、统计二叉树中叶子结点的个数算法基本思想:

先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”

的操作改为:若是叶子，则计数器增1。voidCountLeaf(BiTreeT,int&count){//先序遍历二叉树，计算叶子结点个数if(T){if((!T->lchild)&&(!T->rchild))

count++;//对叶子结点计数

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf2、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法

以字符串的形式“根左子树

右子树”定义一棵二叉树例如:以空白字符“”表示ABCDAB

C

D

空树只含一个根结点的二叉树A以字符串“A”表示以下列字符串表示intCreateBiTree(BiTree&T)

{//按先序序列构造二叉链表表示的二叉树Tscanf(&ch);if(ch=='')T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根结点

CreateBiTree(T->lchild);//构造左子树

CreateBiTree(T->rchild);//构造右子树}

returnOK;//递归出口}//CreateBiTreeAB

C

D

ABCD上页算法执行过程举例如下:ATBCD^^^^^①scanf(&ch);②if(ch=='')T=NULL;

else

{③

if(!(T=newBiTNode))

exit(OVERFLOW);④

T->data=ch;⑤

CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnok//递归出口

仅知二叉树的先序序列“abcdefg”

不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树

如果同时已知二叉树的中序序列“cbdaegf”,则会如何？

二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.3.2

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

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA

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

C^^B

E^对线索链表中结点的约定：

在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针Link=0”；否则Lchild域的指针指向其“前驱”，且左标志的值为“线索Thread=1”。若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针Link=0”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索Thread=1”。

如此定义的二叉树的存储结构称作“线索链表”typedefstruct

BiThrNode{

TElemTypedata;

struct

BiThrNode

*lchild,*rchild;

//左右指针

PointerThr

LTag,RTag;

//左右标志}

BiThrNode,*BiThrTree;线索链表的类型描述：

typedef

enum

{

Link,Thread

}PointerThr;

//Link==0:指针，Thread==1:线索规定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)。为了避免混淆，增加两个标志域，如下图所示：lchildLTagdataRTagrchild约定:当Tag域为0时,表示正常情况;当Tag域为1时,表示线索情况.有关线索二叉树的几个术语：

线索链表：

用前页结点结构所构成的二叉链表

线索：指向结点前驱和后继的指针

线索二叉树：加上线索的二叉树（图形式样）

线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程注：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。ABCGEIDHFroot悬空？悬空？解：该二叉树中序遍历结果为:

H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：例2：画出以下二叉树对应的中序线索二叉树。为避免悬空态，应增设一个头结点对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0--root0二、线索链表的遍历算法由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。对中序线索化链表的遍历算法

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

※在中序线索化链表中结点的后继？

左子树上处于“最左下”（没有左子树）的结点若无右子树，则为后继线索所指结点否则为对其右子树进行中序遍历时访问的第一个结点void

InOrderTraverse_Thr(BiThrTreeT){//线索二叉树的中序遍历算法p=T->lchild;//p指向根结点

while(p!=T)

{

//空树或遍历结束时，p==Twhile(p->LTag==Link)p=p->lchild;//查找第一个结点－最左下

if(!visit(p->data))returnERROR;//若起点值为空则出错告警while(p->RTag==Thread&&p->rchild!=T)

{//若有后继标志，则直接提取p->rchild中线索并访问p=p->rchild;Visit(p->data);//访问后继结点

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

}}在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。三、如何建立线索链表？对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0--root0void

InThreading(BiThrTreep)

{

if(p){//对以p为根的非空二叉树进行线索化

InThreading(p->lchild);

//左子树线索化

if(!p->lchild)//建前驱线索{p->LTag=1;p->lchild=pre;}

if(!pre->rchild)//建后继线索{pre->RTag=1;pre->rchild=p;}

pre=p;//保持pre指向p的前驱

InThreading(p->rchild);

//右子树线索化

}//if}//InThreadingStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//构建中序线索链表if(!(Thrt=newBiThrNode))exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加头结点returnOK;}//InOrderThreading……if(!T)

Thrt->lchild=Thrt;//若二叉树空，左指针回指else{Thrt->lchild=T;

pre=Thrt;//设置前趋指针初值

InThreading(T);//调用算法6.7

pre->rchild=Thrt;

//处理最后一个结点

pre->RTag=Thread;Thrt->rchild=pre;

}

6.4树、森林和二叉树的关系6.4.1树、森林和二叉树的转换设森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉树

B=(LBT,Node(root),RBT);由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ;由ROOT(T1)对应得到Node(root);否则，由(t11,t12,…,t1m)对应得到LBT;由(T2,T3,…,Tn)对应得到RBT。T1T11,T12,…,T1mT2,…,TnLBTRBTroot转换步骤：step1:将树中同一结点的兄弟相连;step2:保留结点的最左孩子连线，删除其它孩子连线；step3:将同一孩子的连线绕左孩子顺时针旋转45度角。加线抹线旋转讨论1：树如何转为二叉树？方法：加线—抹线—旋转

abeidfhgc树转二叉树举例：abeidfhgc兄弟相连长兄为父孩子靠左根结点肯定没有右孩子！讨论2：二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！然后逆时针旋转45度。

abeidfhgc法1：①各森林先各自转为二叉树；②依次连到前一个二叉树的右子树上。讨论3：森林如何转为二叉树？法2：

森林直接变兄弟，再转为二叉树即F={T1,T2,…,Tm}B={root,LB,RB}ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林转二叉树举例：（法2）兄弟相连长兄为父孩子靠左头根为根

A讨论4：二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟

ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B={root,LB,RB}F={T1,T2,…,Tm}

由此，树和森林的各种操作均可与二叉树的各种操作相对应。

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

左是孩子，右是兄弟6.4.2树和森林的遍历一、树的遍历二、森林的遍历三、树的遍历的应用树的遍历可有3条搜索路径:按层次遍历:先根(次序)遍历:后根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。

层次遍历时顶点的访问次序：ABCDEFGHIJK

先根遍历时顶点的访问次序：ABEF

C

DGHIJK后根遍历时顶点的访问次序：EFB

C

IJKHG

DAABCD

EFGHIJK

BCDEFGHIJK1。森林中第一棵树的根结点；2。森林中第一棵树的子树森林；3。森林中其它树构成的森林。可以分解成3部分：森林

若森林不空，则访问森林中第一棵树的根结点;先序遍历森林中第一棵树的子树森林;先序遍历森林中（除第一棵树之外）其余树构成的森林。先序遍历:森林的遍历即：依次从左至右对森林中的每一棵树进行先根遍历。

BCDEFGHIJK森林