数据结构第06章-树和二叉树

第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用6.1树的定义和基本术语1.树的逻辑定义是由n(n≥0)个结点组成的有限集合T。在任意一个非空树中：有且仅有一个特定的称为根的结点；n>1时，其余结点可以分为m（m>0）个互不相交的有限集T1,T2,T3,…,Tm，其中每一个集合本身又是一棵树，且称为根的子树。树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它说明了树的特性。如在右图中，是只有一个根结点的树是有13个结点的树其中A是根，其余结点分成三个互不相交的子集：T1={B，E，F，K，L},T2={C，G},T3={D，H，I，J，M}；

T1,T2,T3

都是A的子树，且本身也是一棵树。则同理按此分析方式分析T1,T2,T3。AABCDEFGHIJKLM2.树的其它表示方法嵌套集合：是一些集合的集体，对于其中任何两个集合，或不相交，或一个包含另一个的形式表示。广义表表示：根作为由子树森林组成的表的名字写在表的左边。凹入表示：类似书的编目。GCABDHIJEKFLA*****************B****************E***************F***************K**************L**************C****************G***************D****************H***************I***************J***************(A(B(E,F(K,L)),C(G),D(H,I,J)))ABCDEFGHIJKL3.树的基本术语结点：数据元素+若干指向其子树的分支；结点的度：结点拥有的子树数；树的度：树中所有结点的度的最大值；叶子结点：度为零的结点，或称为终端结点；分支结点：度大于零的结点，或称为非终端结点；结点的层次：假设根结点的层次为1,若某结点在第i层，则其子树的根在第i+1层；ABDEFHIJKM树的深度：树中叶子结点所在的最大层次；孩子结点：结点的子树的根；相应地该结点称为孩子的双亲结点；兄弟结点：同一个双亲的孩子之间称为兄弟结点；祖先：从根到该结点所经分支上的所有结点；子孙：子树中任一结点；ABDEFHIJKM3.树的基本术语有序树、无序树子树之间是否存在次序关系？将树中结点的各子树看成从左至右是有次序的(即不能互换)称有序树，否则称无序树；森林：是m（m≥0）棵互不相交的树的集合。任何一棵非空树是一个二元组

Tree=（root，F）其中：root被称为根结点，F被称为子树森林；ABDEFHIJKM3.树的基本术语4.树结构和线性结构的比较

第一个数据元素（无前驱）

最后一个数据元素（无后继）

其它元素（一个前驱、一个后继）

根结点（无前驱）

多个叶子结点（无后继）

其它结点（一个前驱、多个后继）

