第6章 二叉树和树

1数据结构及应用算法教程(修订版)配套课件2第6章二叉树和树

前面的章节主要讨论的是线性结构，二叉树和树属于非线性的结构。遍历非线性结构比线性结构要麻烦。二叉树及树的遍历技术是本章各种算法的核心，而且大多是以递归的形式表现的，阅读和编写递归算法是学习本章的难点。讲授本章课程大约需8课时。3

树结构的特点及基本术语

6.1二叉树

6.2二叉树的遍历

6.3树和森林

6.4树的应用4树结构的特点及基本术语

5线性结构树型结构第一个数据元素

(无前驱)

根结点

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

(无后继)多个叶子结点

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

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL结点的层次:假设根结点的层次为1,第l

层的结点的子树根结点的层次为l+1树的深度：树中叶子结点所在的最大层次层次-深度-高度，86.1二叉树一、二叉树的定义和基本术语二、二叉树的几个基本性质三、二叉树的存储结构9一、二叉树的定义和基本术语

10

二叉树的定义

二叉树是n（n≥0）个元素的有限集，它或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。根结点左子树右子树ABCDEFGHKLB11二叉树可以表现出五种基本形态：空树N只含根结点右子树为空树NL左子树为空树NR左右子树均不为空树NLR12

二叉树的基本操作：

查找类的操作

插入类的操作

删除类的操作13Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T);InOrderTraverse(T);PostOrderTraverse(T);LevelOrderTraverse(T);查找类的操作：14InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入类的操作：15ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);删除类的操作：16二、二叉树的几个基本性质17

性质1：

在二叉树的第i

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

归纳基：

归纳假设：

归纳证明：i=1

层时，只有一个根结点：

2i-1=20=1；假设对所有的j，1≤j

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

。18

性质2：

深度为k

的二叉树上至多含

2k-1

个结点（k≥1）。证明：

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

20+21+

+2k-1=2k-1

。19

性质3：

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

个度为

2

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

而b=n-1=n0+n1+n2-1由此，n0=n2+1。20两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。abcdefghij12345678910111213141521

性质4：

具有n

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

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

即k-1≤log2n<k

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

+1。22

性质5

：

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

至n

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

的结点：

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

i/2的结点为其双亲结点；

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

否则，编号为

2i的结点为其左孩子结点；

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

否则，编号为2i+1的结点为其右孩子结点。23三、二叉树的存储结构

二叉树顺序存储表示二叉树链式存储表示24#defineMAX_TREE_SIZE100//二叉树的最大结点数typedef

TElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;

二叉树顺序存储表示25例如:

ABDCEF012345678910111213ABCDEF140132626

二叉树链式存储表示1.二叉链表2．三叉链表3．线索链表27ADEBCFroot结点结构:1.二叉链表lchilddatarchild28typedefstruct

BiTNode

