前面我们学习的线性数据结构完美版资料

前面我们学习的线性数据结构，每个元素都有唯一的前驱（第一个除外）和后继（最后一个除外），但是在现实应用中，一些问题的数据元素之间的关系就不这样简单，例如元素有多个前驱、多个后继。

本章学习一种非线性数据结构一树，数据元素之间是一种层次关系，元素有且只有一个前驱，但可以有多个后继。第六章树和二叉树树的概念和基本术语二叉树二叉树遍历线索二叉树树与森林霍夫曼树

第六章树和二叉树6.1树的概念和基本术语树的定义

树是由n(n0)个结点的有限集合。如果n=0，称为空树；如果n>0，则

有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n>1，除根以外的其它结点划分为m(m>0)个互不相交的有限集

T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。ACGBDEFKLHMIJ例如A只有根结点的树有13个结点的树其中:A是根,其余结点分成三个互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树树的基本术语

树的结点：包含一个数据元素及若干指向子树的分支；

孩子结点：结点的子树的根称为该结点的孩子双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点：同一双亲的孩子结点；

堂兄结点：双亲在同一层的结点互为堂兄弟。结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

ACGBDEFKLHMIJ树的高度：树中结点的最大层次.

结点的度：结点子树的个数

树的度：树内各结点的度的最大值。

叶子结点：也叫终端结点，是度为0的结点；

分枝结点：度不为0的结点；

有序树：子树有序的树，（子树不能互换）如：家族树；

无序树：不考虑子树的顺序；ACGBDEFKLHMIJ任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMF路径：树中的k个结点n1,n2，…，nk，满足ni是ni+1的双亲，n1到nk有一条路径路径长度：分支数＝路径上结点个数一1根没有双亲，叶子没有孩子；vi是vj的双亲，则L(vi)=L(vj)-1;堂兄弟的双亲是兄弟关系吗？有序树和无序树的区别；注意ACGBDEFKLHMIJ对比树型结构和线性结构的结构特点

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)树的常见表示方法

1.直观表示法：用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系.根在上，叶子在下（即树向下生长）2、集合表示法：根据树的集合定义，写出集合划分。

3、文氏图表示法：

集合表示的一种直观表示，用图表示集合。4、目录表示法：

将一棵树描述为一本书，书--章--节--小节5、广义表表示法：将一棵树描述为一个广义表，子树就对应子表。人们最常用的是第一种，但是不适合计算机！树的基本操作

InitTree（＆T）；操作结果：构造空树T。

DestroyTree（＆T）；初始条件：树T存在。操作结果：销毁树T。

CreateTree（＆T，definition）初始条件：definition给出树T的定义。操作结果：按definition构造树T。

ClearTree（＆T）；初始条件：树T存在。操作结果：将树T清为空树。

TreeEmpty（T）初始条件：树T存在。操作结果：若T为空树，则返回ture，否则false。

TreeDepth（T）初始条件：树T存在。操作结果：返回T的深度。

Root（T）初始条件：树T存在。操作结果：返回T的根。

Value（T,Cur_e）初始条件：树T存在，cur＿e是T中某个结点。操作结果：返回cur＿e的值。Assign（T，cur_e，value）初始条件：树T存在，cur＿e是T中某个结点。操作结果：结点cur_e赋值为value。

Parent（T，cur＿e）初始条件：树T存在，cur＿e是T中某个结点。操作结果：若cur＿e是T的非根结点，则返回它的双亲，否则函数值为“空”。

Rightsibling（T，cur＿e）初始条件：树T存在，cur＿e是T中某个结点操作结果：若cur＿e有右兄弟，则返回它的右兄弟，否则函数值为“空”。

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棵子树。

TraverseTree（T，visit（））；初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次.一旦visit（）失败，则操作失败LeftChild（T，cur＿e）初始条件：树T存在，cur＿e是T中某个结点。操作结果：若cur＿e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。6.2二叉树一二叉树的概念二二叉树的性质三二叉树的存储结构定义:二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。ABCDEFGHK根结点左子树右子树6.2二叉树(BinaryTree)特点:每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树应用举例例可以用二叉树表示表达式

e

d

c

b

f

a

+

*

/

-

-a+b*(c-d)-e/f性质1 在二叉树的第i层上至多有2i－1个结点。(i

1)[证明用归纳法]证明：当i=1时，只有根结点，2i-1=20=1。假设对所有j，i>j1，命题成立，即第j层上至多有2j-1个结点。由归纳假设第i-1

层上至多有2i－2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i－2=2i-1。性质性质2

深度为k的二叉树至多有2k-1个结点(k1)。证明：由性质1可见，深度为k的二叉树的最大结点数为