线性结构树结构5.树的抽象类型定义ADTList{数据对象D：是具有相同特性的数据元素的集合数据关系R：数据关系R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系：

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

(2)若D-{root}!=Φ，则存在D-{root}的一个划分D1，D2，…，Dm(m>0)，对任意j≠k(1≤j，k≤m)有Dj∩Dk=Φ，且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di，有<root，xi>∈H；5.树的抽象类型定义ADTList{数据关系R：

(3)对应于D-{root}的划分，H-{<root，x1>，…，<root，xm>}有唯一的一个划分H1，H2，…，Hm(m>0)，对任意j≠k(1≤j，k≤m)有Hj∩Hk=Φ，对任意i(1≤i≤m)，Hi是Di上的二元关系，(Di，{Hi})是一棵符合本定义的子树，称为根root的子树。基本操作：}ADTList树的基本操作1）Root(T);初始条件：树T存在；操作结果：返回T的根2）Value(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点操作结果：返回cur_e的值3）Parent(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则其函数值为“空”。4）TreeDepth(T);

初始条件：树T存在；操作结果：返回T的深度。5）LeftChild(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则其函数值为“空”6）RightSibling(T,cur_e);

初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则其函数值为“空”7）TreeEmpty(T);

初始条件：树T存在操作结果：判别T是否为空树8)TraverseTree(T,Visit());

初始条件：树T存在。Visit是对结点操作的函数。操作结果：按某种次序对T的每个结点调用函数

Visit()一次且至多一次9）InitTree(&T);

操作结果：构造空树T10）Assign(&T,cur_e,value);

初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值value。11）DestroyTree(&T);

初始条件：树T存在操作结果：销毁树T第6章树和二叉树6.1树的定义和基本术语6.2二叉树

6.2.1二叉树的定义

6.2.2二叉树的性质

6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用6.2.1二叉树的定义或者为空树；或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。二叉树的五种基本形态二叉树的常用操作某些操作和树的基本操作类似，另由于二叉树本身特性，增加的操作有：

RightChild(T,e);

初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子，否则其函数值为“空”。

LeftSibling(T,e);

初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左兄弟，若e是T的左孩子或无左兄弟，则返回“空”。PreOrderTraverse(T,Visit());先序遍历InOrderTraverse(T,Visit());中序遍历PostOrderTraverse(T,Visit());后序遍历LevelOrderTraverse(T,Visit());层序遍历6.2.2二叉树的性质性质1：

在二叉树的第i层上至多有2i-1个结点（i≥1）（利用归纳法容易证得此性质）423156789101112131415性质2：深度为K的二叉树上至多含2K-1个结点（K≥1）（证明用求等比级数前k项和的公式）1234423156789101112131415性质3：对任一棵二叉树，若它含有n0个叶子结点，n2个度为2的结点，则必存在关系式：

n0=n2+1证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数B=n1+2n2而B=n-

1=n0+n1+n2-1由此，n0=n2+1231456789满二叉树：深度为k且含有2k-1个结点的二叉树42315678910111213141542315678完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。4231567891011121314154231567891011(a)(b)(c)完全二叉树的特点(1)叶子结点只可能在层次最大的两层上出现；(2)对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次必为L或L+1。性质4：具有n个结点的完全二叉树的高度为

└

log2n┘+1423156789101112证明：设完全二叉树的高度为h，则有(2h-1-1)<n

(2h-1)

或2h-1

n<2h

两边取对数h-1log2n<h

因为h是整数，所以h=└log2n┘+1

性质5：

具若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点：若

i=1，则该结点是二叉树的根，无双亲,否

则，编号为└i/2┘的结点为其双亲结点;423156789101112性质5：

若2i

>

n，则该结点无左孩子，否则，编号

为2i的结点为其左孩子结点；若2i+1

>

n，则该结点无右孩子结点，否则

，编号为2i+1的结点为其右孩子结点。4231567891011126.2.3二叉树的存储结构

（1）二叉树的顺序存储表示（2）二叉树的链式存储表示1.二叉树的顺序存储表示

#defineMAX_TREE_SIZE100

//二叉树的最大结点数

typedefTElemTypeSqBiTree[MAX_TREE_SIZE];

//0号单元存储根结点

SqBiTreebt;

按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。423156789101112123456789101112数组下标：0123456789101123145678123045600708

一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。顺序存储结构的性能分析顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2k-1的一维数组。这样就造成存储空间的浪费。3011556602614红字为对应结点在顺序结构中相应的位置下标2.二叉树的链式存储结构

由二叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据和左、右指针域。DATALChildRChildParent二叉树的结点DB^C^^E^^F^AECBDF二叉链表lchildDatarchildA^二叉树的二叉链表存储表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;

//左右孩子指针}BiTNode,*BiTree;parentAECBDF三叉链表rchildDatalchildBD^C^E^^F^^A^^二叉树的三叉链表存储表示typedefstructTriTNode{TElemTypedata;structTriTNode*lchild,*rchild;

//左右孩子指针

structTriTNode*parent;//双亲指针}TriTNode,*TriTree;

在不同的存储结构中，实现二叉树的操作方法亦不同，如找结点x的双亲PARENT(T，e)，在三叉链表中很容易实现，而在二叉链表中则需从根指针出发巡查。由此，在具体应用中采用什么存储结构，除了根据二叉树的形态之外，还应考虑需进行何种操作。总结

本讲我们学习了树和二叉树的定义，重点介绍了二叉树的性质和存储结构，二叉树是非常重要的数据结构，请同学们重点掌握，在下一讲中我们将学习二叉树的遍历和线索化操作。练习题1.假设在树中，结点x是结点y的双亲时，用(x,y)表示树边。已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}，用树形表示法画出此树，并回答：(1)哪个是根结点?(2)哪是叶结点?(3)哪个是g的双亲?(4)哪些是g的祖先?(5)哪些是g的孩子?(6)哪些是e的子孙?(7)哪些是e的兄弟?哪些是f的兄弟?(8)结点b和n的层次各是多少?(9)树的深度是多少?(10)以结点c为根的子树的深度是多少?(11)树的度数是多少?2.一个深度为h的满k(k>=2)叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：

(1)各层的结点数目是多少?(2)编号为i(i>1)的结点的双亲结点(若存在)编号是?(3)编号为i的结点的第j个孩子结点(若存在)编号是?(4)编号为i的结点有右兄弟的条件是?Ki-1└i+(k-2)/k┘k*i+(j-(k-1))(i-1)%k≠0第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树

6.3.1遍历二叉树

6.3.2线索二叉树6.4树和森林6.6赫夫曼树及其应用6.3.1遍历二叉树

在二叉树的一些应用中，常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就提出了遍历二叉树的问题。提出问题：“遍历”是任何类型均有的操作

对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)；

而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历，即按什么样的搜索路径遍历的问题。

对二叉树而言，是由三个基本单元组成：根结点、左子树和右子树。因此，若能遍历这三部分，便是遍历了整个二叉树。考虑：一共有多少种遍历二叉树的方案？则有DLR

、LDR

、LRD

、

DRL

、RDL

、RLD

先序中序后序六种遍历方案选择假如以L、D、R分别表示遍历二叉树的左子树、访问根结点、遍历右子树，1.先左后右的遍历算法先（根）序遍历算法：若二叉树为空树，则空操作；否则，访问根结点；先序遍历左子树；先序遍历右子树。中（根）序遍历算法：若二叉树为空树，则空操作；否则，中序遍历左子树；访问根结点；中序遍历右子树。后（根）序遍历算法：若二叉树为空树，则空操作；否则，后序遍历左子树；后序遍历右子树；访问根结点。例

:先（根）序的遍历序列为：中（根）序的遍历序列为：后（根）序的遍历序列为：a+/-*efcdb--+a*b–cd/efa+b*c–d–e/fabcd-*+ef/-例：假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK。画出该二叉树。先序遍历二叉树的递归算法StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//二叉链表存储结构，visit是对数据元素操作的应用函数//先序遍历二叉树T的递归算法，对每个数据元素调用visitif(T){if(Visit(T->data))

if(PreOrderTraverse(T->lchild,Visit)if

(PreOrderTraverser(T->rchild,Visit))

returnOK;returnERROR;}elsereturnOK;}//先序遍历ACBD主程序Pre(T)Pre(TR);Pre(TR);TAVisit(A);Pre(TL);TDVisit(D);Pre(TL);TCVisit(C);Pre(TL);TBVisit(B);Pre(TL);返回T>Pre(TR);返回T>返回T>返回T>返回T>Pre(TR);得到的遍历次序为：ABDC中序遍历二叉树的递归算法：

StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))

{if(T){if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}后序遍历二叉树的递归算法：

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

if(T){

if(PostOrderTraverse(T->lchild,Visit))

if(PostOrderTraverse(T->rchild,Visit))if(Visit(T->data))returnOK;

returnERROR;}elsereturnOK;}递归算法执行过程中递归工作栈的状态变化如图，根据其状态变化可以直接写出相应的非递归算法。例：从中序遍历递归算法执行过程中递归工作栈状态可见：(1)工作记录中包含两项，其一是递归调用的语句编号，其二是指向根结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指向左子树根的指针进栈；(2)若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层即栈顶记录中指针所指的根结点；(3)若是从右子树返回，则表明当前层的遍历结束，应继续退栈。从另一角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。中序遍历二叉树的非递归算法一：StausInOrderTrav(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍历二叉树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);}//if}//whileReturnok;}//InOrderTraverse中序遍历二叉树的非递归算法二：StatusInOrderTrv(BiTreeT,Status(*Visit)(TElemTypee))//采用二叉链表存储结构，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;}//else}//whilereturnOK;}//InOrderTrv//根指针进栈，遍历左子树//根指针退栈，访问根结点，遍历右子树2.遍历算法的应用举例

“遍历”是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对于一棵已知树求结点的双亲，求结点的孩子结点，判定结点所在的层次等。例1：统计二叉树中叶子结点的个数StatusCountLeaf(BiTreeT,int&count){if(T){if((T->lchild==NULL)&&(T->rchild==NULL)){count++;returnOK;}CountLeaf(T->lchild,count);//统计左子树中叶子结点个数

CountLeaf(T->rchild,count);//统计右子树中叶子结点个数

}elsereturnERROR;}例2：求二叉树的深度intDepth(BiTreeT){if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+max(depthLeft,depthRight);}returndepthval;}例3：按先序序列建立二叉树的二叉链表已知先序序列：ABC00DE0G00F000（其中0表示空格字符）建立相应的二叉链表。ABCDEFG例3：按先序序列建立二叉树的二叉链表StatusCreateBiTree(BiTree&T){//按先序序列输入二叉树中结点的值，空格字符表示空树

Scanf(&ch)if(ch==’

’)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//构造根结点

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

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

}ReturnOK}从前面的讨论得知：遍历二叉树就是以一定的规则将二叉树中的结点排列成一个线性序列。这实质上就是对一个非线性结构进行线性化操作，使得每个结点在这些线性序列中有且只有一个前驱和后继。如何保存这种在遍历过程中得到的信息呢？总结本讲介绍了二叉树的遍历。由于树结构可以表示为二叉树的形式（在下一讲学习），在二叉树的某种存储结构上对二叉树进行遍历可以进一步实现对树的结点的处理，因此，二叉树的表示与遍历是十分重要的基本操作，希望大家重点掌握。第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树

