数据结构树和二叉树学习教案

会计学1数据结构PPT树和二叉树数据结构可分为线性结构和非线性结构两大类。前面几章主要研究的是线性结构。一般的，线性结构只能用来描述数据元素之间的线性顺序关系，而很难反映元素之间的层次(分支)关系。本章将要讨论一种非线性数据结构，所谓非线性结构是指在结构中至少存在一个数据元素，它具有两个或两个以上的直接后继或直接前驱。树形结构，是一类非常重要的非线性数据结构，它用于描述数据元素之间的层次关系。树形结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。经常用到的两种结构是树和二叉树。本章先介绍树、二叉树的定义、性质及存储结构，重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系，最后介绍树的应用。

引言第1页/共188页内容提要6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用小结第2页/共188页6.1树的定义和基本术语第3页/共188页树(Tree)是包含n(n≧0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根(Root)的结点；(2)当n>1时，其余的结点可分为m(m>0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。树也可以这样定义：树是由根结点和若干棵子树构成的。可以看出，在树的定义中用了递归的概念，即在树的定义中又用到树的定义，它道出了树的固有特性，因此递归算法是树结构算法的显著特点。

树的定义第4页/共188页上图(a)是只有一个根结点的树；图(b)是有13个结点的树，其中A是根，其余结点分成三个互不相交的子集：T1={B，E，F，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1、T2和T3都是根A的子树，且本身也是一棵树。例如T1，其根为B，其余结点分为两个互不相交的子集；T11={E，K，L}，T12={F}。T11和T12都是B的子树。而T11中E是根结点，{K}和{L}是E的两棵互不相交的子树，其本身又是只有一个根结点的树。第5页/共188页数据对象D：D是具有相同特性的数据元素的集合。

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

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

数据关系R：ADTTree{第6页/共188页

基本操作：查找类

插入类删除类第7页/共188页

Root(T)//求树的根结点

查找类：Value(T,cur_e)//求当前结点的元素值

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

插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树第9页/共188页

ClearTree(&T)//将树清空

删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树第10页/共188页树的表示方法有四种，各用于不同的目的。(1)直观表示法：就是一棵树的直观表示。(2)广义表示法：下图(a)是以广义表的形式表示的，根作为由子树森林组成的表的名字写在表的左边。树的形式化表示法主要用于树的理论描述。(3)凹入表示法：下图(b)用的是凹入表示法(类似书的编目)。树的凹入表示法主要用于树的屏幕和打印显示。(4）嵌套集合表示法：参见P120图6.2。表示方法的多样性，正说明了树结构在日常生活中及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可产生一个树结构。

树的表示形式第11页/共188页ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根例如:第12页/共188页第13页/共188页基本术语第14页/共188页结点:结点的度:树的度:叶子结点:分支结点:数据元素及若干指向子树的分支拥有的子树数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM第15页/共188页(从根到结点的)路径：结点的层次:树的深度：

由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次孩子结点：结点子树的根双亲结点：孩子结点的直接前驱兄弟结点：同一双亲的孩子间堂兄弟：双亲在同一层的结点祖先结点：从根到该结点所经分支的所有结点子孙结点：以某结点为根的子树中的任一结点第16页/共188页(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。第17页/共188页任何一棵非空树是一个二元组

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

F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF第18页/共188页对比树型结构和线性结构的结构特点第19页/共188页~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素

(无前驱)

根结点

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

(无后继)多个叶子结点

(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)第20页/共188页6.2

二叉树第21页/共188页6.2.1二叉树的定义

二叉树（BinaryTree）或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。ABCDEFGHK根结点左子树右子树第22页/共188页二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树第23页/共188页抽象数据类型二叉数定义ADTBinaryTree｛数据对象D：D是具有相同特性的数据元素的集合。数据关系R：

若D=

，则R=

，称BinaryTree为空二叉树;

若D≠

，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

(2)若D－{root｝≠φ，则存在D－｛root｝={DL，Dr},DL∩Dr=φ

，

(3)若DL

≠φ,则DL存在唯一的数据元素xL，有<root,xL>

H;且存在DL上的关系HL

H；若Dr≠φ，则Dr存在唯一的数据元素xr，有<root,xr>

H;且存在Dr上的关系Hr

H,H=｛<root,xL>，<root,xr>,HL,Hr｝;(4)（DL,{HL}）是一棵符合本定义的二叉树，称为根root的左子树，（Dr,{Hr}）是一棵符合本定义的二叉树，称为根root的右子树，第24页/共188页二叉树的主要基本操作：查找类插入类删除类第25页/共188页

Root(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,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());第26页/共188页

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);第27页/共188页ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);第28页/共188页6.2.2二叉树

的性质第29页/共188页

性质1：

在二叉树的第i

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

归纳基：

归纳假设：

归纳证明：i=1

层时，只有一个根结点：

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

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

2=2i-1

。第30页/共188页性质2：

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

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

20+21+

+2k-1=2k-1

。第31页/共188页

性质3：

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

2

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

而b=n-1=n0+n1+n2-1由此，n0=n2+1。第32页/共188页两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij第33页/共188页性质4：

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

log2n

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

即

k-1≤log2n<k

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

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

至n

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

的结点：

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

i/2

的结点为其双亲结点；

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

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

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

否则，编号为2i+1的结点为其右孩子结点。第35页/共188页第36页/共188页6.2.3二叉树的存储结构二、二叉树的链式存储结构一、二叉树的顺序存储结构第37页/共188页#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;一、二叉树的顺序存储结构第38页/共188页按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储二叉树上的结点元素。因此，必须把结点安排成一个适当的线性序列，使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系。在一棵有n个结点的完全二叉树中，从树根起，自上层到下层，每层从左到右地给结点编号，就能得到一个足以反映整个二叉树结构的线性序列，如下图所示。二叉树的顺序存储结构第39页/共188页第40页/共188页第41页/共188页第42页/共188页练习:ABCDEF

ABDCEF

0123456789101112131401326第43页/共188页二、二叉树的链式存储表示1.二叉链表2．三叉链表3．双亲链表4．线索链表第44页/共188页ADEBCF

rootlchilddatarchild结点结构:1.二叉链表二叉链表第45页/共188页ABCDEF二叉树第46页/共188页typedefstruct

BiTNode

{//结点结构

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:第47页/共188页ADEBCF

root

2．三叉链表parent

lchilddatarchild结点结构:第48页/共188页

typedefstruct

TriTNode

{//结点结构

TElemTypedata;

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

structTriTNode

*parent;//双亲指针

}TriTNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:第49页/共188页0123456dataparent结点结构:3．双亲链表LRTagLRRRL第50页/共188页

typedefstruct

BPTNode

{//结点结构

TElemTypedata;

int

*parent;//指向双亲的指针

charLRTag;//左、右孩子标志域

}BPTNode

typedefstructBPTree{//树结构

BPTNodenodes[MAX_TREE_SIZE];

intnum_node;//结点数目

introot;//根结点的位置

}BPTree第51页/共188页6.3.1二叉树的遍历6.3遍历二叉树和线索二叉树第52页/共188页一、问题的提出二、先左后右的遍历算法三、算法的递归描述四、中序遍历算法的非递归描述五、遍历算法的应用举例第53页/共188页

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

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

每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。第55页/共188页二叉树的遍历方法二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：L：遍历左子树

D：访问根结点

R：遍历右子树

有六种遍历方法：

DLR，LDR，LRD，

DRL，RDL，RLD约定先左后右,有三种遍历方法：

DLR、LDR、LRD

，分别称为

先序遍历、中序遍历、后序遍历

A

F

G

E

D

C

B第56页/共188页58

先序遍历（

DLR

）

若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；

先序遍历序列：

A

F

G

E

D

C

B例：先序遍历右图所示的二叉树（1）访问根结点A（2）先序遍历左子树：即按DLR的顺序遍历左子树（3）先序遍历右子树：即按DLR的顺序遍历右子树ABCDFGE二、先左后右的遍历算法第57页/共188页59中序遍历（

LDR

）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树

中序遍历序列：

A

F

G

E

D

C

B例：中序遍历右图所示的二叉树（1）中序遍历左子树：即按LDR的顺序遍历左子树

（2）访问根结点A（3）中序遍历右子树：即按LDR的顺序遍历右子树DBCGFAE第58页/共188页60后序遍历（LRD）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点

后序遍历序列：例：后序遍历右图所示的二叉树（1）后序遍历左子树：即按LRD的顺序遍历左子树

（2）后序遍历右子树：即按LRD的顺序遍历右子树（3）访问根结点A

A

F

G

E

D

C

BDGCEAFB第59页/共188页61

e

d

c

b

f

a

+

*

/

-

-

后序遍历序列：

中序遍历序列：

先序遍历序列：例：先中序遍历序遍历、中序遍历、后序遍历下图所示的二叉树前缀表达式中缀表达式后缀表达式-+a*b-cd/efa+b*c-d-e/fabcd-*+ef/-第60页/共188页R^A^DE^^C^H^F^G^B^K^^练习：求下列二叉链表和二叉树的三种遍历次序ABCDEFGHK第61页/共188页这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分：1）基本项（也叫终止项）；2）递归项

若二叉树非空（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；先序遍历递归定义递归项上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例：先序遍历（DLR）的定义：该定义隐含着若二叉树为空，结束三、算法的递归描述第62页/共188页上面先序遍历的定义等价于：若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项

（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；

下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit()访问结点总是成功的。第63页/共188页先序遍历递归算法

voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法//先序遍历以为根结点指针的二叉树，对每个数据元素调用函数//Visit()

if(T){//若二叉树为空，结束返回

//若二叉树不为空，访问根结点；遍历左子树，遍历右子树Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse最简单的Visit函数是：

StatusPrintElement(TElemTypee){//输出元素e的值

printf(e);returnOK;}

∧D

A

B

C

∧∧E

∧F∧T第64页/共188页2中序遍历递归算法

voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()

if(T){//若二叉树为空，结束返回

//若二叉树不为空，遍历左子树，访问根结点，遍历右子树

InOrderTraverse(T->lchild,Visit);Visit(T->data)；

InOrderTraverse(T->rchild,Visit);

}//InOrderTraverse你能写出后序遍历递归算法了吧?第65页/共188页3后序遍历递归算法

voidPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()

if(T){//若二叉树为空，结束返回

//若二叉树不为空，遍历左子树，遍历右子树，访问根结点

PostOrderTraverse(T->lchild,Visit);

PostOrderTraverse(T->rchild,Visit);Visit(T->data)；

}//PostOrderTraverse第66页/共188页任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。GHDEFBCA第67页/共188页四、中序遍历算法的非递归描述StatusInOrderTraverse(BiTreeT,Status(*Visit)(ElemType)){//采用二叉链表存储结构，Visit是对数据元素操作的应用//函数.中序遍历二叉树T的非递归算法，对每个数据元素调//用函数Visit。

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;}//InOrderTraverse第68页/共188页StatusInOrderTraverse(BiTreeT,Status(*Visit)(ElemType)){//采用二叉链表存储结构，Visit是对数据元素操作的应用//函数。中序遍历二叉树T的非递归算法，对每个数据元素调//用函数Visit。

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;}//InOrderTraverse第69页/共188页中序遍历二叉树的非递归算法

示意图CBDFAGEABCDGEFABCNULLSGetTop<--pAS

PoppCBDFA第70页/共188页五、遍历算法的应用举例1、统计二叉树中叶子结点的个数

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

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

CountLeaf

(BiTreeT,int&count){

if(T){

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

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf第73页/共188页2、求二叉树的深度(后序遍历)算法基本思想:

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

首先分析二叉树的深度和它的左、右子树深度之间的关系。第74页/共188页int

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

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

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

}

returndepthval;}第75页/共188页3、复制二叉树其基本操作为：生成一个结点。根元素T左子树右子树根元素NEWT左子树右子树左子树右子树(后序遍历)第76页/共188页BiTNode

*GetTreeNode(TElemTypeitem,

BiTNode

*lptr,BiTNode*rptr){

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);

T->data=item;

T->lchild=lptr;T->rchild=rptr;

returnT;}

生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr)第77页/共188页BiTNode

*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);

returnnewT;}//CopyTree第78页/共188页ABCDEFGHK^D^C^^B^H^^K^G^F^E^A例如：下列二叉树的复制过程如下：newT第79页/共188页4、建立二叉树的存储结构

为二叉树建立二叉链表

输入：二叉树的先序序列

结果：二叉树的二叉链表

遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有结点并完成相应结点的链接？基本思想：输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接第80页/共188页∧D

A

B

∧C

∧∧E

∧∧F

∧T

先序序列：ABDFCE（在空子树处添加*的二叉树的）先序序列：ABD*F***CE***

A

F

E

D

C

B*******

A

F

E

D

C

B第81页/共188页StatusCreateBiTree(BiTree&T){//输入（在空子树处添加*的二叉树的）先序序列（设每个元//素是一个字符）按先序遍历的顺序，建立二叉链表，并将//该二叉链表根结点指针赋给Tscanf(&ch);if(ch==‘*’)T=NULL;//若ch==‘*’则T=NULL返回

else{//若ch!=‘*’if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->date=ch;//建立（根）结点

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

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

}returnOK;}//CreateBiTree第82页/共188页84

分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：由二叉树的先序和中序序列建立二叉树二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根第83页/共188页851.用前序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列;4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，则得到的二叉树如下页所示第84页/共188页861.A为根结点ABDGHCEFIGDHBAECIFBDGHCEFIA2.B为左子树的根结点BDGHGDHBCEFIDHGBA3.D为左子树的左子树的根结点第85页/共188页874.C为右子树的根结点5.F为右子树的右子树的根结点CEFIECIF第86页/共188页abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列第87页/共188页练习：已知结点的先序序列和中序序列，求整棵二叉树。先序序列：ABCDEFG中序序列：CBEDAFGAC

B

E

DFGABCDEFGABCFDEG第88页/共188页6.3.2

线索二叉树

线索二叉树的定义线索的描述建立线索二叉树线索二叉树上的运算第89页/共188页遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA一、线索二叉树的定义第90页/共188页

在这样的线性序列中，很容易求得某个结点在某种遍历下的直接前驱和后继。然而，有时我们希望不进行遍历就能快速找到某个结点在某种遍历下的直接前驱和后继，这样，就应该把每个结点的直接前驱和直接后继记录下来。为了做到这一点，可以在原来的二叉链表结点中，再增加两个指针域，一个指向前驱，一个指向后继，但这样做将会浪费大量存贮单元，存贮空间的利用率相当低(一个结点中有4个指针，1个指左孩子，1个指右孩子，1个指前驱，1个指后继)，而原来的左、右孩子域有许多空指针又没有利用起来。为了不浪费存贮空间，我们利用原有的孩子指针为空时来存放直接前驱和后继，这样的指针称为“线索”，加线索的过程称为线索化，加了线索的二叉树，称为线索二叉树，对应的二叉链表称为线索二叉链表。一、线索二叉树的定义第91页/共188页指向该线性序列中的“前驱”和“后继”的指针，称作“线索”加了线索的二叉树，称作“线索二叉树”包含“线索”的二叉链表，称作“线索链表”ABCDEFGHK^D^

C^^B

E^第92页/共188页

在线索二叉树中，由于有了线索，无需遍历二叉树就可以得到任一结点在某种遍历下的直接前驱和后继。但是，我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢?为此，在二叉链表结点中，还必须增加两个标志域ltag、rtag。

ltag和rtag定义如下：

0lchild域指向结点的左孩子ltag=1lchild域指向结点在某种遍历下的直接前驱

0rchild域指向结点的右孩子rtag=1rchild域指向结点在某种遍历下的直接后继

第93页/共188页

这样，二叉链表中每个结点还是有5个域，但其中只有2个指针，较原来的4个指针要方便。增加线索后的二叉链表结点结构可描述如下：第94页/共188页typedefstruct

BiThrNod{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指针

PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;二、线索的描述：1、类型定义：typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指针，Thread==1:线索第95页/共188页2．线索的画法

在二叉树或二叉链表中，若左孩子为空，则画出它的直接前驱，右孩子为空时，则画出它的直接后继，左右孩子不为空时，不需画前驱和后继。这样就得到了线索二叉树或线索二叉链表。第96页/共188页先序序列为：ABCD第97页/共188页中序序列为：BADC第98页/共188页后序序列为：BDCA第99页/共188页ABCDE第100页/共188页ABCDEABDCET先序序列：ABCDE先序线索二叉链表00001111^11第101页/共188页ABCDEABDCET中序序列：BCAED中序线索二叉链表00001111^11^第102页/共188页ABCDEABDCET后序序列：CBEDA后序线索二叉链表0000111111^第103页/共188页ABCDE0A01B00D11C11E1T中序序列：BCAED带头结点的中序线索二叉链表

0

1头结点：ltag=0,lchild指向根结点rtag=1,rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点ABDCET中序序列：BCAED中序线索二叉链表00001111^11^第104页/共188页

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。此外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。

三、建立线索二叉树第105页/共188页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}//InThreading第106页/共188页StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//构建中序线索链表

if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);

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

