数据结构课件 第6章 树和二叉树

第六章树和二叉树6.1树的类型定义树（Tree）是n（n≥0）个结点的有限集。在任意一棵非空树当中：（1）有且仅有一个特定的结点称为根结点（Root）（2）当n〉1时，其余结点可分为m（m〉0）个互不相交的有限集T1T2…Tm，其中每一个集合本身又是一棵树，并且称为根的子树（subtree）树结构中的基本术语：结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树的个数。终端结点（叶子）：度为0的结点非终端结点（分支）：度不为0的结点树的度：树内各结点的度的最大值。孩子：结点子树的根结点。双亲：结点本身成为其孩子的双亲（父）结点。兄弟：同一个双亲结点的孩子之间互称为兄弟。祖先：是从根到该节点所经分支上的所有结点。子孙：以某结点为根的子树中的任意结点。结点的层次：从根开始定义为第1层，根的孩子为第二层……堂兄弟：其双亲在同一层的结点。树的深度（高度）：树中结点的最大层数。有序树：树中结点的子树看成从左到右有序的（不能互换），则称概树为有序树，否则称为无序树。森林（forest）：是m（m≥0）棵互不相交的树的集合。树的抽象数据类型的定义如下：

ADTTree{

数据对象：D是具有相同特性的数据元素的集合。

数据关系：

若D为空集，则称为空树；

若D中仅含一个数据元素，则关系R为空集；

否则R={H}，

(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

(2)当n>1时，其余数据元素可分为m(m>0)个互不相交的(非空)有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树，每一棵子树的根xi都是根root的后继，即<root,xi>H,i=1,2,…,m。

基本操作：

{结构初始化}

InitTree(&T);

操作结果：构造空树T。

CreateTree(&T,definition);

初始条件：definition给出树T的定义。

操作结果：按definition构造树T。

{销毁结构}

DestroyTree(&T);

初始条件：树T存在。

操作结果：销毁树T。{引用型操作}

TreeEmpty(T);

初始条件：树T存在。

操作结果：若T为空树，则返回TRUE，否则返回FALSE。

TreeDepth(T);

初始条件：树T存在。

操作结果：返回T的深度。

Root(T);

初始条件：树T存在。

操作结果：返回T的根。

Value(T,cur_e);

初始条件：树T存在，cur_e

是T中某个结点。

操作结果：返回cur_e

的值。

Parent(T,cur_e);

初始条件：树T存在，cur_e

是T中某个结点。

操作结果：若cur_e

是T的非根结点，则返回它的双亲，否则返回“空”。LeftChild(T,cur_e);

初始条件：树T存在，cur_e

是T中某个结点。

操作结果：若cur_e

是T的非叶子结点，则返回它的最左孩子，否则返回"空"。

RightSibling(T,cur_e);

初始条件：树T存在，cur_e

是T中某个结点。

操作结果：若cur_e

有右兄弟，则返回它的右兄弟，否则返回“空”。

TraverseTree(T,visit());

初始条件：树T存在，visit是对结点操作的应用函数。

操作结果：按某种次序对T的每个结点调用函数

visit()一次且至多一次。

一旦visit()失败，则操作失败。{加工型操作}

Assign(T,cur_e,value);

初始条件：树T存在，cur_e

是T中某个结点。

操作结果：结点cur_e

赋值为value。

ClearTree(&T);

初始条件：树T存在。

操作结果：将树T清为空树。

InsertChild(&T,&p,i,c);

初始条件：树T存在，p指向T中某个结点，

1≤i≤p所指结点的度＋1，空树c与T不相交。

操作结果：插入c为T中p所指结点的第i棵子树。

DeleteChild(&T,&p,i);

初始条件：树T存在，p指向T中某个结点，

1≤i≤p指结点的度。操作结果：删除T中p所指结点的第i棵子树。

}ADTTree

可从另一个角度来定义树。

定义森林为m(m≥0)棵互不相交的树的集合。

则可定义树是一个二元组

Tree=(root,F)

其中，root

是数据元素，称作树的根，

F

是子树森林，记作F=(T1,T2,…,Tm),

其中Ti=(ri,Fi)

为根root的第i棵(符合本定义的)子树，当m≠0是，在树根和其子树森林之间存在下列关系：

RF={<root,ri>|i=1,2,…,m,m>0}

树和线性结构作如下对照：线性结构树结构存在唯一的没有前驱

的"首元素"存在唯一的没有前驱的

"根结点"

存在唯一的没有后继

的"尾元素"

存在多个没有后继的

"叶子"

其余元素均存在唯一

的"前驱元素"和唯一

的"后继元素"

其余结点均存在唯一的

"前驱(双亲)结点"和多

个"后继(孩子)结点"6.2二叉树类型6.2.1二叉树的类型定义

二叉树的抽象数据类型定义如下:ADTBinaryTree{

数据对象：D是具有相同特性的数据元素的集合。

数据关系：

若D为空集，称BinaryTree

为空二叉树；

否则关系R={H}：

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

root，它在关系H下无前驱；

(2)D中其余元素必可分为两个互不相交的子集

L和R，每一个子集都是一棵符合本定义的二叉树，并分别为root的左子树和右子树。如果左子树L不空，则必存在一个根结点XL，它是root的“左后继”(<root,XL>∈H)如果右子树R不空，则必存在一个根结点XR，为root的"右后继"(<root,XR>∈H)。

基本操作：

{结构初始化}

InitBiTree(&T);

操作结果：构造空二叉树T。

CreateBiTree(&T,definition);

初始条件：definition给出二叉树T的定义。

操作结果：按definition构造二叉树T。

{销毁结构}

DestroyBiTree(&T);

初始条件：二叉树T存在。

操作结果：销毁二叉树T。

{引用型操作}

BiTreeEmpty(T);

初始条件：二叉树T存在。

操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。

BiTreeDepth(T);

初始条件：二叉树T存在。

操作结果：返回T的深度。

Root(T);

初始条件：二叉树T存在。

操作结果：返回T的根。

Value(T,e);

初始条件：二叉树T存在，e是T中某个结点。

操作结果：返回e的值。Parent(T,e);

初始条件：二叉树T存在，e是T中某个结点。

操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。LeftChild(T,e);

初始条件：二叉树T存在，e是T中某个结点。

操作结果：返回e的左孩子。若e无左孩子，则返回"空"。RightChild(T,e);

初始条件：二叉树T存在，e是T中某个结点。

操作结果：返回e的右孩子。若e无右孩子，则返回“空”。LeftSibling(T,e);

初始条件：二叉树T存在，e是T中某个结点。

操作结果：返回e的左兄弟。若e是其双亲的左孩子或无左兄弟，则返回“空”。RightSibling(T,e);

初始条件：二叉树T存在，e是T的结点。

操作结果：返回e的右兄弟。若e是其双亲的右孩子或无右兄弟，则返回"空"。

PreOrderTraverse(T,visit());

初始条件：二叉树T存在，visit是对结点操作的应用函数。

操作结果：先序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。InOrderTraverse(T,vsit());

初始条件：二叉树T存在，visit是对结点操作的应用函数。

操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。

PostOrderTraverse(T,visit());

初始条件：二叉树T存在，visit是对结点操作的应用函数。

操作结果：后序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。LevelOrderTraverse(T,visit());

初始条件：二叉树T存在，visit是对结点操作的应用函数。

操作结果：层序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。

{加工型操作}

ClearBiTree(&T);

初始条件：二叉树T存在。

操作结果：将二叉树T清为空树。

Assign(&T,&e,value);

初始条件：二叉树T存在，e是T中某个结点。

操作结果：结点e赋值为value。

InsertChild(&T,p,LR,c);

初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。

操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点原有左或右子树成为c的右子树。

DeleteChild(&T,p,LR);

初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。

操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。

}ADTBinaryTree

6.2.2二叉树的几个特性

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

个结点(i≥1)。

利用归纳法容易证得此结论。证明：

归纳基：i=1

时，只有一个根结点。显然2i-1=20=1是对的。归纳假设：设对所有的j(1≤j<i)，命题成立，即第j层上至多有2j-1

个结点。归纳证明：由归纳假设“第i-1层上至多有

2i-2个结点”，又二叉树的每个结点的度至多为2，则第

i层上的最大结点数为第

i-1层上最大结点数的2倍，即2×2i-2=2i-1。证毕。二、深度为k的二叉树中至多含有2k-1个结点，(k≥1)。证明：

由特性一可推出，深度为k的二叉树上最大结点数为三、对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则

n0

=n2

+1证明：

由于二叉树中只有三种结点，假设n1为二叉树T中度为1的结点数，则二叉树中结点总数为

n=n0+n1+n2

①

再看二叉树中的分支数目。除了根结点外，其余结点都有一个分支进入，假设B为分支数，则

n=B+1。从另一角度看，这些分支是由度为1或2的结点射出的，所以又有B=n1+2n2

即n=n1+2n2+1

②

综合以上①和②两个等式便可得到

n0=n2+1

有两种特殊形态的二叉树满二叉树:若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。

对满二叉树从上到下从左到右进行从1开始的编号（如图所示），则任意一棵二叉树都可以和同深度的满二叉树相对比。完全二叉树

:假如一棵包含n个结点的二叉树中每个结点都可以和满二叉树中编号为1至n的结点一、一对应，则称这类二叉树为完全二叉树。显然一棵深度为h的完全二叉树中，前h-1层中的结点都是"满"的，且第h层的结点都集中在左边。显然，满二叉树本身也是完全二叉树。

四、具有n个结点的完全二叉树的深度为log2n+1。

假设该完全二叉树的深度为k，则根据特性二和完全二叉树的定义

2k-1-1<n≤2k-1

或2k-1≤n<2k

对后者取对数便得k-1≤log2n<k

因为k是整数，所以k=[log2n]+1

。

五、如果对一棵有n个结点的完全二叉树（其深度为log2n+1）的结点按层序（从第1层到第log2n+1层，每层从左到右）从1起开始编号，则对任一编号为i的结点(1≤i≤n)，有

(1)

如果i=1，则编号为i的结点是二叉树的根，无双亲；如果

i>1，则其双亲结点parent(i)

的编号是

i/2

。

(2)

如果

2i>n，则编号为i

的结点无左孩子（编号为i的结点为叶子结点）；否则其左孩子结点lChild(i)

的编号是2i

。

(3)

如果2i+1>n，则编号为i

的结点无右孩子；否则其右孩子结点rChild(i)

的编号是结点

2i+1。6.3二叉树的存储表示

用一组地址连续的存储单元存储二叉树中的数据元素。二叉树的顺序存储结构的定义如下：

constMAXSIZE=100;//定二叉树中结点数的max为100

typedef

struct

{

ElemType

data[MAXSIZE];//存储空间基址(初始化时分配空间)

int

nodeNum;

//二叉树中结点数

}SqBiTree;

//二叉树的顺序存储结构6.3.1顺序存储结构

对于完全二叉树，只要从根起按层序存储即可。

0123456789abcdefghij根据二叉树的特性五，可推出顺序存储结构中“双亲”和“孩子”的关系：

假设bt.data[i]

是完全二叉树上的一个结点，若

2i+1<bt.nodeNum，则bt.data[2i+1]

是它的左孩子，否则它的左子树为空树；若2i+2<bt.nodeNum，则bt.data[2i+2]是它的右孩子，否则它的右子树为空树。对于一般二叉树，应将其每个结点与完全二叉树上的结点相对照，存在一维数组的相应分量中，不存在的结点用0表示01234567891011121314ABC0E0F00G000006.3.2链式存储结构

一、二叉链表二叉链表的结点结构：lchilddatarchild二叉树的二叉链表存储表示

typedef

struct

BiTNode

{

ElemTypedata;

struct

BiTNode*Lchild,*Rchild;

}*BiTree;a图二叉树的二叉链表如下b图所示。

ab二、三叉链表的结点结构：parentlchilddatachild二叉树的三叉链表存储表示

typedef

struct

TriTNode

{

ElemTypedata;

struct

BiTNode*Lchild,*Rchild;//左、右孩子指针

struct

BiTNode*parent;

//双亲指针

}*TriTree;

和上页相同的二叉树的三叉链表如下图所示。

6.4二叉树的遍历遍历二叉树有两种方法：

1)深度优先遍历二叉树（三部分，根、左子树、右子树）