6.3.1遍历二叉树

6.3.2线索二叉树6.4树和森林6.6赫夫曼树及其应用6.3.2线索二叉树1.何谓线索二叉树？遍历结果是求得结点的一个线性序列。指向该线性序列“前驱”和“后继”的指针，称“线索”；包含“线索”的存储结构，称为“线索链表”；与其相应的二叉树，称为“线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。2.线索链表中结点的结构在二叉链表的结点结构中增加两个标志域，并规定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示结点的左孩子1lchild域指示结点的前驱RTag=0rchild域指示结点的右孩子1rchild域指示结点的后继二叉树二叉线索存储表示typedefenum{Link,Thread}PointerThr;

//Link==0:指针，Thread==1:线索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;

//左右孩子指针

PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;3.线索二叉树图例

线索二叉树及其存储结构（a）中序线索二叉树（b）中序线索链表1234567010020131141050161171thrt0

1如何在线索树中找结点的后继？结合中序线索树若其右标志为“1”，右链是线索，右链直接指示了结点的后继；若其右标志为“0”，右链是指针，其后继为右子树中最左下的结点。1234567如何在线索树中找结点的前驱？结合中序线索树

若其左标志为“1”，左链为线索，直接指示其前驱；若其左标志为“0”，左子树中最右下的结点为其前驱。1234567线索链表的中序遍历算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向头结点，头结点的左链lchild指向根结点，中序遍历

//二叉线索树T的非递归算法，对每个数据元素调用函数Visit。

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;}returnOK;}//IOTraver_T010020131141050161171T0114.如何建立线索化链表？

