数据结构课件-树和二叉树

第六章树和二叉树基本内容

二叉树的概念、性质和存储结构；二叉树的遍历和线索化算法；树的定义、存储结构、树与二叉树的转换、树的遍历；哈夫曼树的构造；

学习要点

1．掌握二叉树的结构特性；

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

3．遍历二叉树是二叉树各种操作的基础。掌握各种遍历策略的递归算法，能灵活运用遍历算法实现二叉树的其他操作；

4．理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。

5．熟悉树的各种存储结构及其特点，掌握树与二叉树的转换方法，掌握树的遍历方法；

6．了解哈夫曼树的特性，掌握构造哈夫曼树和哈夫曼编码的方法。第六章树和二叉树6.1树的有关概念6.2二叉树6.3二叉树的遍历6.4树和森林6.5树与等价问题*6.6哈夫曼树及应用

6.1

树的有关概念1.树的概念2.树的应用3.树的表示树的有关术语5树的基本操作6.1树的定义和基本术语1．树的概念树结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有零个或多个直接后继。树是n个结点的有限集合，在任一棵非空树中：

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

（2）其余结点可分为m个互不相交的集合，而且这些集合中的每一集合本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFE例：下面的图是一棵树T={A,B,C,D,E,F,G,H,I,J}A是根，其余结点可以划分为3个互不相交的集合：

T1={B,E,F},T2={C,G},T3={D,H,I,J}这些集合中的每一集合都本身又是一棵树，它们是A的子树。

例如对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11={E}，T12={F}，T11,T12是B的子树。JIACBDHGFE从逻辑结构看：

1）树中只有根结点没有前趋；

2）除根外，其余结点都有且仅有一个前趋；3）树的结点，可以有零个或多个后继；

4）除根外的其他结点，都存在唯一一条从根到该结点的路径；5）树是一种分支结构JIACBDHGFE2．树的应用

1）树可表示具有分支结构关系的对象例1．家族族谱设某家庭有10个成员A、B、C、D、E、F、G、H、I、J，他们之间的关系可下图所示的树表示：例2．单位行政机构的组织关系JIACBDHGFE2）树是常用的数据组织形式

有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3计算机的文件系统

不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件12C3）问题的求解过程可用树结构的来描述

一些应用问题的求解过程可用树结构的来描述，以帮助程序员写出求解问题的程序或算法。

例4求集合的幂集

求集合A={1，2，3}的幂集显然集合A的所有子集即为该树的所有叶子结点，求集合A的幂集即为求该树的所有叶子。{1}{}{1,2}{1}{2}{}{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}{}集合中每个元素对于子集来说，要么属于该子集，要么不属于该子集例如1不属于{2，3}，左面的树从空集开始，构造集合的子集考虑元素1考虑元素2考虑元素33树的表示

1）图示表示

2）二元组表示

3）文氏图表示

4）凹人表示法（类似书的目录）

5）广义表表示

4.树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；树的高度：树中最大的结点层结点的度：结点子树的个数树的度：树中最大的结点度。叶子结点：也叫终端结点，是度为0的结点；分支结点：度不为0的结点；森林:互不相交的树集合；有序树：子树有序的树，如：家族树；无序树：不考虑子树的顺序；ABCDEFGHIJKLM结点A、D的度：3结点B、E的度：2结点C、H的度：1叶子：K，L，F，G，M，I，J度为0结点A为树的根结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先5树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);8）Value(T,&cur_e);9）Assign(T,cur_e,value);10）Paret(T,cur_e);11）LeftChild(T,cur_e);12）RightSibling(T,cur_e);13）InsertChild(&T,&p,i,c);14）DeleteChild(&T,&p,i);15）TraverseTree(T,Visit());

树是一种分支结构的对象，在树的概念中，对每一个结点的孩子个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树——二叉树。6.2二叉树6.2.1二叉树的定义二叉树：或为空树，或由根及两棵不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两棵子树；二叉树每个结点度小于等于2;2）左、右子树不能颠例——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;AGFEDCB

(a)、(b)是不同的二叉树，(a)的左子树有四个结点，(b)的左子树有两个结点，(a)AGFEDCB(b)AGFEDBC