2)广度优先遍历二叉树（按层次遍历）6.4.1深度优先遍历

深度优先遍历由左到右TLR,LTR,LRT由右到左TRL,RTL,RLT三个深度优先遍历二叉树的算法：

先序遍历二叉树中序遍历二叉树后序遍历二叉树二叉树为空，则空操作；

否则

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。若二叉树为空，则空操作；

否则

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。若二叉树为空，则空操作；

否则

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。请参看flash6-4-2-1、flash6-4-2-2、flash6-4-2-3由于遍历算法的定义很容易写出对应的递归算法算法6.1

voidPreorder(BiTreeT，void(*visit)(BiTree))

{

//先序遍历以T为根指针的二叉树

if(T){//T=NULL时，二叉树为空树，不做任何操作

visit(T);

//通过函数指针*visit访问根结点

Preorder(T->Lchild,visit);//先序遍历左子树

Preorder(T->Rchild,visit);//先序遍历右子树

}//if

}//Preorder根据遍历递归算法递归工作栈的状态变化状况可以直接写出相应的非递归算法算法6.2

void

InorderTraverse(BiTreeT，void(*visit)(BiTree))

{

//采用二叉链表存储结构，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->lchild))ReturnERROR;

Push(S,P->rchild);

}//if

}//while

Returnok;

}//InorderTraverse层次遍历右图的遍历序列为：ABCDTFGHIJ6.4.2广度优先遍历二叉树（按层次遍历二叉树）过程：先访问第1层，然后从左到右依次访问第2层两个节点，依此类推，当第i层访问完以后，在从左到右访问第i+1层的各个节点。这里需要使用一个队列作为辅助的存储结构