//添加头结点

returnOK;}//InOrderThreading

……第107页/共188页if(!T)

Thrt->lchild=Thrt;

else{Thrt->lchild=T;

pre=Thrt;InThreading(T);

pre->rchild=Thrt;//处理最后一个结点

pre->RTag=Thread;

Thrt->rchild=pre;

}第108页/共188页四、线索二叉树上的运算1．线索二叉树上的查找

（1）查找指定结点在中序线索二叉树中的的直接后继

若所找结点右标志rtag=1，则右孩子域指向中序后继，否则，中序后继应为遍历右子树时的第一个访问结点,即右子树中最左下的结点（参见下图）。从下图中可知，x的后继为xk

。第109页/共188页（2）查找指定结点在中序线索二叉树中的的直接前驱

若所找结点左标志ltag=1，则左孩子域指向中序前驱，否则，中序前驱应为遍历左子树时的最后一个访问结点，即左子树中最右下的结点（参见下图）。从下图中可知，x的前驱为xk

。第110页/共188页

(3)查找指定点在先序线索二叉树中的直接后继

先序后继的查找比较方便，若Ｐ无左孩子，右孩子为后继，否则左孩子为后继。

(4)查找指定结点在后序线索二叉树中的直接前驱

后序前驱的查找也比较方便，若左孩子为空，左链指前驱，否则，若右子树为空，左孩子为前驱，否则右孩子为前驱。