由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。对二叉链表p进行中序线索化的递归算法(带头结点)StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)步骤：1.生成头结点Thrt，如果树非空，头结点指向树根，否则，回指自身；2.pre=Thrt;调用不带头结点的中序线索化的递归算法;3.最后一个结点线索化（指向头结点）voidInThreading(BiThrTreep){

if(p){

InThreading(p->lchild);

//左子树线索化

if(!p->lchild){p->lchild=pre;p->ltag=Thread;}//前驱线索

if(!pre->rchild){pre->rchild=p;pre->rtag=Thread;}//后继线索

pre=p;//保持pre指向p的前驱

InThreading(p->rchild);

//右子树线索化

}}InThreading

对二叉链表p进行中序线索化的递归算法(不带头结点)0100203

4050

6

7

pre0

1pStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。

Thrt=(BiThrTree)malloc(sizeof(BiThrNode));if(!Thrt)exit(OVERFLOW);Thrt->ltag=Link;

Thrt->rtag=Thread;//建立头结点

Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;//空树，左指针回指自身

else{//二叉树不为空树，进行线索化

Thrt->lchild=T;//头结点的lchild指向二叉链表根

pre=Thrt;//pre指向前驱结点

InThreading(T);

//中序线索化二叉链表Tpre->rchild=Thrt;

pre->rtag=Thread;

//最后一个结点线索化

Thrt->rchild=pre;}returnOK;}StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){Thrt=(BiThrTree)malloc(sizeof(BiThrNode));

if(!Thrt)exit(OVERFLOW);Thrt->ltag=Link;Thrt->rtag=Thread;Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;//空树，Thrt回指自身

ThrtLinkThread1else{Thrt->lchild=T;//头结点的lchild指向二叉链表根

pre=Thrt;//pre指向前驱结点

InThreading(T);

//中序线索化二叉链表Tpre->rchild=Thrt;

pre->rtag=Thread;

//最后一个结点线索化

Thrt->rchild=pre;

}returnOK;}

ThrtABDCEpre输出：BCAED10111110000preP=nullTABDECFG例：对下图的树按先序、后序、中序线索化第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林

6.4.1树的存储结构

6.4.2森林与二叉树的转换

6.4.3树和森林的遍历6.6赫夫曼树及其应用6.4.1树的存储结构三种常用的链表结构：双亲表示法孩子表示法孩子兄弟表示法1.

双亲表示法即以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。DACREBFHGK双亲结点下标9876543210666311000-1KHGFEDCBAR树的双亲表存储表示#defineMAX_TREE_SIZE100typedefstructPTNode{//结点结构

Elemdata;intparent;//双亲位置域}PTNode;typedefstruct{//树结构

PTNodenodes[MAX_TREE_SIZE];intr,n;//根结点的位置和结点个数}PTree;分析：这种存储结构利用每个结点（除根结点）只有唯一双亲的性质，Parent(T,x）操作可在常量时间内实现。反复调用Parent操作，直到遇见无双亲的结点时，便找到了树的根。但在这种表示方式中，求结点的孩子时需遍历整个结构。2.孩子表示法由于树中每个结点可能有多棵子树，则考虑用多重链表，即结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式：datadegreechild1child2…childdydatachild1child2…childdx采用第一种格式多重链表中的结点是同构的，其中dx为树的度。由于树中很多结点的度小于dx

，所以链表中有很多空链域，造成空间浪费。datachild1child2…childdx采用第二种格式

多重链表中的结点是不同构的，其中

dy为结点的度，drgee

域的值同dy，此时可以节省存储空间，但操作不方便。datadegreechild1child2…childdy有没有既能节省空间又操作方便的办法呢？另一种方式把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空)。而n个头指针又组成一个线性表，为便于查找，采用顺序存储结构。3^6^51^2078^9^K^H^G^EFR^DC^BA0123456789DACREBFHGK树的孩子链表存储表示typedefstructCTNode