在遍历开始时，首先把根节点放入队列；然后每次从队列中取出队头元素进行处理，每处理一个结点时，按从左到右的顺序把它的所有子结点放入队列。这样，上层结点总是排在下一层结点的前面，从而实现了二叉树的广度优先遍历。二叉树的广度优先遍历算法，同学们自己练习写下6.5线索二叉树

6.5.1二叉树的线索链表

先序序列为：

ABDEGHCFIJ

中序序列为：

DBGEHACIJF

后序序列为：

DGHEBJIFCA

如何保存在遍历过程中得到的前驱和后继信息？方法一：最简单的办法是在结点中增加两个指针域分别指向该结点的前驱和后继，但如此做将使存储结构的存储密度大大降低。方法二：一个含n个结点的二叉链表中有n+1个链域的值为"NULL"，可以利用这些空的指针域存放指向前驱和后继的信息，由此得到的二叉树的存储结构称作"线索链表"，其中指向前驱或后继的指针称作"线索"。线索链表的结构定义如下：

二叉树的二叉线索链表存储表示

typedef

enum

PointerType{Link=0,Thread=1};

//

定义指针类型，以Link表示指针，Thread表示线索

typedef

struct

BiThrNode{

ElemTypedata;

struct

BiThrNode

*Lchild,*Rchild;

//

左右指针

PointerType

LTag,RTag;

//

左右指针类型标志

}