＝20+21+…+2k-1=2k-1＝定义2完全二叉树(CompleteBinaryTree)则总编码长度为(2+7+4+5)*2=36.中序遍历序列：D,B,G,E,A,C,F//T指向头结点，头结点的左链lchild指向根结点，^D^E^F^Intn,r;//结点数和根的位置；CTBoxnodes[MAX_TREE_SIZE];证明：由性质1可见，深度为k的二叉树的最大结点数为2）若有右孩子，则有孩子结点编号为2i+1；TreeDatadata;孩子结点：结点的子树的根称为该结点的孩子E3-1-1比等长编码的情形要短。F3-1-1初始条件：树T存在。树的后根遍历可以借助对应二叉树性质3

对任何一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0＝n2＋1.证明：若度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2

-1n2=n0

-1n0=n2+1定义1

满二叉树(FullBinaryTree)

一棵深度为k且有2k-1个结点的二叉树称为满二叉树。两种特殊形态的二叉树621754389101113141512满二叉树2154367216543非完全二叉树定义2完全二叉树(CompleteBinaryTree)

若设二叉树的高度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。621754389101112完全二叉树a+b*(c-d)-e/fD145若二叉树非空

（1）中序遍历左子树

（2）访问根结点或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。孩子结点：结点的子树的根称为该结点的孩子常见的二叉树结点结构如下所示：树后根遍历EFBCGDA操作结果：若cur＿e有右兄弟，则返回它的右兄弟，否则函数值为“空”。性质2 深度为k的二叉树至多有2k-1个结点(k1)。总编码长度正好等于霍夫初始条件：树T存在。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。二叉树由根、左子树、右子树三部分组成取对数h－1<log2nh，又h是整数，InOrderTraverse(T->rchild,Visit);

}//InOrderTraverse性质4

具有n(n0)个结点的完全二叉树的深度为log2(n)＋1

证明： 设完全二叉树的深度为h，则根据性质2和完全二叉树的定义有 2h－1

-1<n2h-1或2h－1

n<2h取对数h－1<log2nh，又h是整数，因此有h=log2(n)＋1性质5

如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0,1,2,…,n-1，则有以下关系：

若i=0,则i无双亲若i>0,则i的双亲为(i-1)/2

若2*i+1<n,则i的左子女为2*i+1，若2*i+2<n,则i的右子女为2*i+2若结点编号i为偶数，且i!=0,则左兄弟结点i-1.若结点编号i为奇数，且i!=n-1,则右兄弟结点为i+1.0712345689性质5：在完全二叉树中编号（1开始）为i的结点，1）若有左孩子，则左孩编号为2i；2）若有右孩子，则有孩子结点编号为2i+1；3）若有双亲，则双亲结点编号为

i/2；2i+2

2i2i+12i+22i+3i+12i2i+1iii+1二叉树的存储结构

二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。顺序存储结构这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。一般二叉树的顺序表示123456789101234056780091012489105673顺序表示912365478910完全二叉树的顺序表示--------二叉树的顺序存储表示------------#defineMAX_TREE_SIZE100//二叉树的最大结点数

typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存放根结点

SqBiTreebt;最坏情况：深度为k的且只有k个结点的单支树需要长度为2k-1的一维数组。链式存储结构

在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：lChilddatarChild

其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。类型定义为：

typedefstructBiTNode{TElemTypedata;structBiTNode*Lchild,*Rchlid;}BTNode,*BTree;GHDEFBCA^G^^H^^D^E^F^B^CABT这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。lChilddataparentrChild

typedefstructTriTNode{//结点结构TElemTypedata;

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

structTriTNode

*parent;//双亲指针

}TriTNode,*TriTree;类型描述如下:二叉树链表表示的示例ABCDFErootFABCDErootABCDFEroot三叉链表二叉树二叉链表三叉链表的静态结构ABCDFErootdataparentleftChildrightChild012345A

-11-1B023C1

-1-1D145E3-1-1F3-1-1上面们二叉链表或三叉链表是用指针实现，是一种动态的链式存储结构，链式存储结构也可用一维数组来实现，用一维数组表示的二叉链表或三叉链表，称为静态链表6.3二叉树的遍历一.二叉树的遍历方法二.遍历的递归算法6.3二叉树的遍历遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每个结点，而且每个结点仅被访问一次？二叉树的遍历方法

二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：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

A

F

G

E

D

C

B例：先序遍历右图所示的二叉树（1）访问根结点A（2）先序遍历左子树：即按DLR的顺序遍历左子树（3）先序遍历右子树：即按DLR的顺序遍历右子树中序遍历（LDR）若二叉树非空

（1）中序遍历左子树