{//结点结构

TElemTypedata;

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

lchilddatarchild结点结构:30

typedefstruct

TriTNode

{

//结点结构

TElemTypedata;

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

struct

TriTNode

*parent;//双亲指针

}TriTNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:31（请见后面的线索二叉树）3．线索链表326.2二叉树遍历一、问题的提出二、遍历算法描述三、遍历算法应用举例四、线索二叉树33

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

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

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

对“二叉树”而言，可以有三条搜索路径：

1．先上后下的按层次遍历；

2．先左（子树）后右（子树）的遍历；

3．先右（子树）后左（子树）的遍历。36先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法37若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：ABCDFGEH38若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：ABCDFGEH39若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：ABCDFGEH40ABCDEFGHA前序遍历：ABCDEFGHBDCEGHFB中序遍历：DAGEHCFD后序遍历：BGHEFCA二叉树遍历的输出顺序示例演示41NULLNULLNULLNULLNULLNULLNULLNULLNULLABCDEFGH先序遍历：中序遍历：后序遍历：ABDBDCEGHFDAGEHCFBGHEFCA二叉树遍历过程的示例演示42二、遍历算法描述

先序（前序）遍历二叉树的递归算法

中序遍历二叉树的递归算法

后序遍历二叉树的递归算法43先序遍历二叉树的递归算法voidpreorder(BiTreeT){

//

先序遍历二叉树

if(T==NULL)exit；

{

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

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

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

}}44void

inorder(BiTreeT）{

//

中序遍历二叉树

if(T==NULL)exit；{

inorder(T->lchild);

//遍历左子树

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

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

}}中序遍历二叉树的递归算法45void

postorder(BiTreeT）

{

//

后序遍历二叉树

if(T==NULL)

{

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

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

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

}}后序遍历二叉树的递归算法46三、遍历算法应用举例1、统计二叉树中叶子结点的个数

(先序遍历)2、求二叉树的深度(后序遍历)3、复制二叉树(后序遍历)4、建立二叉树的存储结构471、统计二叉树中叶子结点的个数算法基本思想:

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

if(T){

if

((!T->lchild)&&(!T->rchild))count++;

//对叶子结点计数

CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);

}

//if}

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

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

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

Depth(BiTreeT

){//返回二叉树的深度

if

(!T)depthval=0;else{

depthLeft=Depth(T->lchild);

depthRight=Depth(T->rchild);

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

}

return

depthval;}513、复制二叉树(后序遍历)核心操作：生成一个根结点,并链接左右子树根元素T根元素NEWT递归操作：完成左右子树的复制52BiTNode*CopyTree(BiTNode*T)

{

if

(!T)returnNULL;

if(T->lchild)

newlptr=CopyTree(T->lchild);//复制左子树

elsenewlptr=NULL;

if

(T->rchild)

newrptr=CopyTree(T->rchild);//复制右子树

elsenewrptr=NULL;

newT=GetTreeNode(T->data,newlptr,

newrptr);

return

newT;}

//CopyTree53BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){

if

(!(T=newBiTNode))

exit(1);T->data=item;T->lchild=lptr;T->rchild=rptr;

returnT;}

生成一个二叉树的结点的操作算法：(其数据域为item,左指针域为lptr,右指针域为rptr)54ABCDEFGHK^D^C^^H^^K^G^F^E^A例如：下列二叉树的复制过程如下：^BnewTT554、建立二叉树的存储结构

不同的定义方法相应有不同的存储结构的建立算法。以下建立以二叉链表表示的存储结构。从输入的字符串建立二叉树由前序和中序的序列建立二叉树56

以字符串的形式

根

左子树

右子树定义一棵二叉树例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空树只含一个根结点的二叉树A以字符串“A”表示以下列字符串表示57voidCreateBiTree(BiTree&T){cin>>ch;

if(ch=='')T=NULL;

else{

if

(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根结点

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

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

}}//CreateBiTree58AB

C

D

ABCD上页算法执行过程举例如下：ATBCD^^^^^59

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

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

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

二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根60abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列61preinopsps+n-1isis+n-1pre[ps]kps+1k-isps+1+(k-is)k+1n-(k-is)-1子树序列下标位置的确定62void

CrtBT(BiTree&T,charpre[],charino[],

intps,intis,intn){

//已知pre[ps..ps+n-1]为二叉树的先序序列，//ins[is..is+n-1]为二叉树的中序序列，//本算法由此两个序列构造二叉链表

if

(n==0)T=NULL;

else{k=Search(ino,pre[ps]);//在中序序列中查询

if(k==-1)T=NULL;

else{}//递归程序段

}}//CrtBT……

63T=newBiTNode;T->data=pre[ps];if(k==is)T->Lchild=NULL;else

CrtBT(T->Lchild,

pre[],ino[],

ps+1,is,k-is

);if(k==is+n-1)T->Rchild=NULL;else

CrtBT(T->Rchild,

pre[],ino[],

ps+1+(k-is),k+1,n-(k-is)-1);递归语句程序段：64四、线索二叉树一、何谓线索二叉树？二、线索链表的遍历算法三、如何建立线索链表？65一、何谓线索二叉树？

遍历二叉树的结果是，求得结点的一个线性序列，例如:先序序列:

ABDEGHCFIJ中序序列:

DBGEHACIJF后序序列:

DGHEBJIFCA66

遍历引起的思考：

遍历二叉树把非线性结构以序列的形式加以“线性化”了，那么所得序列信息可否长期利用？信息保持可否尽量少占用额外的存储空间？是否能否形成一般化的方法？

处理办法：

在遍历时，串联起前驱、后继的关系链，以备后期的再利用。67

指向该线性序列中的“前驱”和“后继”的指针，称作“线索”DBG

E

H

A

CIJF

以中序为例,看结点H的前驱线索和后继线索ABCFDGEHIJ的前驱线索H的后继线索H68

与其相应的二叉树，称作“线索二叉树”

包含“线索”的存储结构，称作“线索链表”

按“序”来讲，可分成：“先序线索二叉树”、“中序线索二叉树”和“后序线索二叉树”69typedefstruct

BiThrNode

{

TElemTypedata;

struct

BiThrNode*lchild,rchild;

struct

BiThrNode*pred,succ;

//前驱、后继线索}

BiThrNode,*BiThrTree;线索二叉树的类型定义：70HABCDEGHFIJT中序线索化二叉树示例71DBGEHACIJF线索关系表现为双向循环链表查找前驱和后继变得异常容易72

遍历带有线索的二叉树，既无需重新递归遍历，也无需栈的协助，只进行相当“线性结构”的寻访即可，而且可正反双向进行。二、线索链表的遍历算法:73void

InOrder(BiThrTreeH,void(*visit)(BiTree))

{

//H为指向中序线索链表中头结点的指针

p=H->succ;

while(p!=H)

{

visit(p);p=p->succ;

}}74三、如何建立线索链表？

建立中序线索化的过程，是在中序遍历的过程中串联起前驱和后继的线索指针链。（线索化过程参照教科书）756.3树和森林一、树和森林的定义二、树和森林的存储结构三、树和森林的遍历76一、树和森林的定义

77

树的定义：树是n（n≥0）个元素的有限集D，若D为空集，则为空树。否则：

(1)在D中存在唯一的称为根的数据元素root；

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

查找类的操作

插入类的操作

删除类的操作79Root(T)//求树的根结点查找类的操作：Value(T,cur_e)//求当前结点的元素值

Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T)//遍历80InitTree(&T)//初始化置空树

插入类的操作：CreateTree(&T,definition)

//按定义构造树Assign(T,cur_e,value)

//给当前结点赋值InsertChild(&T,&p,i,c)

//将以c为根的树插入为结点p的第i棵子树81

ClearTree(&T)//将树清空

删除类的操作：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)

//删除结点p的第i棵子树82ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根例如:83(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。84任何一棵非空树是一个二元组

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

F

被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootCGDHIJMFBEFKL85二、树和森林的存储结构1.双亲表示法2.孩子链表表示法3.树的二叉链表(孩子-兄弟）存储表示法86ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=6dataparent1.双亲表示法:87

typedefstructPTNode{Elemdata;

intparent;//双亲位置域

}PTNode;

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

intr,n;//根结点的位置和结点个数}PTree;树结构:89r=0n=6data,firstchild0

A

-11

B

02

C

03

D

04

E

25

F

26

G

56451232.孩子链表表示法:ABCDEFG90typedefstruct

CTNode{

intchild;

struct

CTNode*next;}*ChildPtr;孩子结点结构:

childnextC语言的类型描述:91

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

}CTBox;双亲结点结构

datafirstchild92typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

int

n,r;//结点数和根结点的位置}CTree;树结构:93ABCEDFG

3.树的二叉链表(孩子-兄弟）存储表示法ABCDEFGrootABCDEFG94typedefstructCSNode{Elemdata;

structCSNode

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

firstchilddatanextsibling

树—二叉树

将一棵树转换为二叉树的方法是：

(1)树中所有相邻兄弟之间加一条连线。

(2)对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。(删线）

(3)以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。树做这样的转换所构成的二叉树是唯一的。图

树到二叉树的转换图

树与二叉树的对应2.森林转换为二叉树森林是若干棵树的集合。树可以转换为二叉树，森林同样也可以转换为二叉树。因此，森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下：（1）将森林中的每棵树转换成相应的二叉树。（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。图

森林转换为二叉树的过程100

森林和二叉树的对应关系设森林

F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉树

B=(LBT,Node(root),RBT);101由森林转换成二叉树的转换规则为:若

F=Φ，则

B=Φ；否则，

由

ROOT(T1)

对应得到

Node(root)；

由

(t11,t12,…,t1m)

对应得到

LBT；

由

(T2,T3,…,Tn)

对应得到

RBT。102由二叉树转换为森林的转换规则为：若B=Φ，则F=Φ；否则，由Node(root)

对应得到ROOT(T1

)；由LBT

对应得到(t11,t12,…，t1m)；由RBT

对应得到(T2,T3,…,Tn)。103

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

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

左是孩子，右是兄弟。104

三、树和森林的遍历

1.树的遍历2.森林的遍历3.树的遍历的应用1051.树的遍历(可有三条搜索路径):按层次遍历:先根(次序)遍历:后根(次序)遍历:

若树不空，则先访问根结点，然后依次先根遍历各棵子树。

若树不空，则先依次后根遍历各棵子树，然后访问根结点。

若树不空，则自上而下自左至右访问树中每个结点。106ABCDEFGHIJK

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

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

层次遍历时顶点的访问次序：ABCDEFGHIJK1072．森林中第一棵树的子树森林；1．森林中第一棵树的根结点；

BCDEFGHIJK3．森林中其它树构成的森林。森林由三部分构成：2.森林的遍历108

先序遍历

即：依次从左至右对森林中的每一棵树进行先根遍历。

若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。109中序遍历

若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其

余树构成的森林。

即：依次从左至右对森林中的每一棵树进行后根遍历。110

树的遍历和二叉树遍历的对应关系？先根遍历后根遍历树二叉树森林先序遍历先序遍历中序遍历中序遍历111(设树的存储结构为孩子兄弟链表)typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;

求树的深度

输出树中所有从根到叶子的路径

建树的存储结构3.树的遍历的应用112intTreeDepth(CSTreeT){

if(!T)return0;

else{h1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);

}}//TreeDepthreturn(max(h1+1,h2));

求树的深度的算法：113ABCDABCD求树深算法的理解(max(h1+1,h2))的图解

114

输出树中所有从根到叶子的路径的算法:例如：对左图所示的树，其输出结果应为：ABEABFACADGHIADGHJADGHK

ABCDEFGHIJK115void

AllPath(BitreeT,Stack&S)

{

if

(T)

{

Push(S,T->data);if(!T->Lchild&&!T->Rchild)PrintStack(S);else{

AllPath(T->Lchild,S);AllPath(T->Rchild,S);

}

Pop(S);

}//

if(T)}

//AllPath//输出二叉树上从根到所有叶子结点的路径116ABCDEFGHABA-B-D-FDFGA-B-D-GCEHA-C-E-H输出二叉树上从根到所有叶子结点的路径演示117ABCDEFGHIJKABEABFACADGHIADGHJADGHK输出树中所有从根到叶子的路径ǾǾǾǾǾǾ如何判定叶子？118void

OutPath(BitreeT,Stack&S){

while(!T){

Push(S,T->data);

if(!T->firstchild)Printstack(s);

else

OutPath(T->firstchild,s);

Pop(S);

T=T->nextsibling;

}

//while}

//OutPath//输出森林中所有从根到叶的路径119

建树的存储结构的算法:

和二叉树类似，不同的定义相应有不同的算法。

假设以二元组(F，C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。120ABCDEFG例如:对下列所示树的输入序列应为:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCD(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)

算法中需要一个队列保存已建好的结点的指针。121voidCreatTree(CSTree&T){T=NULL;

for(scanf(&fa,&ch);ch!=#;

scanf(&fa,&ch);)

{ p=GetTreeNode(ch);//创建结点

EnQueue(Q,p);//指针入队列

if(fa==

#)T=p;//所建为根结点

else{ }

//非根结点的情况

}

//for}

//CreateTree

……

122GetHead(Q,s);//取队列头元素(指针值)while(s->data!=fa){

//查询双亲结点

DeQueue(Q,s);GetHead(Q,s);}

if(!(s->firstchild))

{s->firstchild=p;r=p;}

//链接第一个孩子结点else

{r->nextsibling=p;r=p;

}

//链接其它孩子结点

非根结点的情况的代码段：123

6.4树的应用

一、堆排序的实现二、二叉排序树三、赫夫曼树及其应用124一、堆排序的实现125堆是满足下列性质的数列{r1,r2,…，rn}：或堆的定义:{12,36,27,65,40,34,98,81,73,55,49}例如:是小顶堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小顶堆)(大顶堆)复习第4章排序126rir2ir2i+1

若将该数列视作完全二叉树，则r2i

是ri

的左孩子;r2i+1

是

ri

的右孩子。1236276549817355403498例如:是堆14不127如何“建堆”？两个问题:如何“筛选”？定义堆类型为:typedef

SqListHeapType;//堆采用顺序表表示之HeapAdjust(.,.,.);12812998814973556412362740例如:是大顶堆12但在98

和12

进行互换之后，它就不是堆了因此，需要对它进行“筛选”98128173641298比较比较130void

HeapAdjust(RcdType&R[],int

s,int

m){//已知R[s..m]中记录的关键字除R[s]之外均

//满足堆的特征，本函数自上而下调整R[s]的

//关键字，使R[s..m]也成为一个大顶堆}//HeapAdjustrc=R[s];//暂存R[s]for

(j=2*s;j<=m;j*=2

){//j初值指向左孩子

自上而下的筛选过程;}R[s]=rc;

//将调整前的堆顶记录插入到s位置131if(rc.key>=R[j].key)break;//再作“根”和“子树根”之间的比较，

//若“>=”成立，则说明已找到rc的插

//入位置s，不需要继续往下调整R[s]=R[j];s=j;

//否则记录上移，尚需继续往下调整if(j<m

&&R[j].key<R[j+1].key)++j;//左/右“子树根”之间先进行相互比较

//令j指示关键字较大记录的位置自上而下的筛选过程的代码段：132

建堆是一个从下往上进行“筛选”的反复过程40554973816436122798例如:排序之前的关键字序列为123681734998817355

现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。98494064361227133voidHeapSort(HeapType&H){

//对顺序表H进行堆排序。}

//HeapSortfor

(i=H.length/2;i>0;--i)

//建大顶堆

HeapAdjust(H.r,i,H.length);

for(i=H.length;i>1;--i)

{//调整堆来实现排序

H.r[1]←→H.r[i];

//将堆顶记录和当前未经排序子序列

//H.r[1..i]中最后一个记录相互交换

HeapAdjust(H.r,1,i-1);

//对H.r[1]进行筛选

}13412345678910405549731227988164363612738181559849557340984049

堆排序的逻辑结构是一棵完全二叉树，而实现的空间则是顺序表。以数据模型演示数据在顺序空间的动态变化。初始堆的建立过程：初始堆的建立过程有比较大的消耗，可达4n135堆排序第一趟：1234567891098814973362740556412129881127312641281堆排序第二趟：123456789108173496436274055121298128112731264125573堆排序第三趟：1234567891073644955362740128112988173121264125564可以看出，每趟的调整只牵涉少量的数据……

有序段136堆排序的时间复杂度分析(建堆+

n-1

次调整)：

以后的每次调整，耗费将显著减少。因为这样调整所耗用的比较操作次数都不超过堆的树深，是一种消耗很少的局部调整。

初始堆的建立过程:O(n)

建成深度为

h=(log2n+1)的堆,需要调整n-1次，总共进行的关键字比较的次数不超过

2*(log2(n-1)+log2(n-2)+

…+log22)<2n(log2n)

因此，堆排序的时间复杂度为O(nlogn)137二、二叉排序树

138（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1．二叉排序的定义：

二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；139503080209010854035252388例如:是二叉排序树。66不140（49，38，65，76，49，13，27，52）4938657649132752构造二叉排序树

构建二叉排序树的过程，是一个从空树起不断插入结点的过程。每插入一个结点都应保证遵从二叉排序树的定义。141（，，，，，，，）1327384949526576（49，38，65，76，49，13，27，52）原始序列数据4938657649132752构造的二叉排序树中序遍历二叉排序树

如果中序遍历二叉排序树，所得序列将是有序的，即实现了对原始数据的排序，二叉排序树即由此得名。142

有关二叉排序树更详细的讨论及算法，请见第8章查找表的二叉查找树一节143三、赫夫曼树及其应用

（哈夫曼树）最优树的定义如何构造最优树前缀编码压缩的本质就是--赫夫曼树abaabaabadbcaabcabadababa计算机内部：ASCII码，定长编码；8bit-一个字节，共256个字符；（汉字-双字节表示一个汉字，共6万字符，康熙字典多于这个；）25*8=200bit,144哈夫曼编码：非定长编码原则：根据如字符出现频率高，则其编码越短。在军事情报中，根据截留的代码，分析每串字符出现的频率，分析可能是代表什么文字？慢慢凑成一句话，就能找出每个字的代码是什么。因为说话的频率难以更改：比如我，的之类的。145

abaabaabadbcaabcabadababa等长编码：总共才四个字符，等长编码：都用两个bit表示，2*25=50bit用哈夫曼树可以更省空间跟时间计数：统计每个字符出现的次数a：13次---0；b：8次---10；c:2次----110，d：2次----111；13*1+8*2+2*3+2*3=45bit在军事上，就可能取得时间上的胜利。146如何获得不等长的编码-建立哈夫曼树来进行编码---二叉树的应用哈夫曼编码的实质就是为了压缩，那如何译码呢？147问题：如何获得哈夫曼编码-----如何解出实际内容（字符）：译码哈夫曼法--哈夫曼树-输入一串字符，计算每个字符出现频率--哈夫曼树（最优二叉树）-哈夫曼编码-实现压缩（输出编码序列）编码过程-哈夫曼树（解压缩）输出字符序列：译码过程什么是哈夫曼树----最优二叉树？148149

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

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

结点的路径长度定义为：

从根结点到该结点的路径上

分支的数目。150

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

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

含n个叶子结点、每个叶子结点带权为w，必存在一棵其带权路径长度取最小值的二叉树，称为“最优二叉树”或者哈夫曼树PL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954152

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

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

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

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

重复(2)

和(3)

两步，直至F中只含一棵树为止。(3)(4)1559例如:已知权值W={

5,6,2,9,7

}5627527697671395271566713952795271667132900001111000110110111157

指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。前缀编码

利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。158出现频度:5,6,2,9,7编码:

101,00,100,11,01字母集:

s,t,a,e,i电文:eat编码:eat111000025701100101911160167130100012901tiase译电文:eat

符合前缀编码规则才能按唯一性进行译码问题：如何获得哈夫曼编码-----如何解出实际内容（字符）：译码哈夫曼法--哈夫曼树-输入一串字符，计算每个字符出现频率--哈夫曼树（最优二叉树）-哈夫曼编码-实现压缩（输出编码序列）编码过程-哈夫曼树（解压缩）输出字符序列：译码过程什么是哈夫曼树----最优二叉树？159哈夫曼算法：就是找到最优二叉树，就是构造最优二叉树的过程，WPL总和最小。哈夫曼算法：输入：n个带权值的字符---将其看成H[]数组输出：最优二叉树就是哈夫曼树。160算法流程（步骤）：1、从H[]中选择两个权值最小的字符x,y;2、利用x，y构建一棵二叉树Z,权值为xw+yw；3、将新产生的二叉树Z,加入到集合中，同时将x，y删除；4、不断重复1、2、3，直到H[]中只剩下一个元素为止。161哈夫曼树----哈夫曼编码？规则：1、沿着哈树分支，左边为0，右边为1；2、每个叶子结点的路径：从根—该叶子结点所形成的01代码串---就为该叶子结点对应字符编码。162压缩---编码字符----01串解压缩—译码01串—字符1、从哈树的根开始，遇0走左分支，遇1走右分支，直至叶子结点----输出相应字符；2、不断重复1，直到01串结束。163难点：哈夫曼树的构造

采用技巧：用数组表示二叉树。Typedefstructleafnode{intweight;权值intleft;intright;intparent;}HNODEHNODEH[];

}164Parent，left，right表示该结点父结点，孩子结点的下标Parent,left,right=-1,表示无父结点，无左右孩子准备：建立H[]数组表示叶子结点，其父结点、左右孩子均为-1；weight，data值求哈夫曼树函数Huffman（HNODEH[],intn）（n为叶子结点数）165Huffman（HNODEH[],intn）Count=n；While(count>1){If(H[].parent=-1)Selecttwomin(H,n,&index1,&index2);//找当前数组中权值最小的两个数,其下标用Index1，index2表示Index=creatBiTree(H,n,index1,index2)//两结点建立二叉树，新生成的结点为indexDelecttwomin（H，n，index1，index2；）Count--;}166Index=creatBiTree(H,n,index1,index2){H[n]为新结点，H[0—n-1]为放原叶子结点值H[n].left=index1;H[n].right=index2;H[n].parent=-1;H[n].weight=H[index1].weight+H[index2].weightH[index1].parent=n;H[index2].parent=n;}技巧：当parent==-1，表示已经用过该结点。167作业：编码：输入：一串英文txt（都为小写，不考虑空格）输出：该txt的01压缩串（编码）译码：输入：01串输出：该01串表示的字符串（解压缩译码）168输入：一串英文txt（都为小写，不考虑空格）---1、计数（求权值weight）2、建立哈树（数组H[]）3、哈编码：txt的编码（01串）4、译码169输入：一串英文txt（都为小写，不考虑空格）1、计数—求权值：每个字母出现的频率.intA[26];//放每个字符出现的次数chardoc[];//英文txtinti=1;

while(i<n){A[doc[i]-’a’]++;i++;}//后两条语句可用A[doc[i++]-’a’]++;A[doc[i]-’a’]++;//-’a’得到该字符在A[]中的下标位置，对其++运算，等于累计该字符在txt中出现的次数，也就是它的weight。1702、建立哈树（H[]）:哈夫曼算法计数后，得到每个字母的权值weight，就可以求得哈夫曼树---将此树用H[]数组表示。(程序见前面)1713、哈编码：txt的编码（01串）输出每个叶子结点（每个字母）的编码。算法思路：1、从哈树根开始，沿着哈树分支，左分支为0，右分支为1；2、每个叶子结点的编码：从根—>该叶子结点所形成的01代码串---就为该叶子结点对应字符编码。172Outputcode(H,n){

for(i=1;i<n;i++){1、Index=found(H,n)//找到每个叶子结点H[i].left=H[i].right=-12、沿着H[index].parent不断往上寻找，判断该index是其父亲的左孩子还是右孩子，如为左则将0，右则将1压入栈中。3、,重复2，直到找到根，然后将代码出栈，就得到该叶子结点代表的字符的编码。}1734、译码输入一串01串----输出字符串算法思想：1、从根开始走，看到1就走右分支，看0就走左分支，直到走到叶子结点为止（left=right=-1），输出该叶子结点对应的字符。2、重复1，直到01串结束174迁移：1、可实现压缩图像图像RGB表示，分别用8位（一个字节）表示，如R用256个字符表示。判断每个256个字符出现的概率---哈夫曼树（数组）---每个字符的编码---压缩2、中文txt3、视频压缩175176本章学习要点177

1.熟练掌握二叉树的结构特性，了解相应性质的证明方法。

2.熟悉二叉树的各种存储结构的特点及适用范围。

3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。178

4.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟悉二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。179

5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的方法。

6.学会编写实现树的各种操作的算法。

7.