*BiThrTree;

若结点的左指针类型标志为“Link”，则Lchild

指向它的左子树根结点，否则指向它的“前驱”；

若结点的右指针类型标志为“Link”，则Rchild

指向它的右子树根结点，否则指向它的"后继"。

图二叉树的中序线索链表如下所示（图中所有实线表示指针，虚线表示线索）

从图中可见，在线索链表中添加了一个"头结点"，头结点的左指针指向二叉树的根结点，其右线索指向中序序列中的最后一个结点，中序序列中的第一个结点的左线索和中序序列中的最后一个结点的右线索均指向头结点。这就好比将二叉树中所有结点置于一个双向循环链表之中，即可以从头结点出发，依照中序遍历的规则对二叉树中的结点依次进行"顺序"（和中序序列相同的次序）访问，或"逆序"（和中序序列相反的次序）访问。

6.5.2以中序线索链表为存储结构的中序遍历如何在中序线索链表上进行遍历，关键问题有二：一是如何找到访问的第一个结点？

二是如何找到每个结点在中序序列中的后继？

由于线索链表上保存的是“遍历”过程中得到的前驱和后继的信息，显然，线索链表应该在遍历过程中建立，即在遍历过程中改变二叉链表中结点的“空指针”以及相应的“指针类型标志”。