（2）访问根结点（3）中序遍历右子树中序遍历序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B例：中序遍历右图所示的二叉树（1）中序遍历左子树：即按LDR的顺序遍历左子树（2）访问根结点A（3）中序遍历右子树：即按LDR的顺序遍历右子树后序遍历（LRD）若二叉树非空

（1）后序遍历左子树

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

A

F

G

E

D

C

B后序遍历序列：a,b,c,d,-,*,+,e,f,/,-中序遍历序列：a,+,b,*,c,-,d,-,e,/,f先序遍历序列：-,+,a,*,b,-,c,d,/,e,f例：先序遍历、中序遍历、后序遍历下图所示的二叉树--/+*abcdef这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分：1）基本项（也叫终止项）；2）递归项若二叉树非空（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；先序遍历递归定义递归项二.遍历的递归算法上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例：先序遍历（DLR）的定义：该定义隐含着若二叉树为空，结束上面先序遍历的定义等价于：若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit()访问结点总是成功的。先序遍历递归算法

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;}2中序遍历递归算法

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

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

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

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

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

InOrderTraverse(T->rchild,Visit);

}//InOrderTraverse

3后序遍历递归算法

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

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

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

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

PostOrderTraverse(T->lchild,Visit);

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

}//PostOrderTraverse

例: 已知一棵二叉树的中根序列和先根序列分别为ABCDEFGHIJK和EBADCFHGIKJ，试画出这棵二叉树。4.中序遍历二叉树(非递归算法)用栈实现baabcdeadaaab入栈b退栈访问d入栈d退栈访问e退栈访问ecc栈空

a退栈访问ce入栈c

退栈访问