求后序后继和先序前驱都比较麻烦，在此不再作进一步介绍。第111页/共188页2．线索二叉树上的遍历

遍历某种次序的线索二叉树，只要从该次序下的开始结点出发，反复找到结点在该次序下的后继，直到后继为空。这对于中序线索和前序线索二叉树很方便，但对于后序线索二叉树较麻烦(因求后序后继较麻烦)。故后序线索对于遍历没有什么意义。第112页/共188页中序线索链表的遍历算法

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

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

void(*Visit)(TElemTypee)){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=p->rchild;Visit(p->data);//访问后继结点

}p=p->rchild;//p进至其右子树根

}}//InOrderTraverse_Thr第114页/共188页

从上面算法可知，线索二叉树上的遍历较一般二叉树要方便得多。但是这种方便是以增加线索为代价的，增加线索本身要花费大量时间。所以二叉树是以二叉链表表示，还是以线索二叉链表示，可根据具体问题而定。3．线索二叉树的插入和删除

线索二树上的查找、遍历都较一般二叉树方便，但线索二叉树也存在其缺点，就插入和删除运算而言，线索二叉树比一般二叉树的时间花费大，因为除修改指针外，还要修改相应线索。线索二叉树的扦入和删除较麻烦，因此本书不再介绍算法第115页/共188页