2．二叉树的基本形态

φ3．应用举例例1可以用二叉树表示表达式

a+b*(c-d)-e/f-bf*a/+-dce6.2.2二叉树性质性质1在二叉树的第i层上最多有2i-1个结点。证明：用数学归纳法证明:

归纳基：

归纳假设：

归纳证明：i=1时，只有一个根结点。显然，2i-1=20=1

假定对所有的j,1≤j<i,命题成立，即第j层上至多有2j-1个结点。那么，可以证明j=i时命题也成立。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点个数为第i-1层上的最大结点数的2倍，即2*2i-2=2i-1。性质2深度为k的二叉树最多有2k-1个结点(k≥1)证明：深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。既为：20+21+…+2k-1=2k-1。性质3对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。1231145891213671014151234567证明：设二叉树中度为1的结点个数为n1根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点数为n0*0+n1*1+n2*2(分支数）而一棵二叉树中，除根结点外所有都为孩子结点，故该二叉树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1因此,有n=n0+n1+n2=n0*0+n2*1+n2*2+1，得到n0=n2+1。为继续给出二叉树的其它性质，先定义两种特殊的二叉树。

满二叉树深度为k具有2k-1个结点的二叉树，称为满二叉树。从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。123114589121367101415完全二叉树

如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，则称这棵二叉树为完全二叉树。从完全二叉树定义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右排列，若左边空一个位置时不能将结点放入右边。123114589126710完全二叉树1234567123456非完全二叉树从满二叉树及完全二叉树定义还可以知道，满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。深度为3的满二叉树和完全二叉树如图6-6所示。

A

G

F

E

D

C

B

A

E

D

C

B图6.6深度为3的满二叉树和完全二叉树

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个结点的完全二叉树高度为

log2(n)

+1或

log2（n+1）

。(注意

x

表示取不大于x的最大整数，也叫做对x下取整，

x

表示取不小于x的最小整数，也叫做对x上取整。)证明：设完全二叉树高度为k，则二叉树的前面k-1层为满二叉树，共有2k-1-1个结点而二叉树具有k层，第k层至少有1个结点，最多有2k-1个结点。因此有下面的不等式成立:(2k-1–1)+1≤n≤(2k-1-1)+2k-1即有2k-1≤n≤2k-1由式子后半部分可知,n≤2k-1…①由式子前半部分可知2k-1≤n…②由①有n+1≤2k，取对数得：log2(n+1)≤k故k≥log2(n+1),即k=

log2(n+1)

即得到第二个结论。由②有2k-1≤n，取对数得：k≤log2n+1即k=

log2n

+1，即第一个结论成立性质5.如果对一棵有n个结点的完全二叉树（深度为

log2n

+1

）的结点按层序编号（从第一层到第

log2n

+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。1231145891267106.2.3二叉树的存贮结构

1.二叉树的顺序结构完全二叉树的顺序结构用一组连续的内存单元，按编号顺序依次存储完全二叉树的元素 顺序结构图示1234567m-1

ABCDEF

①A

⑥F

⑤E

④D

③C

②B二叉树的顺序结构假想，我们补齐二叉树所缺少的那些结点，使其成为完全二叉树，对其结点编号。用这种方式对二叉树结点编号，则在二叉树中编号为i的结点，1）若有左孩子，则左孩编号为2i；

2）若有右孩子，则有孩子结点编号为2i+1；

3）若有双亲，则双亲结点编号为i/2；

A

F

G

E

D

C

B⑥⑧⑨②B①

A③C④

D⑤E⑦F⑩G12345678910m-1

AB

C

DE

F

G二叉树的顺序结构图示将二叉树原有的结点按编号存储到内存单元“相应”的位置上②B①

A③C④

D⑤E⑦F⑩G⑥⑨⑧2二叉链表二叉链表中每个结点至少包含三个域：数据域、左指针域、右指针域∧

D

A

B

∧C

∧∧

E

∧∧

F

∧二叉链表图示ABCDEF二叉链表类型说明

typedef

struct

Bitnode{

Telemtypedata;

struct

Bitnode*lchild,*rchild;}Bitnode,*Bitree;∧

D

A

B

∧C

∧∧

E

∧∧

F

∧二叉链表图示3三叉链表三叉链表中每个结点至少包含四个域：数据域、双亲指针域、左指针域、右指针域4

静态链表

上面的二叉链表或三叉链表是用指针实现的，是一种动态的链式存储结构，链式存储结构也可用一维数组来实现，用一维数组表示的二叉链表或三叉链表，称为静态链表孩子结点在数组中的位置0表示无左或右孩子静态二叉链表A13C05B00E00F00D4

0123456LchilddatarchildABCDEF6.3遍历二叉树和线索二叉树遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事。

二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每个结点，而且每个结点仅被访问一次？

6.3.1遍历二叉树二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：L：遍历左子树

D：访问根结点

R：遍历右子树

有六种遍历方法：

DLR，LDR，LRD，

DRL，RDL，RLD

约定先左后右,有三种遍历方法：

DLR，LDR,LRD，分别称为先序遍历（先根遍历）、中序遍历（中根遍历）、后序遍历（后根遍历）

A

F

G

E

D

C

B先序遍历（DLR

）

若二叉树非空

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

（3）先序遍历右子树；

先序遍历序列：A,B,D,E,G,C,F例：先序遍历右图所示的二叉树（1）访问根结点A（2）先序遍历左子树：即按DLR的顺序遍历左子树

（3）先序遍历右子树：即按DLR的顺序遍历右子树

A

F

G

E

D

C

B中序遍历（LDR

）若二叉树非空

（1）中序遍历左子树

（2）访问根结点（3）中序遍历右子树

中序遍历序列：

D,B,G,E,A,C,F例：中序遍历右图所示的二叉树

（1）中序遍历左子树：即按LDR的顺序遍历左子树

（2）访问根结点A

（3）中序遍历右子树：即按LDR的顺序遍历右子树

A

F

G

E

D

C

B后序遍历（LRD

）

若二叉树非空

（1）后序遍历左子树

（2）后序遍历右子树（3）访问根结点

后序遍历序列：

D,G,E,B,F,C,A例：后序遍历右图所示的二叉树

（1）后序遍历左子树：即按LRD的顺序遍历左子树

（2）后序遍历右子树：即按LRD的顺序遍历右子树

（3）访问根结点A

A

F

G

E

D

C

B后序遍历序列：abcd-*+ef/-表达式的逆波兰表示（后缀表达式）中序遍历序列：a+b*c-d-e/f

中缀表达式先序遍历序列：-+a*b-cd/ef

表达式的波兰表示（前缀表达式）例：先序遍历、中序遍历、后序遍历下图所示的二叉树-bf*a/+-dce这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分：1）基本项（也叫终止项）；2）递归项若二叉树非空（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；先序遍历递归定义递归项遍历的递归算法

上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例：先序遍历（DLR）的定义：该定义隐含着若二叉树为空，结束上面先序遍历的定义等价于：若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit()访问结点总是成功的。先序遍历递归算法

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

//采用二叉链表存贮二叉树，visit()是访问结点的函数。//先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit()if(T){

//若二叉树为空，结束返回

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

Visit(T->data)；

printf(e);

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);}//if

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

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