6.5.2以中序线索链表为存储结构的中序遍历若结点没有左子树，

则令其左指针指向它的“前驱”并将左指针类型标志改为“Thread”，若结点没有右子树，

则令它右指针指向它的“后继”并将右指针类型标志改为“Thread”。为了获取"前驱"的信息，需要在遍历过程中添加一个指向其前驱的指针pre。

由此建立线索链表的过程即为将遍历过程中对结点进行下列“访问”操作(指针p指向当前访问的结点，pre

指向在它之前“刚刚”访问过的结点)：

if(!pre->Rchild){

pre->RTag=Thread;

pre->Rchild=p;

}

if(!p->Lchild){

p->LTag=Thread;

p->Lchild=pre;

}

pre=p;

6.5.3线索链表的生成

算法6.10

void

InThreading(BiThrTreep，BiThrTree&pre)

{//对p指向根结点的二叉树进行中序遍历，遍历过程中进行//“中序线索

化”。若p所指结点的左指针为空，则将它改为“左线//索”，若pre所指结点的右指针为空，则将它改为“右线索”。指//针pre在遍历

过程中始终指向p所指结点在中序序列中的前趋

if(p){

InThreading(p->Lchild,pre);

//对左子树进行线索化

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,pre);

//对右子树进行线索化

}//if

}//InThreading算法6.11

void

InOrderThreading(BiThrTree

&Thead,BiThrTreeBT)

{//BT为指向二叉树根结点的指针，由此二叉链表建立二叉树

//的中序线索链表，Thead

指向线索链表中的头结点。

BiThrTreepre;

if(!(Thead=new

BiThrNode))exit(1);//存储分配失败

Thead->LTag=Link;Thead->RTag=Thread;

//建头结点

Thead->Rchild=Thead;

//右指针回指

if(!BT)Thead->Lchild=Thead;

//若二叉树空，则左指针回指

else

{

Thead->Lchild=BT;pre=Thead;

InThreading(BT,pre);

//中序遍历进行中序线索化

pre->Rchild=Thead;pre->RTag=Thead;

//对中序序列中最后一个结点进行线索化

Thead->Rchild=pre;

//建非空树的头结点的"右线索"

}//else

}//InOrderThreading

参看flash6-5-26.6树和森林的存储表示

6.6.1树的双亲表示法

结点中只设一个指向双亲的指针，并对无序树不需要设子树位置的标志。所有结点存储在一个地址连续的存储空间中。