{//孩子结点

intchild;

structCTNode*next;}*ChildPtr;typedefstruct{

//双亲结点结构

Elemdata;

ChildPtrfirstchild;//孩子链的头指针}CTBox;typedefstruct{//树结构:

CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根结点的位置}CTree;分析：与双亲表示法相反，孩子表示法便于涉及孩子的操作实现，却不适用于Parent(T，x)操作。可根据某种需要，将二者结合起来，即带双亲的孩子链表。3.孩子兄弟表示法或称二叉树表示法，或称二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。^R^E^^K^^C^FAB^G^H^D^DACREBFHGK3.孩子兄弟表示法例：树的二叉链表（孩子-兄弟）存储表示typedefstructCSNode{Elemdata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;分析：这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。如果为每个结点增设一个(parent)域，则同样能方便地实现Parent(T,x)操作。6.4.2森林和二叉树的转换1.树和二叉树的对应关系由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。树转换为二叉树方法：1）对每个孩子进行从左到右的排序；2）在兄弟之间加一条连线；3）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；4）以根结点为轴心，将整个树顺时针转45°。ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId2.森林和二叉树的对应关系从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId已知条件：森林和二叉树的对应关系设森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);

二叉树B=(LBT,Node(root),RBT);由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ;否则，由Root(T1)对应得到Node(root);

由(t11,t12,…,t1m)对应得到LBT;

由(T2,T3,…,Tn)对应得到RBT。由二叉树转换为森林的转换规则为:若B=Φ,则F=Φ;否则，由Node(root)对应得到Root(T1);

由LBT对应得到(t11,t12,…，t1m);T1除根以外所构成的森林由RBT对应得到(T2,T3,…,Tn)；除T1之外的森林6.4.3树和森林的遍历1.树的遍历：有三条搜索路径先根(序)遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根(序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历：若树不空，则自上而下自左至右访问树中每个结点。例对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：ABCDEGHFIABEFCDGHIEFBCGHIDA2.森林的遍历先序遍历(对森林中的每一棵树进行先根遍历)1）若森林不空，访问森林中第一棵树的根结点；

2）先序遍历森林中第一棵树的子树森林；

3）先序遍历森林中(除第一棵树外)其余树构成的森林。后序遍历(对森林中的每一棵树进行后根遍历)1）若森林不空，后序遍历森林中第一棵树的子树森林；

2）访问森林中第一棵树的根结点；

3）后序遍历森林中(除第一棵树外)其余树构成的森林。例：对森林进行先序遍历，获得的先序序列是：对森林进行后序遍历，获得的后序序列是：BCDEGHFIBEFCDGHIEFBCGHID总结：1.二叉树的线索化2.树的表示及其遍历操作；3.建立森林与二叉树的对应关系。由于在树和森林中，一个结点的孩子的个数不定，它们在计算机中的表示以及在各种操作计算机中的算法实现均不易实现，因此将树和森林表示为二叉树，并将对树和森林的操作转化为对二叉树的操作是通常采用的方法。1）假设一棵二叉树的中序序列为DCBGE

AHF

IJK和后序序列为DCEGBFHKJIA。

画出该二叉树。2）线索二叉树是一种（）结构。

A、逻辑B、物理C、线性3）试找出分别满足下面条件的所有二叉树。

A、先序序列和中序序列相同；

B、后序序列和中序序列相同；

C、先序序列和后序序列相同；树和二叉树的习题第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用6.6赫夫曼树及其应用1.基本术语1）路径和路径长度若一棵树中存在一个结点序列k1,k2,…,kj，使得ki是kj的双亲（0<i<j），则称此结点序列是从ki～kj的路径。从k1～kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1。ABCDEFG

在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，称其为该结点的权。结点的带权路径长度（WPL)规定为从树根到该结点之间的路径长度与该结点上权的乘积。acbd7398例：结点c的路径长度为2，其WPL=2*9=182）结点的权和带权路径长度

树中所有叶子结点的带权路径长度之和。通常记为：其中n表示叶子结点的数目，wi

和li分别表示叶子结点ki的权值和根到ki之间的路径长度。acbd73983）树的带权路径长度4）赫夫曼（Huffman）树