printf(e);

returnOK;}

∧

D

A

B

∧C

∧∧

E

∧∧

F

∧T先序遍历：preorder(p){if(p!=NULL){printf(p->data);

preorder(p->lchild);

preorder(p->rchild);}}abedcftree主程序(preorder(tree))printf(p->data);preorder(p->lchild);preorder(p->rchild);a^ab^printf(p->data);preorder(p->lchild);preorder(p->rchild);d^printf(p->data);preorder(p->lchild);preorder(p->rchild);bdprintf(p->data);preorder(p->lchild);preorder(p->rchild);ee2中序遍历递归算法

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

//采用二叉链表存贮二叉树，visit()是访问结点的函数。//中序遍历二叉树T，对每个数据元素调用函数Visit()

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

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

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

InOrderTraverse(T->rchild,Visit);

}//if}//InOrderTraverse

你能写出后序遍历递归算法了吧3后序遍历递归算法

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

//采用二叉链表存贮二叉树，visit()是访问结点的函数。//中序遍历二叉树T，对每个数据元素调用函数Visit()

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

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

PostOrderTraverse(T->lchild,Visit);

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

}//if}//PostOrderTraverse

非递归遍历中序非递归遍历∧

D

A

B

∧C

∧∧

E

∧∧

F

∧Tvoidinorder(BiTreeT){//二叉链表存贮二叉树

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

Printf(p->data);

Push(p->rchild);}//if}//while}//inorderTTBAD

