第6章 树教学课件

第6章树

・2二叉树

6.3遍历二叉树

第六章树

第6章树

树形结构是一种应用十分广泛和重要的非线性数据结

构，是一种以分支关系定义的层次结构。在这种结构中，

每个数据元素至多只有一个前趋，但可以有多个后继；数

据元素之间的关系是一对多的层次关系。树形结构主要用

于描述客观世界中具有层次结构的数据关系。

本章重点讨论树与二叉树的概念、性质、存贮结构及

其各种运算，并研究一般树、森林和二叉树的转换关系；

此外，作为树形结构的应用，介绍了哈夫曼树及其哈夫曼

编码。

第六章树

ti6.1树的基本概念

6.1.1树的定义及表示

1、树形结构示例

张红军

(a)一个家族结构示意图

第六章树

校长办公室

计算机学院科研处人事处财务处教务处

计算机系电信系数学系人事科劳资科教务科教材科

(b)行政结构树形示意图

6.1树形结构示意图

第六章树—

--------------__

■2、树的定义

树（Tree）是n（n>0）个结点的有限集合T,当n=0时不焉用树，

否则，称为非空树。在任一棵非空树中：

（1）有且仅有一个称为树根的结点。

（2）除根结点之外的其余结点可分为m（m>0）个互不相交的集

合TLT2,…，Tm,其中每一个集合本身又都是一棵树，一般称为

根的子树。

树的定义是一个递归的定义，它反映了树的固有特性，即一棵树

由若干棵子树构成，且各子树间互不相交，而每棵子树又由若干棵更

小的子树构成。例如，在图6.2中，（a）是只有一个根结点的树；（b）

是有8个结点的一般树，其中A是根，其余结点分成三个互不相交的子

集：T1={B、E、F},T2={C},T3={D、G、H},而且它们都是A的子

树，且其本身也是一棵树。

第六章树

(a)只有根结点的树(b)一般树

6.2树示例

树的表示方法有树形表示、集合表示、凹入表示和广义表等4种。图

6.3给出了树的其它表示形式，如(a)为集合表示法或范氏图法，(b)

为凹入表示法或缩格法，(c)为广义表表示法或嵌套括弧法等。

ni/〃/〃/〃〃/〃〃〃〃〃/“/,