例如，下图所示树的双亲链表如下所示r=0n=110A-16C01B07D02E18F73H29G74I210K95J2树的双亲链表存储表示

constMAX_TREE_SIZE=100;

typedef

struct{

//结点结构

ElemTypedata;

intparent;

//双亲位置域

}

PTNode;

typedef

struct{

//树结构

PTNode

nodes[MAX_TREE_SIZE];

intr,n;

//根的位置和结点数

}

PTree;

6.6.2树的孩子表示法

让每个结点的"子树根"构成一个线性表，以链表作它的存储结构，令其头指针和结点的数据元素构成一个结点，并将所有这样的结点存放在一个地址连续的存储空间里，所构成的树的存储结构称为树的孩子链表。如：下列图示树的孩子链表如下图所示

树的孩子链表存储表示

typedef

struct

CTNode

{

//孩子结点

intchild;

struct

CTNode*next;

}*ChildPtr;typedef

struct{

ElemTypedata;

//结点的数据元素

ChildPtr

firstchild;

//孩子链表头指针

}

CTBox;

typedef

struct{

CTBox

nodes[MAX_TREE_SIZE];

intn,r;

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

}

CTree;

6.6.3树和森林的孩子兄弟表示法

树中每个结点都设有两个指针，

firstchild

指向该结点的“第一个”子树根结点，nextsibling

指向它的“下一个”兄弟结点。

森林可认为各棵树的根结点之间是一个“兄弟”关系因此无论树和森林都可以用这样的“二叉链表”表示。由于结点中的两个指针指示的分别为"孩子"和"兄弟"的关系，故称为"孩子-兄弟链表"。

6.6.4森林和二叉树的转换假设森林

F={T1,T2,…,Tn}，

其中第一棵树T1由根结点ROOT(T1)和子树森林{T11

,T12

,…,T1m

}构成。可按如下规则转换成一棵二叉树

B=(LBT,Node(root),

RBT

)：

若森林F为空集，则二叉树B为空树；否则，由森林中第一棵树的根结点

ROOT(T1

)复制得二叉树的根Node(root)，由森林中第一棵树的子树森林

{T11

,T12

,…,T1m

}转换得到二叉树中的左子树LBT，由森林中删去第一棵树之后由其余树构成的森林

{T2,T3,…,Tn}转换得到二叉树中的右子树RBT。

反之，对于任意一棵二叉树

B=(LBT,Node(root),RBT)，

可按如下规则转换得到由n棵树构成的森林

F={T1,T2,…,Tn}

若二叉树B为空树,则与其对应的森林F为空集；否则，由二叉树的根结点Node(root)

复制得森林中第一棵树的根结点ROOT()，由二叉树中的左子树LBT

转换构造森林中第一棵树的子树森林{T11

,T12

,…,T1m

}，由二叉树中的右子树RBT转换构造森林中其余树构成的森林{T2,T3,…,Tn}

。

由此，对树和森林进行的各种操作均可通过对"二叉树"进行相应的操作来完成，但同时也必须注意，此时的"二叉树"，其左、右子树和根结点之间的关系不再是它的"左、右孩子"，而是左子树是根的"孩子们"，右子树是根的"兄弟们"。

6.7树和森林的遍历

6.7.1树的遍历对树进行遍历可有两条搜索路径：

1.是从左到右

2.是按层次从上到下。树的按层次遍历类似于二叉树的按层次遍历，例如下图树按层次遍历所得访问的次序的为：ABCDEFGHIJK。类似于二叉树，在这条搜索路径上途径根结点两次，由对根的访问时机不同可得下列两个算法：

一、先根(次序)遍历树

若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树；

二、后根(次序)遍历树

若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点；

树进行从左到右遍历的搜索路径如下图所示。进行先根遍历所得结点的访问序列为：ABEHIJCDFGK进行后根遍历所得结点的访问序列为：HIJEBCFKGDA

如图