又称最优二叉树。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。例：有四个叶子结点a,b,c,d，分别带权为9、4、5、2，由它们构成三棵不同的二叉树。acbd4952bcda4952abcd9245a）

WPL=9×2+4×2＋5×2＋2×2＝40b）WPL=4×1＋2×2＋5×3＋9×3＝50c）WPL=9×1＋5×2＋4×3＋2×3＝37abc1）根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树；4)重复(2)和(3)两步，直至F中只含一棵树为止。3)从F中删去这两棵树，同时加入刚生成的新树；2)在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;2.构造最优树赫夫曼算法：第一步：abcd9254ac9bd2456第二步：abcd9245第三步：611第四步：a9bcd245611203.判定树

(赫夫曼树的应用之一)

在解决某些判定问题时，利用赫夫曼树可以得到最佳判定算法。例：编制一将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图(a)二叉树结构来实现。a<60

a<70

a<80

a<90

不及格中等良好优秀及格YNYNYNYN(a)输入10000个数据，则需进行31500次比较。分数0—5960—6970—7980—8990—99比例0.050.150.40.30.1学生成绩分布不是均匀的情况：a<60

a<70

a<80

a<90

不及格中等良好优秀及格YNYNYNYN(a)有没有一种更好的办法来减少比较次数呢？70≤a<80a<60及格中等良好80≤a<9060≤a<70不及格优秀YNYYYNNN(b)不及格Ya<90a<80a<70a<60优秀中等及格良好YNNN(c)YYY以比例数为权构造一棵哈夫曼树，如（b)判断树所示。再将每一比较框的两次比较改为一次，可得到（c)判定树。输入10000个数据，仅需进行22000次比较。分数0—5960—6970—7980—8990—99比例0.050.150.40.30.14.赫夫曼编码（赫夫曼树的应用之二）1）二进制编码通信中，可以采用0、1的不同排列来表示不同的字符，称为二进制编码。发送端需要将电文中的字符序列转换成二进制的0、1序列，即编码；接受端需要把接受的0、1序列转换成对应的字符序列，即译码。字符：ABACCDA电文：00010010101100ABCD的编码分别为：00、01、10、11电文总长度为：14

如何能缩短传送电文的总长度，从而节省传送时间呢？

若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样有可能缩短传送电文的总长度。字符：ABACCDAABCD的编码分别为：0、00、1、01电文：

000011010电文总长度为：9?无法译码！为此引入前缀编码的概念2）前缀编码

若对某一字符集进行不等长编码，则要求字符集中任一字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。如何设计前缀编码？利用二叉树设计二进制的前缀编码如何得到电文总长最短的二进制前缀编码呢？01abcd1100

假设有一棵如左图所示的二叉树，四个叶结点分别表示A、B、C、D四个字符，且约定左分支表示字符‘0’，右分支表示字符‘1’，则可以从根结点到叶子结点的路径上以分支字符组成的字符串作为该叶子结点的编码。可以证明，如此得到的必为二进制前缀编码。3）赫夫曼编码

设计电文总长最短的二进制前缀编码即：以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码称赫夫曼编码。例：设通信用的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，试为这8个字母设计哈夫曼编码。0.070.190.020.060.320.030.210.100.070.190.020.060.320.030.210.100.050.070.190.020.060.320.030.210.100.050.110.070.190.020.060.320.030.210.100.050.110.170.070.190.020.060.320.030.210.100.050.110.170.280.070.190.020.060.320.030.210.100.050.110.170.280.400.070.190.020.060.320.030.210.100.050.110.170.280.400.600.070.190.020.060.320.030.210.100.050.110.170.280.400.601.0000000001111111a=1010b=00c=10000d=1001e

=11f=10001g=01h=1011bgedahcftypedefstruct{ unsignedintweight; unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;建立赫夫曼树及求赫夫曼编码的算法

赫夫曼树没有度为1的结点，则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。