6.4树和森林

第116页/共188页6.4.1树的存储结构一、双亲表示法二、孩子表示法三、孩子-兄弟（树的二叉链表）存储表示法第117页/共188页

它是以一组地址连续的存储单元来存放树中的结点，每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。该结构的具体描述见下图。

一、双亲表示法:第118页/共188页ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=6dataparent例:第119页/共188页

typedefstructPTNode{TElemTypedata;

intparent;//双亲位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:第120页/共188页typedefstruct{PTNodenodes[MAX_TREE_SIZE];

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

}PTree;树结构:第121页/共188页

将一个结点所有孩子链接成一个单链表，而树中有若干个结点，故有若干个单链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述，具体描述参见下图

二、孩子表示法:第122页/共188页typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子结点结构:

childnextC语言的类型描述:第123页/共188页

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

}CTBox;双亲结点结构

datafirstchild第124页/共188页typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

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

}CTree;树结构:第125页/共188页

双亲孩子表示法

将第1、2两种方法结合起来，则得到双亲孩子表示法，具体参见下图。第126页/共188页ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=6datafirstchild123456例:-1000224第127页/共188页

类似于二叉链表，但第一个链指向第一个孩子，第二个链指向下一个兄弟。将左图的树用孩子兄弟表示法表示，见右图。三、孩子-兄弟（树的二叉链表）表示法第128页/共188页ABCDEFGABCEDFGrootABCEDFG