voidInOrder(BinTreeT){

stackS;InitStack(&S);//递归工作栈

BinTreeNode*p=T;

//初始化while(p!=NULL||!StackEmpty(&S)){ if(p!=NULL){Push(&S,p);p=p->leftChild;}else{Pop(&S,p);//退栈printf(p->data);//访问根p=p->rightChild;}//if}//whilereturnok;}abcde线索二叉树

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

1）对二叉树所有结点做某种处理可在遍历过程中实现;2）查找二叉树某个结点，可通过遍历实现；

与线性表相比，对二叉树的遍历存在如下问题：

1）遍历算法要复杂的多，费时的多；

2）为检索或查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。5.4线索二叉树(ThreadedBinaryTree)如何将二叉树线性化？

以中序遍历为例，我们看到通过遍历可以得到二叉树结点的中序序列。若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。加上结点前趋后继信息（线索）的二叉树称为线索二叉树中序遍历序列：D,B,H,E,A,F,C,G在中序序列中，D的后继是B，H的前趋是B，后继是E…加上结点前趋后继信息（结索）的二叉树称为线索二叉树

AG

H

E

D

C

B

F线索二叉树孩子指针前趋指针后继指针2．线索链表

线索二叉树的存贮方法：

1）

为每个结点增加二个标志域。

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

D

A

B

C

∧F

∧∧

H∧

E

∧∧

G

∧对线索链表中结点的约定：

在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针Link”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索Thread”。若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索Thread”。Ltag=0,lchild为左子女指针Ltag=1,lchild为前驱线索Rtag=0,rchild为右子女指针Rtag=1,rchild为后继指针结点结构lchildrchilddataLtagRtag

线索链表的类型说明typedefenum{link,thread}PointerTag;//link=0,thread=1typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;//左右指针域PointerTagLtag,Rtag;//左右标志域，标志域为0时表示左右指针域存储的是左右孩子的指针，标志域为1时表示左右指针域存储的是前趋后继结点的指针}BiThrNode，*BiThrTreeF11E01G10D01A00B00H11C00线索链表图示线索二叉树

AG

H

E

D

C

B

F孩子指针前趋指针后继指针中序遍历序列：D,B,H,E,A,F,C,G为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点.约定：

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

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

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

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

在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历。

基本步骤：1）p=T->lchild;p指向线索链表的根结点；2）若线索链表非空，循环：（a）循环，顺着p左孩子指针找到最左下结点；访问之（b）若p所指结点的右孩子域为线索，p的右孩子结点即为后继结点循环：p=p->rchild；并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）（c）一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p->rchild，使p指向右孩子结点；3）返回OK；结束线索链表的遍历算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)){//T指向头结点，头结点的左链lchild指向根结点，//中序遍历二叉线索树T算法，对每个数据元素调用函数Visit。P=T->lchild;//p指向根结点While(p!=T){//空树或遍历结束时，p==TWhile(p->Ltag==Link)p=p->lchild;

//找到最左下结点；访问之Visit(p->data))while(p->Rtag==Thread&&p->rchild!=T){

//若p所指结点的右孩子域为线索且不是最后一个结点p=p->rchild;Visit(p->data);//访问后继结点}p=p->rchild;}returnOK;}//InOrderTraverse_Thr树的存储结构在树中，每个结点即可能有孩子也可能有双亲，所以既可以通过保存每个结点的孩子结点位置来表示结点之间的结构关系，也可以通过保存每个结点的双亲结点位置来表示结点之间的结构关系。1.双亲表示：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。树与森林ABCDEFGdataparentABCDEFG-10001130123456*便于涉及双亲的操作；*求结点的孩子时需要遍历整棵树。特点:用双亲表示实现的树定义#defineMaxSize //最大结点个数typedefcharTreeData;//结点数据typedefstruct{//树结点定义TreeDatadata;intparent;//双亲位置域}TreeNode;typedefTreeNodeTree[MaxSize];//树2、孩子表示法孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。方法一:

顺序存储#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intchild1;//第1个孩子位置域intchild2;//第2个孩子位置域......intchildd;//第d个孩子位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}PTree;孩子表示法举例RADEFCBGKH0123456789数组下标:*便于涉及孩子的操作；求双亲不方便；*采用同构的结点，空间浪费。R1A4B0C6D0E0F7G0H0K023500000000089000000方法二:链式存储：对树的每个结点用线性链表存贮它的孩子结点树的孩子链表类型定义typedefstructCTNode{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];Intn,r;//结点数和根的位置；}CTree;孩子链表存储表示举例RADEFCBGKH0123456789数组下标:*便于涉及孩子的操作；*求结点的双亲时不方便。RAB/CD/E/FG/H/K/123/45/6/789/T.nodes[];T.n=10;T.r=0;结点结构

datafirstChildnextSibling3孩子兄弟表示法(二叉链表示法)孩子兄弟表示法用二叉链表作为树的存贮结构typedefstructCSNode{

ELemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;

类型定义:RADEFCBGKHRADECHFGBK孩子兄弟表示法示例：树与二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。树与二叉树转换方法树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子特点：一棵树转换成二叉树后，根结点没有右孩子。IACBDHGFE此二叉链表既是树(a)的孩子兄弟表示又是二叉树(b)的二叉链表由此可将树与二叉树对应起来AIHDGFCEBFIABDHGCE森林森林：树的集合

将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历；

J

O

P

N

M

L

KIACBDHGFE包含两棵树的森林如果F={T1,T2,…,Tm}是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)。(1)若F为空，即m=0,则B为空树；(2)若F非空，则B的根root即为森林中第一棵树的根ROOT(T1)；B的左子树LB是从T1中根结点的子树森林F1={T11,T12,…,T1m1}转换而成的二叉树;其右子对RB是从森林F'={T2,T3,…,Tm}转换而成的二叉树.T1T2T3AFHBCDGIJEK3棵树的森林T1T2T3AFBCDEGHIKJ各棵树的二叉树表示ABCEDHIKJFG森林的二叉树表示森林与二叉树的转换二叉树转换成森林如果B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林F={T1,T2,…,Tm}：(1)若B为空，则F为空；(2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root；T1中的根结点的子树森林F1是由B的左子树LB转换而成的森林;F中除T1之外其余树组成的森林F'={T2,T3,…，Tm}是由B的右子树RB转换而成的森林。当树非空时访问根结点依次先根遍历根的各棵子树树先根遍历

ABEFCDG对应二叉树前序遍历ABEFCDG树的先根遍历结果与其对应二叉树表示的前序遍历结果相同树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCEDGF树的先根次序遍历树的遍历ACBDGFE树的后根次序遍历:当树非空时依次后根遍历根的各棵子树访问根结点树后根遍历EFBCGDA对应二叉树中序遍历EFBCGDA树的后根遍历结果与其对应二叉树表示的中序遍历结果相同树的后根遍历可以借助对应二叉树的中序遍历算法实现ACBDGFEABCEDGF森林的两种遍历方法：一、先序遍历森林：若森林非空，则（1）访问森林中第一棵树的根结点；（2）先序遍历第一棵树的根结点的子树森林；（3）先序遍历除去第一棵树之后的森林。二、中序遍历森林：若森林非空，则（1）中序遍历第一棵树的根结点的子树森林；（2）访问森林中第一棵树的根结点；（3）中序遍历除去第一棵树之后的森林。霍夫曼树(HuffmanTree)

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

wi

与该结点到根的路径长度

li

的乘积的和。用公式可表示为：WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=367*3=464*3=35222444555777带权路径长度达到最小霍夫曼树假设有n个权值{ω1,ω2,…,ωn}，试