∧TDTF非递归遍历先序非递归遍历∧

D

A

B

∧C

∧∧

E

∧∧

F

∧Tvoidpreorder(BiTreeT){//二叉链表存贮二叉树

InitStack(S);Push(S,T);while(!StackEmpty(S)){

while(GetTop(S,p)&&p){

Printf(p->data);Push(p->lchild);}//whilePop(S,p);//空指针退栈

if(!StackEmpty(S)){Pop(S,p);Push(p->rchild);}//while}//preorder非递归遍历后序非递归遍历∧

D

A

B

∧C

∧∧

E

∧∧

F

∧T

先序遍历和中序遍历，树中每个仅经过两次，后序遍历必须经过每个结点三次。遍历完左子树到达根结点和遍历完右子树到达根结点无法区别，因此需要加标志予以区别。遍历是二叉树的基本操作：二叉树许多操作可在遍历过程中完成，如二叉树线索化，就是在对二叉树进行遍历时加上线索的。本节再例子举几个二叉树遍历应用实例。

遍历的应用例1编写

求二叉树的结点个数的算法

输入：二叉树的二叉链表

结果：二叉树的结点个数基本思想：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。所以可在二叉树遍历的过程中，统计结点的个数。∧

D

A

B

∧C

∧∧

E

∧∧

F

∧Tvoidnodecoun(BiTreeT){//采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的结点//的个数。本算法在先序遍历二叉树的过程中，统计结点的个数//第一次被调用时，n=0

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

//若二叉树不为空，在先序遍历二叉树的过程中，//统计结点的个数n=n+1;

nodecoun

(T->lchild);

nodecoun

(T->rchild);}//if}//nodecoun

voidnodecoun(BiTreeT){//采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的结点个数。//本算法在先序遍历二叉树的过程中，统计结点的个数第一次被调用时，n=0if(T){//若二叉树为空，结束返回

//若二叉树不为空，在先序遍历二叉树的过程中，统计结点的个数

visi(T->data);n=n+1;

nodecoun(T->lchild);

nodecoun(T->rchild);}//if}//nodecoun

viod

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

//采用二叉链表存贮二叉树，visit()是访问结点的函数。//先序遍历二叉树T，对每个数据元素调用函数Visit()

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

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

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//if}//PreOrderTraverse比较先序遍历算法和计算结点算法，有什么相同和不同？结构类似函数名不同访问结点时调用visit()访问结点时统计结点的个数例2为二叉树建立二叉链表输入：二叉树的先序序列

结果：二叉树的二叉链表

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

D

A

B

∧C

∧∧

E

∧∧

F

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

A

F

E

D

C

B*******

A

F

E

D

C

BStatusCreateBiTree(BiTree&T){//输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字//符）按先序遍历的顺序，建立二叉链表，并将该二叉链表根结点指针//赋给T

scanf(&ch);if(ch==‘*’)T=NULL;//若ch==‘*’则T=NULL返回else{//若ch!=‘*’if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//建立（根）结点

CreateBiTree(T->lchild);//构造左子树链表,并将左子树根结点指针

//赋给（根）结点的左孩子域

CreateBiTree(T->rchild);//构造右子树链表，并将右子树根结点指针//赋给（根）结点的右孩子域}

returnOK;}//CreateBiTree例3、二叉树拷贝voidCopyTree(t,s)//源s,目的：t{if(s!=NULL){ T=(BiTNode*)malloc(sizeof(BiTNode)); t->data=s->data;

CopyTree(t->lchild,s->lchild);

CopyTree(t->rchild,s->rchild);}elset=NULL;}小结1二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；2二叉树既可以用顺序结构存储，也可用链式结构存储；3遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树，本课程介绍了三种遍历算法：先序遍历、中序遍历、后序遍历；习题十1P386.2、6.3、6.5、6.6、6.7、6.82对P396.15给出的二叉树求出以下的遍历序列：（1）先序序列（2）中序序列（3）后序序列3P396.15（上完线索二叉树后完成）习题取自数据结构题集C语言版严尉敏等编清华大学出版社第六章习题一6.3.2线索二叉树