例第129页/共188页typedefstructCSNode{ElemTypedata;

structCSNode

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

firstchilddatanextsibling第130页/共188页1．树转换成二叉树可以分为三步：（1）

连线指相邻兄弟之间连线。（2）

抹线指抹掉双亲与除左孩子外其它孩子之间的连线。

（3）

旋转只需将树作适当的旋转。

具体实现过程见下图。

6.4.2森林与二叉树的转换第131页/共188页第132页/共188页2．森林转换成二叉树

（1）将森林中每一棵树分别转换成二叉树

这在刚才的树转换成二叉树中已经介绍过。（2）合并

使第n棵树接入到第n-1棵的右边并成为它的右子树，第n-1棵二叉树接入到第n-2棵的右边并成为它的右子树，…，第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止。第133页/共188页第134页/共188页3．二叉树还原成树或森林

（1）右链断开

将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子树的二叉树。具体操作见下图(b)。

（2）二叉树还原成树

将（1）中得到的每一棵二叉树都还原成树（与树转换成二叉树的步骤刚好相反）。具体操作步骤见下图(c)。

第135页/共188页第136页/共188页6.4.3树和森林的遍历第137页/共188页一、树的遍历二、森林的遍历第138页/共188页树的遍历可有三条搜索路径:按层次遍历:先根(次序)遍历:后根(次序)遍历:

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

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

若树不空，则自上而下自左至右访问树中每个结点。第139页/共188页ABCDEFGHIJK

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

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

层次遍历时顶点的访问次序：KJIHGFBCDEAADGHKCFIJBEKJIHGDBEFCA第140页/共188页

BCDEFGHIJK1．森林中第一棵树的根结点；2．森林中第一棵树的子树森林；3．森林中其它树构成的森林。森林由三部分构成：第141页/共188页1.先序遍历森林的遍历

若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。第142页/共188页２．中序遍历

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

余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。第143页/共188页

树的遍历和二叉树遍历的对应关系？先根遍历后根遍历树二叉树森林先序遍历先序遍历中序遍历中序遍历第144页/共188页6.6赫夫曼树

及其应用

最优二叉树（赫夫曼树）

如何构造赫夫曼树赫夫曼编码

第145页/共188页6.6.1最优二叉树（赫夫曼树）

1．路径和路径长度

在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。在路径上的分支数目被称为路径长度。

树的路径长度是从树根到每一个结点的路径长度之和

2．结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度为：从该结点到树根之间的的路径长度与结点上权的乘积。

第146页/共188页

3．树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl=，其中n为叶子结点数目，wi为第i个叶子结点的权值，li

为第i个叶子结点的路径长度。

4．赫夫曼树的定义

假设有n个权值{w1，w2，…，wn}，试构造一棵有n个叶子的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。第147页/共188页下面我们讨论一下权值、树形与带权的路径长度之间的关系。假设有6个权值分别为{3，6，9，10，7，11}，以这6个权值作为叶子结点的权值可以构造出下面三棵二叉树。第148页/共188页36791011(a)这棵二叉树的带权路径长度为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117第149页/共188页11109763(b)这棵二叉树的带权路径长度为：WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177第150页/共188页11103679(c)这棵二叉树的带权路径长度为：WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158第151页/共188页WPL(T)=72+52+22+42=36WPL(T)=71+52+23+43=35WPL(T)=73+53+42+21=46第152页/共188页

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

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

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

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

重复

(2)

和

(3)

两步，直至F中只含一棵树为止。(3)(4)第155页