D[〃〃/〃〃〃〃〃〃//

D|〃〃〃/〉必〃〃〃〃

E〃〃〃〃〃〃

I7177777777777

p[7777777777777777777(A(B(E,F),C,D(G,H)))

D1〃〃〃〃〃〃〃〃〃/

IcI卜I〃〃〃〃〃/

H

11!\?/〃//〃//〃//〃//〃if/

(a)集合表示(b)凹入表示(c)广义表表示

图6.3树的其它表示法

第六章树

|6.L2树的常用术语K*

树的结点：是指一个数据元素及若干指向其子树的分支，通常用一

个结构体或记录来描述，在树形表示中用一个圆圈及短线表示。

结点的度：是指结点的子树数目。

叶子或终端结点：是指度为零的结点。

分支结点或非终端结点：是指度不为零的结点。

树的度：是指树中各结点度的最大值。

有时，在实际应用中也引用家族树中的一些习惯用语来描述树，如

孩子、双亲、祖先、子孙和兄弟等。如将某结点的子树的根称为该结点

的孩子，相应地，将该结点称为孩子的双亲；同一个双亲的孩子之间互

称为兄弟等等。祖先则是从根结点到该结点所经过分支上的所有结点，

而以某结点作为根的子树中任一个结点都称为该结点的子孙。

第六章树________________________________

I

t结点的层次：从根开始定义，根为第一层，根的孩子为嚣三盘，

以此类推，即设根结点的层数为1,其余结点的层数等于其双亲结点的

层数加1。若某结点在第i层，则其孩子结点就在第i+1层。

树的深度或高度：是指树中结点的最大层次数。

路径：若树中存在一个结点序列瓦，k2,kj,使得ki是ki+1的

双亲(l<i<j),则称该结点序列是从k］到kj的一条路径，且路径的长

度为j-L即等于路径上分支的数目。在树形表示中，路径表示从kl出

发自上而下地通过k2，k3,与各结点。

有序树和无序树：若将树中每个结点的各子树看成是从左至右有序

且不能交换，则称该树为有序树，否则称为无序树。图6.4给出了两棵

不同的有序树。

，森林：是指m（m>0）棵互不相交的树的集合。

显然，树形结构不同于线性结构。在树中，一个结点至多个直

接前趋（双亲），却可以有多个直接后继（孩子），即结点之间的关系不

象线性结构中的结点关系是一一对应关系，而是呈现出一对多的层次关系。

第六章树

树的基本运算i9W

(1)setnull(T)：置T为空树，即初始化一棵树T。

(2)root(T)或root(x)：求根函数。

(3)parent(T,x)：求双亲函数。

(4)child(T,x,i)：求孩子结点函数。

(5)rsibling(T,x)：求右兄弟函数。

(6)create(x,F)：建树函数。

(7)delchild(x,i)：子树删除操作。

(8)addchild(y,i,x)：插入子树操作。

(9)traverse(T)：树的遍历操作。

第六章树

6.2二叉树

二叉树(BinaryTree)是另一种重要的树形结构，在

实际应用中具有重要的意义。本节将详细地讨论二叉树的

定义、重要性质、存储方式、运算及其应用。

第六章树

6.2.1二叉树的概念及运算

1、二叉树定义

二叉树是n(>0)个结点的有限集合，这个集合可以是空集合，

或者由一个根结点和两棵互不相交的分别称为根的左子树和右子树

的二叉树组成。显然，由定义可知，二叉树具有递归性质，它的特

点是每个结点至多只有二棵子树即二叉树中任何结点的度数不大于2,

而且，二叉树的子树有左右之分，其次序不能任意颠倒。应该指出

的是，二叉树与树是两个不同的概念，它不是树的特殊情形，例如，

在图6.5中，(a)和(b)所示的两棵二叉树虽然与(c)所示的一般

树相似，但却不等同于这棵一般树。

第六章树

(a)二叉树1(b)二叉树2(c)一般树

图6.5二叉树与度为2的一般树的区别举例

第六章树

2、二叉树基本形态

（a）空树（b）只有根结点（c）只有左子树（d）只有右子树（e）左

空

图6.6二叉树的五种基本形态

两种特殊形态的二叉树：满二叉树和完全二叉树。

第六章树

T)满二叉树是指一棵深度为h且有2人1个结点的二叉前，笳露.7(a)

T所示是一棵深度为3的满二叉树。

(2)完全二叉树：对满二叉树中的结点按照从根结点起，自上而下，

自左至右的约定进行连续编号，一棵深度为h,有n个结点的二叉树，当且

仅当其每一个结点都与深度为h的满二叉树中的编号从1至n的结点一一对应

时，称之为完全二叉树，如图6.7(b)所示为一棵深度为3的完全二叉树，

而图6.7(c)所示就不是完全二叉树。

(3)满二叉树的每一层上具有最大的结点数，它不存在度为1的结点，

所有叶子结点均在第h层上。

(4)完全二叉树的特点是所有叶子结点都只可能在最大的两层出现，

第i(i0h-l)层含有2口个结点，第h层上的结点都集中在该层最左边的位置

上，换句话说，完全二叉树上的结点编号与同深度的满二叉树对应位置的

结点编号相同。满二叉树是完全二叉树的特殊情形，它一定是完全二叉树，

而完全二叉树不一定是满二叉树。

第六章树

(c)非完全二叉树

第六章树

二叉树的基本运算

(1)setnull(bt)：置bt为空二叉树-

(2)求根函数root(bt)或root(x)(3)求双亲函数parent(bt,x)

(4)求孩子结点函数Ichiki(bt,x)和rchild(bt,x)

(5)插入运算addlchild(b,x,y)和addrchild(bt,x,y)

(6)二叉树建立运算create(x,Ibt,rbt)

(7)删除子树运算dellchild(bt,x)和delrchild(bt,x)

(8)遍历运算traverse(bt)

第六章树

6.2.2二叉树的性质.

性质1在二叉树的第i层上至多有2H结点(应1)。

性质2深度为h的二叉树至多有2»1个结点(h>l)o

性质3对任何一棵二叉树T,如果其终端结点数为%,度为2的结点数为吗，

则n0=n2+lo

性质4具有n个结点的完全二叉树的深度为|_log2n」+l。

性质5如果对一棵有n个结点的完全二叉树(其深度为,按照

从根结点起，自上而下，从左到右的约定对所有结点从1到n进行编号，

则对于任意的编号为i的结点(l<i<n)有以下性质：

(1)如果i=L则结点i是二叉树的根，无双亲；如果i>l,则其双亲的

编号是㈤2」。

(2)如果2i>n,则结点i无左孩子(结点i为叶子结点)，否则其左孩子

的编号是2i。

(3)如果2i+l>n,则结点i无右孩子，否则其右孩子的编号是2i+L

(4)若i为奇数且不为1,则该结点左兄弟的编号是i・L否则无左兄弟。

(5)若i为偶数且小于n,则该结点右兄弟的编号是i+L否则无右兄弟。

第六章树

J|623二叉树的存储结构

1.顺序存储结构

二叉树的顺序存储是用一组地址连续的存储单元存储二叉树中的数

据元素。

(1)完全二叉树

对一棵具有n个结点的完全二叉树，从树根结点起，自上层到下层，

每层自左至右地给所有结点编号，然后将完全二叉树中的所有结点按编

号顺序依次存储在一维数组R[L..n]中，如图6.8(a)所示。

(2)一般二叉树

一般二叉树也必须按完全二叉树的形式来存储一般二叉树中的结点,

只有通过添加一些并不存在的“虚结点”，使之成为完全二叉树的形式

才行，如图6.8(b)所示。

在最坏的情况下，一个深度为h且只有h个结点的右单支树需要2L1

个的结点空间。所以，不宜采用顺序存储结构存储一般的二叉树。

A#B###C

(b)一般二叉树及其顺序存储结构

图6.8二叉树的编号及其顺序存储结构

!第六章树

2.链式存储结构，?N^

1(1)二叉链表

采用链式存储结构来存储二叉树，而且设计不同的结点结构可以构

成不同形式的二叉树的链式存储结构。二叉树的结点由一个数据元素

和分别指向其左、右子树的两个分支构成，所以，二叉树的链式存储

结构中的结点至少应包含三个域：数据域和左、右指针域，即每个结

点应包含两个指针Ichild和rchild,分别指向该结点的左孩子和右孩子。

其结点结构形式如图6.9所示。

Ichilddatarchild

图6.9二叉链表结点结构

第六章树

结点类型定义：

typedefstructnode

{datatypedata；/*数据域*/

structnode*lchild,*rchild；/*左、右孩子域*/

}btnode,*bitree；

在一棵二叉树中，所有类型为btnode的结点，加上一个指向

根结点的头指针，就可构成二叉树的链式存储结构，有时将这种

存储结构称为二叉链表，如图6.10所示。一个二叉链表可以由头

指针唯一地确定。

采用二叉链表作为二叉树的链式存储结构便于从根结点开始

往下搜索孩子或子孙结点。

第六章树

root

(a)二叉树(b)二叉链表

图6.10二叉树的链式存储结构

第六章树

(3)三叉链表

有时，为了便于检索结点的双亲或祖先结点，可在结点中

增加一个指向其双亲结点的指针域(如图6.11(a)中的parent),这

种结构称为三叉链表，如图6.11所示即为图6.10(a)中二叉树所对应

的三叉链表。

(a)三叉链表结点结构(b)三叉链表

图6.11二叉树的三叉链表

第六章树

二叉树的简单运算实现

这里所讨论的运算实现算法，以二叉链表作为其存储结构。

(1)置空二叉树setnun(bt)

voidsetnull(bitreebt)

{bt->lchild=NULL；/*左链域置空*/

bt->rchild=NULL；/*右链域置空刃

}

(2)求二叉树的根root(bt)

datatyperoot(bitreebt)

{if(bt->lchild==NULL)

returnNULL；/*空树时返回NULL*/

else

return(bt->lchild->data)；/*否则返回根结点数据域的值*/

)

[第六章树.

(3)建立二叉树操作create(x,Ibt,rbt)

bitreecreate(datatypex,bitreeIbt,bitreerbt)

{bitreep；

p=(bitree)malloc(sizeof(btnode))；

/*申请一个结点空间，地址传给p指针*/

p->data=x；

p->lchild=lbt；/*把二叉树Ibt填入p的左孩子链域*/

p->rchild=rbt；/*把二叉树rbt填入p的右孩子链域*/

returnp；/*返回建成的二叉树*/

)

(4)插入左孩子addlchild(bt,x)

voidaddlchild(bitreebt,datatypex)

{bitreep；

p=(bitree)malloc(sizeof(btnode))；/*申请一个结点空间*/

p->data=x；

p->lchild=NULL；

p->rchild=NULL；/*左、右孩子域置空*/

第六章树

(5)删除左孩子dellchild(bt)

voiddellchild(bitreebt)

{bitreep；

p=bt->lchild；/*保存左子树指针*/

bt->lchild=NULL；/*bt的左孩子域置空*/

free(p)；/*释放左子树空间*/

第六章树

6.3遍历二叉树

在实际应用中，常常要求在二叉树中检索或查找具有某种特征的

结点，或者对二叉树中的所有结点逐一地进行某种处理，这就提出了

一个遍历二叉树的问题，即如何按某条搜索路径巡访二叉树中的每个

结点，使得每个结点都被访问且仅被访问一次。可以说，遍历操作的

实质就是使非线性结构线性化。

若以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，

贝I」有DLR、LDR、LRD、DRL、RDL和RLD六种遍历次序。显然，前

三种遍历次序和后三种是对称的，若约定先左后右，则只有前三种情

况即DLR、LDR和LRD,分别称为前序遍历、中序遍历和后序遍历。

■第六章树._______

6.3.1遍历二叉树的递归算法—

假设二叉树采用二叉链表作为存储结构，对根结点的访问是输出结点数

据，以上三种遍历运算的递归定义及算法如下：

L前序遍历(PreorderTraversal)

若二叉树为空，则遍历结束，否则进行如下操作：

(1)访问根结点；

(2)前序遍历根结点的左子树；

(3)前序遍历根结点的右子树。

前序遍又称之为先根遍历或先序遍历。其递归算法描述如下：

voidpreorder(bitreebt)

{if(bt)

{printf(“％d\t”，bt->data)；/*访问根结点，这里假设数据域为整型*/

preorder(bt->lchild)；/*前序遍历左子树*/

preorder(bt->rchild)；/*前序遍历右子树刃

)

)

第六章树

2.中序遍历(InorderTraversal)

若二叉树为空，则遍历结束，否则进行如下操作:

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。

中序遍历又称为中根遍历。算法描述如下：

voidinorder(bitreebt)

{if(bt)

{inorder(bt->lchild)；/*中序遍历左子树*/

printf(“％d\t”,bt->data)；/*访问根结点*/

inorder(btt->rchild)；/*市序遍历右子树*/

)

}

3,后序遍历(PostorderTraversal)

若二叉树为空，则遍历结束，否则进行如下操作:

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。.，

第六章树

,后序遍历也称为后根遍历。其递归算法描述如下：’

voidpostorder(bitreebt)

{if(bt)

{postorder(bt->lchild)；/*后序遍历左子树*/

postorder(bt->rchild)；/*后序遍历右子树*/

printf("%d\t”,bt->data)；/*访问根结点*/

}

}

从遍历递归算法的执行踪迹来看，这三种遍历的搜索路线相同，如图

6.12所示。只要分别将搜索路线上的所有在第一次、第二次和第三次经

过的结点收集，即可分别得到该二叉树的前序、中序和后序遍历序列。

第六章树

(a)遍历二叉树的搜索路线(b)遍历二叉树的的递归执行过程

图6.12遍历过程示意图

■第六章树.______

*叉树的三种遍历序列如下：.0

前序遍历序列：ABDCE

中序遍历序列：DBACE

后序遍历序列：DBECA

又如，一棵表达式二叉树如图6.13所示，对该表达式树进行前序、中

序和后序遍历，结果分别为：

前序遍历序列：-+a*bc/de

中序遍历序列：a+b*c-d/e

后序遍历序列：abc*+de/・

上述三种遍历序列都是线性序列，有一个开始结点和一个终端结点,

其余结点有且仅有一个前趋结点和一个后继结点。有时，为了区分树形

结构中的前趋结点和后继结点的概念，对以上三种线性序列，均在某结

点的前趋和后继之前加上其遍历次序的名称。

13表注式树

第六章树

632遍历二叉树的非递归算法

递归算法简洁精炼、可读性好、易理解，但其执行效率较低，但

有些程序设计语言不支持递归功能，所以，我们有必要讨论遍历二叉树

的非递归算法。

可以利用后来保存遍历过程中遍历的结点的左孩子和右孩子，从而

实现遍历二叉树的非递归算法。假定在每个算法中，s为用一维数组表

示的顺序栈，top为栈顶指针，P为临时变量，S栈的作用是保存待访问

结点的指针，S栈的深度要大于整个树的深度，即假设栈空间足够大，

不会出现栈满清况。

I第六章树—

卜序遍历二叉树的非递归算法

#defineM100.

voidpreorder(bitreebt)/*前序遍历二叉树的非递归算法*/

{bitreep,s[M]；

inttop=-l；

p=bt；

do

{while(p)

{printf("%d\t”,p->data);

if(p->rchild)

s[++top]=p->rchild；

)

if(top>=0)/*栈非空，退栈，使p指向右子树继续扫描右子树*/

p=s[top-]；

}while((top==-1)&&(p==NULL))；

I第六章树

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

voidinorder(bitreebt)/*中序遍历二叉树的非递归算法*/

{bitreep,s[M]；

inttop=-l；

p=bt；

do

{while(p)/*搜索最左下的结点，并将左孩子进栈*/

{s[++top]=p；

p=p->lchild；

)

if(top>=0)

{p=s[top-]；/*出栈，栈顶元素赋p*/

printf(“％d\t”，p->data)；/*访问根结点*/

p=p->rchild;/*p指向右子树，继续搜索右子树*/

)

}while((top==-1)&&(p==NULL))；

第六章树—

]3,后序遍历二叉树的非递归算法।

voidpostorder(bitreebt)/*后序遍历二叉树的非递归算法*/

{ints2[M],top=-l,flag；

bitreep,sl[M]；

p=bt；

do

{while(p)/*遍历其左子树*/

{sl|++topl=p；

s2[top]=0；/*p结点首次进栈*/

p=p->lchild；

)

if(top>=0)

{flag=s2[--top]；

p=sl[top]；

第六章树

if(flag==0)

{sl[top]=p；'

Ts2[++top]=l；/*p结点第二次进栈*/

p=p->rchild；

}/*遍历p结点的右子树*/

else

{printf(w%d\f\p->data)；/*访问根结点*/

p=NULL；

}

)

}while(top==-1)；

)

后序遍历的非递归算法也可以描述如下：

voidpostorder(bitreebt)/*后序遍历二叉树的非递归算法*/

{inttop=-l；

bitree^[M]；_____________

第六章树—

do

{while(p)

{top++；

s[top]=p；

if(p->lchild!=NULL)p=p->lchild；

elsep=p->rchild；

)

p=s[top]；

top—；

printf("％d\t"，p->data)；/*访问结点*/

while((top>=0)&&(s[top]->rchild==p))

{P=s[top];

top-

printf(66%d\tM,p->data)；

)

if(top>=0)p=s[top]->rchild；

}while(top==-l)；

■第六章树

T6.3.3二叉树的层次遍历

所谓层次遍历(LevelorderTraversal)是指从二叉树的根结点开始

从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个结点。

例如，对图6.12(a)的二叉树，按层次遍历得到的结点序列为ABCDE。

可利用一个队列结构来实现层次遍历，其做法是：

(1)首先将根结点入队列；

(2)当队列不空，从队列中取出队头结点访问它，并在其左右孩子非

空时，把它的左孩子和右孩子结点依次入队列；(3)反复执行(2),

直到队列为空时止。

第六章树

#defineMAXSIZE100

voidlevelorder(bitreebt)/*层次遍历二叉树bt*/

{bitreequeue[MAXSIZE]；/*定义队列*/

intfront,rear；/*定义队列指针*/

if(bt==NULL)/*如果是空树，则返回*/

return；

front=0；rear=0；/*队列指针初始化*/

queue[++rear]=bt；/*根结点入队*/

while(front!=rear)/*当队列不空*/

{front=(front+l)%MAXSIZE；/*队头结点出队*/

printf("%d\t"，queue[front]->data)；

if(queue[front]->lchild!=NULL)

{rear=(rear+l)%MAXSIZE；/*修改队尾指针*/

queue[rear]=queue[front]->lchild；

}

if(queue[front]->rchild!=NULL)

{rear=(rear+l)%MAXSIZE；/*修改队尾指针*/

queuefrear]=queue[front]->rchild；

第六章树

6.3.4二叉树的运算举例

遍历是二叉树各种运算的基础，利用各种遍历运算可以在遍

历过程中对结点进行各种操作，如求二叉树中某结点的双亲、孩

子和结点的层次等，也可以在遍历过程中生成结点，建立二叉树

的存储结构以及输出二叉树等。

第六章树

艮建立二叉树

例如，若要建立图6.14所示的二叉树的二叉链表，则按下列顺序

输入字符：AB（|）D（|）（|）C（|）（|）（其中巾表示空格字符，说明无子树）。显然,

该输入序列与二叉树的前序遍历序列相对应。算法描述如下：

bitreecreatebitree()

{bitreet；charch；

scanf(“％c”,&ch)；

if(ch==69)t=NULL；

else

{t=(bitree)malloc(sizeof(btnode))；/*生成根结点*/

t->data=ch；

t->lchild=createbitree()；/*建立左子树*/

t->rchild=createbitree()；/*建立右子树*/

)

return(t)；

)

第六章树

r一

上20t

/IA|\

一/।।।

AB\AcA

।、一

八|D|八

(a)二叉树(b)二叉链表

图6.14二叉树及其二叉链表

第六章树

2.求二叉树的叶子数目

可以在遍历过程中对所遇结点判断是否为叶子结点，若是则统计变

量加1,直到遍历完所有结点，叶子结点总数即可求得。下面给出利用中

序遍历求叶子结点数的递归算法：

intcountleaf(bitreebt)

{intnum=O;/*初始化统计变量*/

if(bt!=NULL)

if((bt->lchild==NULL)&&(bt->rchild==NULL))

num++;

else

num=countleaf(bt->lchild)+countleaf(bt->rchild);

returnnum;

)

■第六章树.______

翼叉树中结点的检索

以前序遍历来实现检索运算的递归算法。

bitreesearch(bitreebt,datatypex)

{if(bt!=NULL)/*如果二叉树bt非空刃

{if(bt->data==x)returnbt；/*如果根结点数据域值为x则返回bt*/

search(bt->lchild,x)；/*在左子树中检索*/

search(bt->rchild,x)；/*在右子树中检索*/

)

else

returnNULL；

)

第六章树

4.求二叉树的高度

利用后序遍历求二叉树高度的递归算法:

inttreedepth(bitreebt)

{inth,Ih,rh；

if(bt==NULL)h=0；

else

{lh=treedepth(bt->lchild)；

rh=treedepth(bt->rchild)；

if(lh>=rh)h=lh+l；

elseh=rh+l；

)

returnh；

第六章树

6.4线索二叉树

B।线索二叉树的概念

1、问题提出

遍历二叉树可以得到二叉树中结点的某个遍历次序序列，这实质上是

对一个非线性结构进行线性化的操作，使得除第一个和最后一个外的每个

结点在这些线性序列中有且仅有一个直接前趋和直接后继。然而，当二叉

树以二叉链表作为存储结构时，由于每个结点中只有指向其左、右孩子的

指针，所以，从任一个结点出发可以直接找到该结点的左、右孩子结点，

在一般情况下是不能直接得到该结点在某一遍历序列中的前趋和后继结点

的信息。那如何才能直接得到这些信息呢？

2、解决办法

(1)通过采用多重链表来表示二叉树的方法得到，即在每个结点中除

原来的左、右孩子的指针之外，增加两个指针指示结点在某一个遍历序列

中的前趋和后继结点。

第六章树

(2)通过遍历的方法，每当要求某结点在某一个遍历序列中的前趋和

后继结点的信息，就进行一次遍历。

(3)利用在有n个结点的二叉链表中的n+1个是空链域来存放结点在

某一个遍历序列中的前趋和后继结点的指针。

3、线索二叉树

有时也装种附加的指向其前趋和后继的指针称为线索(Thread),而

将加上了线索的二叉链表称为线索链表(ThreadLinkedList),相应的

加上线索的二叉树称为线索二叉树，对二叉树以某种次序遍历使其变为线

索二叉树的过程称为线索化。

第六章树

线索二叉链表的类型:

typedefenum{0,1}ptrtag；

typedefstructbithnode

{datatypedata；

structbithnode*lchild,*rchild；

ptrtagItag,rtag；/*标志域*/

}bithnode,*bithptr；

其中：ltag=0表示Ichild域为指向结点的左孩子的指针；ltag=l表示

Ichild域为指向结点其前趋的左线索；rtag=0表示rchild域为指向结点的右

孩子的指针；rtag=l表示rchild域为指向结点其后继的右线索。例如图

6.15(a)、(b)所示。

第六章树

(a)中序线索二叉树(b)中序线索链表

图6.15中序线索二叉树及其线索链表

第六章树

642线索二叉链表的建立

可以在对二叉树的某种次序遍历过程中，一边遍历一边建立线索,

若当前访问结点的左孩子域为空则建立前趋线索，若右孩子域为空则

建立后继线索。下面给出中序线索二叉链表的建立算法。

要建立中序线索二叉链表，可以对二叉树采用一边中序遍历一边

建立线索的方法，若在遍历过程中被访问结点的左孩子为空，则建立

前趋线索；若右孩子为空，则建立后继线索。算法描述如下：

第六章树

bithptrpre/*pre为全程量，初值为NULL*/

bithptrcreatinordthrd(bithptrroot)/*t指向二叉树的根*/

{voidinthrd()；

bithptrthrt；

thrt=(bithrtree)malloc(sizeof(bithrnode))；

thrt->ltag=O；

thrt->rtag=l；

thrt->rchild=thrt；

if(root==NULL)

thrt->lchild=thrt；

else

{thrt->lchild=root；

pre=thrt；

inthrd(root)；/*进行中序线索化*/

pre->rchild=thrt；

pre->rtag=l；

thre->rchild=pre;

)

returnthrt；—一

1—

第六章树

voidinthrd(bithptrroot)/*将二叉树root中序线索化*/

{if(root!=NULL)

{inthrd(root->lchild)；/*左子树线索化*/

if(root->lchild==NULL)root->ltag=l；/*建立左线索标志*/

if(root->rchild==NULL)root->rtag=l；/*建立右线索标志*/

if(pre!=NULL)/*pre为全程量，为root的前趋指针*/

{if(pre->rtag==1)

pre->rchild=root；/*pre无右子树*/

if(root->ltag==1)

root->lchild=pre；

}

pre=root；

inthrd(root->rchild)；/*右子树线索化*/

第六章树

■6.4.3遍历线索二叉树芸—

・在线索二叉树上进行遍历，只要从头结点出发反复查找结点前继,

直到又回到头结点时止。下面给出中序遍历中序线索二叉树的算法。

voidinordtraverse(bithptrroot)/*root为头结点指针*/

{bithptrp；

p=root->lchild；/*p指向根结点*/

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

{while(p->ltag==0)/*查找最左下的结点*/

p=p->lchild；

printf(66%c\tM,p->data)；

while((p->rtag==1)&&(p->rchild!=root))

{p=p->rchild；/*若右指针为线索，贝传递指针*/

printf("％c\t"，p->data)；/*访问结点*/

)

p=p->rchild；

)

<Back

第六章树

iI6.5树和森林

6.5.1树的存储结构

1.双亲表示法

可以在存储树中结点信息的同时，为每个结点增加一个指向其双亲

的指针parent。假设以一组地址连续的空间存储树的结点，则其类型说

明如下：

#defineMAXSIZE100

typedefstructnode

{datatypedata;

intparent;

Jptnode；

ptnodeT[MAXSIZE]；

第六章树

.

0123456789•••maxsize-1

dataABCDEFGHI・・・

parent-1011122244•••

(a)树(b)双亲表示

图6.16树的双亲表示

第六章树

2.孩子表示法

为树中每个结点的孩子建立一个单链表，一棵具有n个结点的树就有

n个孩子链表,并在每个结点中增加一个指针域，指向其孩子链表的表头，

这种孩子表示法也称为孩子链表表示法，其形式说明如下：

typedefstructnode

{datatypedata；

structnode*next；/*定义孩子链表头指针*/

}ctree;

ctreeT[MAXSIZE]；

孩子表示法便于实现对结点的孩子的运算，但不适合于对结点的双

亲进行运算。若要既便于实现涉及孩子又便于实现与双亲有关的运算，

可以考虑将双亲表示法与孩子链表表示法结合起来，形成双亲孩子链表

表不法。

第六章树

1D人

2G人

3

4

5

6

7

8

9

图6.17树的孩子链表表示

第六章树

1

2

3

4

5

6

7

8

9

图6.18树的双亲孩子链表表示

第六章树

♦孩子兄弟表示法

该方法又称二叉链表表示法，即以二叉链表做为树的存储结构，

链表中结点的两个指针域分别指向结点的第一个孩子结点和下一个右

兄弟结点，所以，有时也称为左孩子右兄弟表示法。其结构的类型说

明如下：

typedefstructnode

{datatypedata；

structnode*firstchild,*nextsib；

}cstnodc?*cstree；

利用这种存储结构庙于实现树的各种运算如查找结点的孩子等，

可借助二叉链表导出树与二叉树之间的确定对应关系，并利用二叉树

的有关算法来实现对树的各种运算。

第六章树

图6.19树的孩子兄弟表示法

第六章树

6.5.2树、森林与二叉树的转换

可借助二叉链表导出树与二叉树之间的确定对应关系。任何一个

森林或一棵树可以唯一地对应于一棵二叉树，而任何一棵二叉树也能

唯一■地对应到一■个森林或一1棵树上。

第六章树

■L树、森林转换为二叉树、》一,

「从树的孩子兄弟表示法中可以导出树与二叉树的对应关系，的树中

每个结点最多只有一个最左边的孩子和一个右邻的兄弟，按照这种关系,

就可以将一棵树转换为二叉树。

图6.20树转换为二叉树

森林转换为二叉树：先将森林中的每一棵树转换为二叉树，再将第一

棵树的树根作为转换后二叉树的根，第一棵树的左子树作为转换后二叉

树的左子树，第二棵树作为转换后的二叉树的右子树，第三棵树作为转

如此进行，直纱转脸宅:上匕

第六章树

AEA

森林与二叉树转换

CDFHE

C

树与二叉树转换

DH

E

I

H

K

C

K

图6.21树、森林与二叉树的相互转换示意图

第六章树

・二叉树转换成森林

若二叉树非空，则将二叉树的根及其左子树作为转换后的第一棵树的

二叉树形式，剩下的二叉树的右子树又可以看作是由一个森林转换后的二

叉树，可以利用同样的方法进行转换，如此类推，直到最后产生一棵没有

右子树的二叉树为止，这样就得到了森林。

若想进一步得到树，可以利用树的孩子兄弟表示法的逆方法，即根据

结点本身、结点的右孩子、右孩子的右孩子、…，原本都是同一个双亲的

兄弟这个性质将二叉树转换为树。

显然，上述定义是递归定义，容易写出相互转换的递归算法。同时，

利用树、森林与二叉树的相互转换，对树和森林的运算也可转换成二叉树

的运算来实现。

第六章树

・3树和森林的遍历

对于树和森林，根据访问根结点的次序可分为前序遍历和后序遍历

两种方法。

L树的遍历

(1)树的前序遍历

树的前序遍历也称作先根遍历或先序遍历，其递归定义为：

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

(2)树的后序遍历

树的后序遍历也称作后根遍历，其递归定义为：

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

例如，对图6.16(a)中所示的树进行先序遍历，可得前序遍历序列

为：ABEFGCDHI

若对其进行后序遍历，则可得后序遍历序列为：EFGBCHIDA

第六章树_________________________________

I

2.森林的遍历.—

i按照森林和树的相互递归的定义，可以得到森林的两种遍历方法。

(1)森林的前序遍历

森林的前序遍历即依次按前序次序遍历森林中的每一棵树，其形式化

的递归定义为：若森林非空，则先访问森林中第一棵树的根结点，然后前

序遍历第一棵子树中根结点的子树森林，再前序遍历除第一棵树之外剩余

的树构成的森林。

(2)森林的后序遍历

后序遍历即依次按后序次序遍历森林中的每一棵树，其形式化递归定

义为：若森林非空，则先后序遍历森林中第一棵树的根结点的子树森林，

然后访问第一棵树的根结点，再后序遍历除第一棵树之外剩余的树构成的

森林O

何如，对图6.21中的森林进行前序和后序遍历，其结果为：

前序遍历序列：ABCDEFGHIK

后序遍历序列：BCDAFEHKIG

第六章树

.6.6哈夫曼树

哈夫曼（Huffman）树又称最优二叉树，是一类带权路径长度最短

的二叉树，有着广泛的应用。本节先讨论哈夫曼树（最优二叉树）的概

念，然后讨论它的应用及其算法实现。

6.6.1基本术语

1.路径和路径长度

树中两个结点之间的路径，是指从树中一个结点到达另一个结点之

间的分支。

将路径中所经过的分支数称为这两个结点之间的路径长度，它等于路

径上的结点数减1,即等于路径上分支的数目j-1。

将从树根到每一个结点的路径长度之和定义为树的路径长度。

第六章树

2.结点的权和带权路径长度

.在许多实际应用中，常为树中的结点赋于一个有某种意义祥照，

称之为该结点的权。

将结点的带权路径长度规定为从树根结点到该结点之间的路径长度

与该结点权值的乘积。

3.树的带权路径长度

树的带权路径长度(WeightedPathLength)为树中所有叶子结点

的带权路径长度之和，通常记为：

n

W尸L=>wz.Zz-

£=1

其中，n表示带权叶子结点的数目，Wj表示叶子用的权值，L表示

由树的根到叶子结点ki之间的路径长度。

例如，图6.22计算每一棵二叉树的带权路径长度WPL分别为：

第六章树

图6.22具有不同带权路径长度的二叉树

(a)WPL=7X3+1X3+2X2+5X1=33

(b)WPL=1X3+2X3+5X2+7X1=26

(c)WPL=1X2+7X3+2X4+5X4=51

第六章树

4,哈夫曼树

哈夫曼树(HuffmanTree)是指由n个带权叶子结点构成的所有

二叉树中带权路径长度WPL最小的二叉树，又称最优二叉树。相应的,

其构造算法称为哈夫曼算法。

对于具有n个其权值分别为Wjw2,Wn的带权叶子结点的二

叉树来说，其形态可以有许多种，其中能被称为哈夫曼树的二叉树是

不唯一的，但其最小的WPL是确定的，而且在叶子数目及权值相同的

二叉树中，完全二叉树不一定是最优二叉树。一般情况下，在哈夫曼

树中，权值越大的叶子结点离根结点越近。

第六章树

6.6.2哈夫曼算法

(1)根据给定的n个权值{wLw2,…，wn)构成n棵二叉树的森林

F={T1,T2,…，Tn},其中每棵二叉树Ti(IWiWn)都只有一个权值为wi的

根结点，其左、右子树均为空；

(2)在森林F中选出两棵根结点的权值最小的二叉树作为一棵新的二

叉树的左、右子树，且置新的二叉树的根结点的权值为其左、右子树上根

结点的仅值之和；

八(3)从森林F中删除这两棵二叉树，同时将新得到的二叉树加入到F中;

(4)重复(2)和(3)步骤，直到F中只含一棵二叉树为止，此二叉

树便是所构造的哈夫曼树。

例如，上例中由4个带权为7,1,2,5的叶子结点A,B,C,D,根据

哈夫曼算法构造其对应哈夫曼树的过程如图6.23所示。

第六章树

15

71257

(a)(b)(c)(d)

图6.23哈夫曼树的构造过程

第六章树

6.6.3哈夫曼编码

哈夫曼算法的应用很广泛，本节以远距离电报通讯中的编码为例来

说明它的应用。

(1)编码和译码

在电报通讯中，需要将欲传送电文中的字符转换成由二进制的0、1

序列，然后进行传送，并在接收端将收到的二进制串转化为对应的字符

序列。一般的，编码的方法有等长编码和不等长编码等。等长编码即为

每个字符编制的二进制码的码长相同。

(2)等长编码

例如，电文为“ABACCDA”，由于其中出现的字符只有四种，所以

只需两个字符的二进制串便可分辨。若将其等长编码设计为：A：00,B：

01,C：10,D：11,则上述七个字符的电文便为“00010010101100”，

总长度14位，接收端接收并进行译码时，可按二位一分割译码即可得相

应的电文。显然，利用等长编码方法进行编码，译码方便，但编码所得

到的码串过于冗长。

第六章树

(3)不等长编码

如上例中，A、C字符出现的次数较多，这样可以设计字符A、B、C、

D的编码分别为0、00、1和01,则上述共7个字符的电文可编码为总长度

为9的二进制字符串“000011010”。显然，其编码总长度大幅度减少，但

在译码时会带来麻烦。例如，在接收端接收到的二进制串中前四个字符

的子串“0000”就可有多种译法，可以是“AAAA”，或是“ABA”，也可

以是“BB”等，显然是不合适的，原因在于以上编码不是前缀编码因而

在译码时会产生多义性。

(4)前缀编码

若利用不等长编码，要求字符集中任一个字符的编码都不能是其它

字符编码的前缀，这种编码称做前缀编码(PrefixCode)。可以利用二叉树

来设计二进制的前缀编码。用叶子结点表示要编码的字符，并约定左分

支为‘0"右分支为'「，然后就可以用从根到叶子结点的路径上分支字

符组成的串作为该字符的编码，这样得到的编码必为二进制前缀编码。

第六章树

01

0

0

©

图6.24前缀编码示例

第六章树

(5)哈夫曼编码.、一

S假设每种字符在电文中出现的次数为巧，其编码长度为L，电文中有n

种字符，则电文总长度应为WJ+W2I2+…+wj=0对应到二叉树上,

n可以看作是二叉树中叶子结点的个数，Wj可以着作是叶子结点的权值，I

恰为从根结点到叶子结点Kj的路径长度，显然，设计电文总长度最短的二

进制前缀编码即是构造以字符出现频率作为权值的具有n个叶子结点的哈

夫曼树，由此所得到的二进制前缀编码称为哈夫曼编码(Huffman

Code)o

例，假设电文中出现5个字符A、B、C、D、E,已知它们在电文中

出现的频率是9、3、7、6、1,利用｛9,3,7,6,1｝为权值构造的哈夫曼

树如图6.25所示，其编码分别为：A：00,B：100,C：01,D：11,E：

101o

哈夫曼树也可以用来译码，译码时从根结点出发，按二进制位串中的

0和1确定是进入左分支还是进入到右分支，当到达叶子结点时便可译出该

叶子对应的字符，若电文未完，则回到根结点继续进行译码。

第六章树

26

9376196

@@©@©

(a)

图6.25哈夫曼树及哈夫曼编码

第六章树

6.6.4哈夫曼算法的实现■

1.哈夫曼树的构造算法

用一个大小为2n・l的一维数组构成静态链表来存放哈夫曼树中的结点。

如图6.26所示的静态链表。其中data为数据域,Ichild为左孩子指针域,

rchild为右孩子指针域,parent为双亲指针域,’0,表示空指针。

dataIchiIdrchilddataIchildparentrchild

A231A203

B452B415

C673C617

D004D020

E005E020

F006F030

G007G030

(a)二叉树(b)二叉静态链表(c)三叉静态链表

第六章树

结点结构描述:

typedefstruct

{floatweight；/*数据域用于存放权值*/

intIchild,pa