遍历是二叉树最基本最常用的操作。

1）对二叉树所有结点做某种处理可在遍历过程中实现；

2）检索（查找）二叉树某个结点，可通过遍历实现；

与线性表相比，对二叉树的遍历存在如下问题：1）遍历算法要复杂的多，费时的多；2）为检索或查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；

如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。

如何将二叉树线性化？

以中序遍历为例，我们看到通过遍历可以得到二叉树结点的中序序列。若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。

中序遍历序列：D,B,H,E,A,F,C,G在中序序列中，D的后继是B，H的前趋是B，后继是E…

A

G

H

E

D

C

B

F线索二叉树孩子指针前趋指针后继指针加上结点前趋后继信息（线索）的二叉树称为线索二叉树线索链表

线索二叉树的存贮方法：

为每个结点增加二个指针域。

缺点：要占用较多的内存空间。

n个结点的二叉链表，有n+1个空指针域，故可利用这些空指针域存放结点的前趋和后继指针，以这种结点的构成二叉链表称为线索链表T∧

D∧

A

B

C

∧

F

∧∧

H∧

E

∧∧

G

∧线索链表的类型说明typedef

enum{link,thread}PointerTag;//link=0,thread=1typedef

struct

BiThrNode{

TElemTypedata;

Struct

BiThrNode*lchild,*rchild;//左右指针域

PointerTag

Ltag,Rtag;//左右标志域，标志域为0时，表示左右指//针域存储的是左右孩子的指针，标志域为1时，表示左右指针域存储的//是前趋后继结点的指针}BiThrNode，*BiThrTreelchild

LtagdataRtag

rchildF11E01G10D01A00B00H11C00线索链表图示线索二叉树

A

G

H

E

D

C

B

F孩子指针前趋指针后继指针

A

G

H

E

D

C

B

F二叉树的线索化线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索。前驱或后继的信息在遍历时才可以得到。因此线索化即是在遍历的过程中修改空指针。

先序线索化算法：VoidPreorderthread(BithrTreeP){if(p){if(!p->lchild){

p->lchild=pre;//调用Preorderthread之前给赋空值

p->ltag=1;}//if

if(!p->rchild)p->rtag=1;//右孩子为空，rchild一定是线索

if(pre&&pre->rtag==1)pre->rchild==p;//修改p的前驱的右指针pre=p;//p为pre的后继

if(p->ltag==0)Preorderthread(p->lchild);//左子树线索化

Preorderthread(p->rchild);//右子树线索化}//if}//Preorderthread

A

G

H

E

D

C

B

F线索二叉树的遍历在线索二叉树中，树的结点已经线索化了，所以遍历时，从第一个结点开始，然后依次找结点的后继，直到后继为空。

在先序线索二叉树中：1）第一个结点是二叉树的根结点；2）若p所指结点的右孩子域为线索，则p的右孩子域所指结点即为后继结点；3）若p所指结点的右孩子域为孩子指针，则p的后继结点为其左孩子结点。

A

G

H

E

D

C

B

F在中序线索二叉树中：1）第一结点，是二叉树的最左下结点；2）若p所指结点的右孩子域为线索，则p的右孩子结点即为后继结点3）若p所指结点的右孩子域为孩子指针，则p的后继结点为其右子树的最左下结点；

A

G

H

E

D

C

B

F

后序线索二叉树的遍历比较复杂。1）第一结点，是二叉树的最左下结点；2）若p所指结点的右孩子域为线索，则p的右孩子结点即为后继结点；3）若p所指结点的右孩子域为孩子指针，则p的后继结点需要进行后序遍历才能确定。

A

G

H

E

D

C

B

F为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点

约定：

头结点的lchild域：存放线索链表的根结点指针；

头结点的rchild域:中序序列最后一个结点的指针；

中序序列第一结点lchild域指向头结点;

中序序列最后一个结点的rchild域指向头结点;F11E01G11D11A00B00H11C0001头结点如图标出的中序二叉树结点的顺序，可看出1）中序序列的第一结点，是二叉树的最左下结点；2）若p所指结点的右孩子域为线索，则p的右孩子结点即为后继结点；3）若p所指结点的右孩子域为孩子指针，则p的后继结点为其右子树的最左下结点；F11E01G11D11A00B00H11C0001头结点①②③

中序遍历序列：D,B,H,E,A,F,C,G线索二叉树的插入

先看二叉树的插入，规定要插入的二叉树缺一棵子树，例如，无左子树。设X为要插入的二叉树的根，Y为被插入的二叉树的根，Y有左、右子树。1)若X作为Y的左子树，则X->lchild=Y->lchild;Y->lchild=X;2)若X作为Y的右子树，则X->lchild=Y->rchild;Y->rchild=X;

在线索二叉树中，插入、删除操作均破坏线索树的线索，修复线索和重新线索几乎有相同的代价。因此，仅考虑插入一个结点的情况。例：中序线索二叉树，在Y结点的右孩子位置上插入X。

我们分两种情况讨论：1）Y无右孩子，将X作为Y的右孩子插入到树中，影响Y和Y原来后继之间的关系。需要执行以下四组语句：

(1)X->rtag=Y->rtag;X->rchild=Y->rchild;//Y的后继作为X的后继(2)X->ltag=1;X->lchild=Y;//X的前驱为Y(3)Y->rtag=0;Y->rchild=x;//X为Y的右孩子(4)if(X->rchild)and(X->rchild->ltag=1)X->rchild->lchild=x;//原来

Y的后继的前驱改为X

2）Y有右孩子，将X作为Y的右孩子插入到树中。需要执行以下四组语句。

(1)X->rtag=Y->rtag;X->rchild=Y->rchild;//Y的右孩子作为X的右孩子(2)X->ltag=1;X->lchild=Y;//X的前驱为Y(3)Y->rtag=0;Y->rchild=x;//X为Y的右孩子(4)q=X->rchild;while(q->ltag==0)q=q->lchild;q->lchild=X;//原来Y的后继的前驱改为XY有右孩子和Y无右孩子的不同在第四组语句。小结以中序遍历为例，将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。加上结点前趋后继信息（线索）的二叉树称为线索二叉树；6.4树和森林

6.4.1树的存贮结构

1双亲表示法双亲表示法：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。用一组连续的内存单元存储树的结点，每个结点包含两个域：一个数据域，一个“指针域”，用于指示其双亲结点在数组中的位置。双亲表示类型定义#defineMAX_TREEE_SIZE100typedef

struct

PTNode{

TelemTypedata;

intparent;//双亲位置域}PTNode;typedef

struct{

PTNodenodes[MAX_TREE_SIZE];

Intn;//结点数}Ptree;IACBDHGFE双亲表示图示A-1B0C0D0E1F1G2H3I3012345678.dataparent9T.nodesT.n结点数双亲结点在数组中的位置-1表示无双亲2、孩子表示法孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。

与双亲表示法相反，孩子表示法适合实现涉及孩子的操作。还可以将双亲表示与孩子表示法结合：带双亲的孩子链表。

方法1：多重链表(类似二叉链表）

两种方式：定长结点不定长结点定长结点

优点结点结构一致，便于实现树的操作。缺点是浪费一些内存。

不定长结点

优点：节省内存;缺点：不定长会使一些操作实现复杂一些方式2：孩子链表孩子链表：对树的每个结点用线性链表存贮它的孩子结点树的孩子链表类型定义typedef

struct

CTNode{//孩子结点

intchild;

struct

CTNode*next;}*ChildPtr;typedef

struct{

TElemTypedata;

ChildPtr

firstchild;//孩子链表头指针}CTBox;typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

Intn,r;//结点数和根的位置；}CTree;IACBDHGFE13∧245∧8∧6∧790T.nodesT.nT.rdatafirstchildA

B

C

D

E∧F∧G∧H∧I∧

012345678…99结点的孩子结点链表结点数和根的位置3孩子兄弟表示法

孩子兄弟表示法用二叉链表作为树的存贮结构

孩子兄弟表示法类型定义

typedef

struct

CSNode{

TElemTypedata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree;IACBDHGFEAIHDGFCEB树的孩子兄弟表示法图示B的第一个孩子结点B的右兄弟结点IACBDHGFE此二叉链表既是树(a)的孩子兄弟表示又是二叉树(b)的二叉链表(a)(b)由此可将树与二叉树对应起来AIHDGFCEBFIABDHGCE6.4.2树与二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。树与二叉树转换方法树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子IACBDHGFEFIABDHGCE6.4.3树和森林的遍历1.树的遍历

先根遍历先访问根，然后依次先根遍历根每一颗子树。

例先根遍历序列

ABEFCGDHI后根遍历依次后根遍历根的每一颗子树，然后访问根。

后根遍历序列

EFBGCHIDA树的先根遍历对应二叉树的先根遍历；树的后根遍历对应二叉树的中根遍历。不论是先根遍历还是后根遍历都是对树按深度方向的遍历，也可按宽度方向（按层）遍历树。IACBDHGFE2.森林的遍历森林：树的集合

将森林中树的根看成兄弟，可用树的孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；一种方法是可用二叉树的遍历方法对森林进行遍历；另一种方法是可以直接对森林进行遍历。IACBDHGFE包含两棵树的森林JLKNMOPIACBDHGFEJLKNMOPFIABDHGCEPONMLKJ

1）先序遍历若森林非空，则（1）访问森林中第一棵树的根结点（2）先序遍历第一棵树中根结点的子树森林（3）先序遍历除去第一棵树之后剩余的树构成的森林序列：ABEFCGDHIJKMNPLOFIABDHGCEPONMLKJ

2）中序遍历若森林非空，则（1）中序遍历森林中第一棵树的根结点的子树森林（2）访问第一棵树的根结点（3）中序遍历除去第一棵树之后剩余的树构成的森林序列：EFBGCHIDAMPNKOLJFIABDHGCEPONMLKJ小结二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换；习题十一6.19,6.20,6.21

习题取自数据结构题集C语言版严尉敏等编清华大学出版社第六章习题二6.6哈夫曼树及其应用6.6.1哈夫曼树及构造1哈夫曼树的概念路径:从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；路径长度：路径上的分支数目称为路径长度；结点的权：根据应用的需要可以给树的结点赋权值；结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度=树中所有叶子结点的带权路径长度之和；

通常记作WPL=

wi

Li哈夫曼树：假设有n个权值(w1,

w2,…,wn

)，构造有n个叶子结点的二叉树，每个叶子结点有一个wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。306015510153015306045510155601015455530WPL=5*1+10*2+15*3+30*3=160

WPL=5*3+10*3+15*2+30*1=105WPL=5*2+10*2+15*2+30*2=120

2应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例编制一个将百分制转换成五分制的程序。最直观的方法是利用if语句来的实现。

if(i<60)printf(‘E’)elseif(i<70)printf(‘D’)elseif(i<80)printf(‘C’)elseif(i<90)printf(‘B’)elseprintf(‘A’)a<60a<90a<80a<70EYNDYNCYNBYNA判定过程可用二叉树描述。如果这个程序很不经常使用，或要转换的分数不多，不必考虑该程序效率，我们可以按照这个流程编程。如果该程序经常要使用或数据量很大。比如对几十万学生的分数进行转换，在这种情况下，要考虑转换程序的效率。

设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下：分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.10考虑转换程序的效率,我们可以构造5个叶子结点的哈夫曼树,如下图:等级分数段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.1070

a<80a<60CYNBYNDYNEYNA80

a<9060

a<70a<80a<70a<60a<90EYNDYNCYNBYNA按最初的图的判定过程，转换10000个分数所需的总比较次数=31500

若将学生成绩在5个等级以上的分布比例看作描述判定过程二叉树叶子结点权值，构造哈夫曼树

（0.05

1+0.15

2+0.4

3+0.3

4+0.1

4）

正是该哈夫曼树的带权路径长度。可见要想获得效率较高的转换程序，可构造以分数的分布比例为权值的哈夫曼树。转换10000个分数所需的总比较次数=220004030601551015301003哈夫曼树的构造构造哈夫曼树的步骤：1．根据给定的n个权值，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合2．在F中选取两棵根结点权值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和；3．从F中删除这两棵树，并将新树加入F；4．重复2、3，直到F中只含一棵树为止；403060155101530403060155101530100例：构造以W=（5，15，40，30，10）为权的哈夫曼树。3051015404030155101540303015510156.6.2哈夫曼编码1.哈夫曼编码哈夫曼树除了能求解最优判定问题解，还用于其他一些最优问题的求解。这里介绍用哈夫曼树求解数据的二进制编码。在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。例如：邮局发电报、数据压缩，发送方将原文转换成二进制字符串，接收方将二进制字符串还原成原文。原文----

电文（二进制字符串）-----

原文例要传输的原文为ABACCDA

设ABCD的编码为

A；00

B；01

C：10

D：11发送方：将ABACCDA转换成00010010101100接收方：将00010010101100还原为ABACCDA1).等长编码

每个字符都有相同长度的二进制编码。我们上面的例子是一个等长编码的例子。*优点：译文容易。*缺点：报文长。若某种文字有n个字符，每个字符的编码为k位，则：

K=log2(n+1)

例如：英文字母26个，若要等长的给每个字母一个编码，则需要5位二进制。2).不等长编码

每个字符具有长度不同的二进制编码。在电报通讯的例子中，我们总希望电文长度尽可能的短。在数据压缩时总希望压缩比尽可能的大。

采用不等长的编码，并且让字符串中出现频率大的字符的编码尽可能的短，则电文的（字符串的编码）总长度即可减少，但这时会出现编码的唯一性问题。如果：A,B,C,D的编码分别为：0，00，1，01则：上述电文：000011010共9位，长度减少。但是译文困难。前面的连续四个0，可以译成AAAA,BB,ABA。不唯一。

3).前缀编码

任一字符的编码都不是另一个字符编码的前缀。如果我们的不等长编码是前缀编码，则问题就解决了。前缀编码可以用二叉树来设计。方法：1）字符放在叶结点上。2）树中度为1的结点个数为0。3）左右分支的编码分别为0，1。4）从根结点到叶结点的路径上各分支的字符组成的二进制串作为叶结点的编码。

A:0B:10C:11用这种方式得到的编码是前缀编码。BCA例某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，利用二叉树设计一种不等长编码：1）构造以a、b、c、d、e、f、g、h为叶子结点的二叉树；2）将该二叉树所有左分枝标记0，所有右分枝标记1；3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；acbdgfeha:0000b:0001c:0010d:0011e:010f:011g:10h:11应用中每个字符的使用频率是不一样的。显然，为使传输的二进制串尽可能的短，使用频率高的字符用较短编码，使用频率低的字符用较长的编码。如何使得电文最短呢？这就希望常用的字符编码尽可能的短。统计语言各个字符的使用频度Wi，利用哈夫曼树就可以对这种语言定义出一种最优的编码，使

WiLi最小（电文最短）。如何得到使二进制串总长最短的编码？2．哈夫曼编码

目的：得到使报文最短的前缀码表

途径：构造哈夫曼树依据：字符的使用频度

设：有8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11。构造以字符使用频率作为权值的哈夫曼树。将权值取为整数w=(5,29,7,8,14,23,3,11)，按哈夫曼算法构造的一棵哈夫曼树如下：对应字符的编码a:0110b:10c:1110d:1111e:110f:00g:0111h:01029195842100158735811231429*哈夫曼树的应用

1）报文到电文的译码

a)从根出发

b)取一位报文，若取完，译码结束。c)若报文=1，向右分支行进一个结点若报文=0，向左分支行进一个结点

d)若所得结点不是叶结点，转b)e)若所得结点是叶结点，则字符即为译码结果，得到一个字符，转a)

例：报文：111010001100100111

cbfehg29195842100158cgadhfeb2）产生前缀码表

a)找一个待编码的叶结点，没有此结点，算法结束。

b)找该结点的双亲，如果无双亲，一个字符编码完成，转a)。c)有双亲，确定该结点是双亲的左（右）孩子，得到一位编码值。

d)以双亲为当前结点，转b)见