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

Chp6树和二叉树本章重点内容6.1树的定义和基本概念6.2二叉树

6.2.1树的定义和基本术语

6.2.2二叉树的性质

6.2.3二叉树的存储结构6.3遍历二叉树

6.3.1遍历二叉树

6.3.2线索二叉树

6.4树和森林

6.4.1树的存储结构

6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.6赫夫曼树及其应用

6.6.1最优二叉树（赫夫曼树）

6.6.2赫夫曼编码

树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等引言6.1树的定义与基本概念1.树的定义定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点——根树中各子树是互不相交的集合A只有根结点的树ABCDEFGHIJKLM有子树的树根子树从逻辑结构看：

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

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

4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构，（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有零个或多个直接后继。JIACBDHGFE2．树的应用

1）树可表示具有分枝结构关系的对象例1家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M他们之间的关系可用下图所示的树表示：JIACBDHGFEKLM2）树是常用的数据组织形式

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

例2计算机的文件系统

不论是Linux文件系统还是Windows文件系统，所有的文件是用树的形式来组织的。文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件12/3．树的逻辑结构描述

二元组描述为：Tree=(D,R)

D={Ki∣1≤i≤n;n≥0,KiTElemtype}

R={r}

其中：D是n个具有相同特性的数据元素的集合;n为树中结点个数，若n=0，则为一棵空树，n>0时称为一棵非空树。关系r应满足下列条件：（1）有且仅有一个结点没有前驱，称该结点为树根;（2）除根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有零个或多个直接后继(孩子结点)。

基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子堂兄结点——同一层上结点树的度——一棵树中最大的结点度数结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点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的祖先树的表示方法1.树型表示bacghdefij2.凹入表表示abdeijfcgh3.嵌套集合表示4.广义表表示ijdfghabcea(b(d,e(i,j),c(g,h)))6.2二叉树定义定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空性质1:

在二叉树的第i层上至多有2i-1个结点(i≥1)。

证明：

用数学归纳法。

1)当i=1时，整个二叉树只有一根结点，此时2i-1=20=1，结论成立。

2)设i=k时结论成立，即第k层上结点总数最多为2k-1个。现证明当i=k+1时，结论成立：因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-1，故结论成立。推论：度为m的树中第i层上至多有mi-1个结点,(i≥1)。二叉树性质性质2:

深度为k的二叉树至多有2k-1个结点（k≥1）。

证明：因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为推论：深度为k的m叉树至多有个结点。

性质3:

对任意一棵二叉树，若终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

证明：设二叉树中结点总数为n，n1为二叉树中度为1的结点总数，设二叉树中分支数目为B。①n=n0+n1+n2

除根结点外，每个结点均对应一个进入它的分支：②n=B+1

二叉树中的分支都是由度为1和度为2的结点发出③B=n1+2n2于是：由①②③可得：n0+n1+n2=n1+2n2+1n0=n2+1。几种特殊形式的二叉树满二叉树定义：一颗深度为k且有2k-1个结点的二叉树特点：每一层上的结点数都是最大结点数满二叉树的顺序表示，即从二叉树的根开始，层间从上到下，层内从左到右，逐层进行编号（1，2，…，n）。完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为~特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右子树的最大层次为L，则其左子树的最大层次必为L或L+1（最下层的叶子结点集中在树的左部）(b)完全二叉树(c)非完全二叉树(d)非完全二叉树图6.9特殊形态的二叉树(a)满二叉树性质4

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

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

2h－1-1<n2h-1或2h－1

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

＋1621754389101112性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：

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

如果i>1，则其双亲是i/2(2)如果2i>n，则结点i无左孩子；

如果2in，则其左孩子是2i(3)如果2i+1>n，则结点i无右孩子；

如果2i+1n，则其右孩子是2i+1621754389101112二叉树的存储结构顺序存储结构满二叉树或完全二叉树的顺序存储结构

对于完全二叉树来说，除最下面一层外，各层都被结点充满。若对二叉树按层排序，则从一个结点的编号就可推知其双亲、左右孩子等结点的编号。用一维数组bt[]存放一棵完全二叉树，将标号为i的结点的数据元素存放在分量bt[i]中，bt[0]不存放元素。

例:bt[5]（i=5)的双亲结点标号是k=└i/2┘=2，双亲结点所对应的数组分量bt[k]=bt[2]。bt[2]（i=2)的右孩子结点标号是k=2i+1=5，所对应的数组分量bt[k]=bt[5]。ABCEFG123456k0123456…nbt[k]ABCEFG…顺序结构图示:二叉树的存储结构非完全二叉树的顺序存储结构实现：按完全二叉树的形式补齐二叉树所缺少的那些结点，对二叉树结点再按层编号，将二叉树原有的结点按编号存储到内存单元“相应”的位置上。特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树abcdefgabcde0000fg12345678910116789123451011补齐二叉树所缺少的那些结点ABCDEFGHIJKL123456789101112完全二叉树abcdefghijkl结点编号123456789101112131415结点值123450000670000第i号结点的左右孩子一定保存在第2i及2i+1号单元中。缺点：对非完全二叉树而言，浪费存储空间#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;链式存储结构二叉链表typedefstructnode{datatypedata;structnode*lchild,*rchild;}JD;lchilddatarchildABCDEFG在n个结点的二叉链表中，有n+1个空指针域ABCDEFG^^^^^^^^空指针个数：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1链表中每个结点由三个域组成三叉链表typedefstructnode{datatypedata;structnode*lchild,*rchild,*parent;}JD;lchilddataparentrchildABCDEFGABCDEFG^^^^^^^^^指向双亲遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事

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

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

D：访问根结点

R：遍历右子树有六种遍历方法：

DLR，LDR，LRD，

DRL，RDL，RLD

约定先左后右,有三种遍历方法：DLR、LDR、LRD

，分别称为先序遍历、中序遍历、后序遍历

A

F

G

E

D

C

B二叉树的遍历方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRLADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC先序遍历:

先访问根结点,然后分别先序遍历左子树、右子树ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC中序遍历：

先中序遍历左子树，然后访问根结点，最后中序遍历右子树ADBCLRDLRDLRD>A>>D>>CLRD后序遍历序列：DBCA后序遍历:

先后序遍历左、右子树，然后访问根结点B先序遍历：中序遍历：后序遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef--/+*abcdef例：将如下表达式

a+b*(c-d)-e/f存入一个树结构。叶子节点为操作数中间节点为运算符前缀表达式中缀表达式后缀表达式若二叉树非空（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；先序遍历（DLR）的定义：上面先序遍历的定义等价于：若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；AFGEDCB

遍历的算法先序遍历的递归算法voidpreorder(JD*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC先序遍历的非递归算法递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，效率不高，故有时考虑非递归算法。

遍历时从根结点开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问。

在下面算法中，二叉树以二叉链表存放，用一维数组stack[Maxsize]实现栈，变量top用来表示当前栈顶的位置。

（1）令当前指针p指向根结点；（2）当p非空,访问当前结点p，将p压入栈中，令当前指针指向其左孩子，重复（2），直到p为NULL；（3）当p为空时，从栈中弹出栈顶元素赋给变量p，令当前指针指向其右孩子；（4）若栈非空或当前指针非NULL，执行（2）；当p为空且栈也为空时，遍历结束。先序遍历（DLR）的非递归算法思想

先序遍历的非递归算法dbea*-/c+voidNRPreOrder(BTreebt){ BTreestack[Maxsize],p; inttop; if(bt!=NULL){ top=-1;p=bt; while(p!=NULL||top>-1) { while(p!=NULL) { printf("%d",p->data); top++; stack[top]=p; p=p->lchild; } if(top>-1) { p=stack[top];top--;p=p->rchild; } }}}/*指针指向p的左孩子*//*访问结点的数据域*//*将当前指针p压栈*//*从栈中弹出栈顶元素，指针指向p的右孩子结点*//*初始化*/中序遍历的递归算法

voidInOrderTraverse(BiTreeT) {if(T!=NULL){InOrderTraverse(T->lchild); printf("%c",T->data);/*访问根结点*/ InOrderTraverse(T->rchild); }}中序遍历的非递归算法遍历时从根结点开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点访问。中序遍历的非递归算法思想从二叉树的根结点开始，令变量p为根结点，若p不为空，则令p沿左子树根结点前进，在前进过程中，把所经历的结点逐个压入栈中，当p为空时，弹出栈顶元素给p，并访问该结点，再令p为它当前结点的右子树根结点。重复上述过程，当p为空且栈也为空时，遍历结束。在算法具体实现时，只需将先序遍历的非递归算法中的Visit(p->data)移到p=stack[top];top--;和p=p->rchild之间即可。后序遍历递归算法

∧a∧

+

*//\d/\-bt∧e∧∧b∧∧c∧a*(b-c)+d/evoidPostorder(BTreebt){

if(bt!=NULL)

{

Postorder(bt->lchild);

Postorder(bt->rchild);

printf(“%c,”,bt->data);

}}后序序列为abc–*de/+称为后缀表达式后序遍历的非递归算法遍历从根结点开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。后序遍历的非递归算法思想：

后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。

可采用标记法，结点入栈时，配一个标志tag一同入栈(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。

首先将T和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。

typedef

struct

{

BTree

data;int

tag;

}stacknode;void

NRPostOrder(BTree

T){

InitStack(S);

while

(

T!=NULL

||

!StackEmpty(S)

){

while

(

T

!=

NULL

){

Push(S,T,1);T

=

T->lchild;}

while

(

!EmptyStack(S)

&&

GetTopTag(S)==2){

Pop(S,

x);Visit(x->data);}

if

(

!EmptyStack(S)

){

SetTopTag(S,

2);

//

设置栈顶标记

T

=

GetTopPointer(S);

//

取栈顶保存的指针

T

=

T->rchild;

}else

break;}

}层序遍历算法遍历方法：从上而下，从左到右依次访问树中每个结点。层序遍历二叉树算法思想:若二叉树不为空，则根结点入队；如队列不空，循环：做出队操作，队首元素作为当前结点，访问当前结点；将当前结点的左右孩子入队；最后，出队序列就是层序遍历序列AFGEDCB遍历结果ABCDEFG例1：为二叉树建立二叉链表(递归算法)以递归方式建立二叉树输入：二叉树的先序序列结果：二叉树的二叉链表遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有结点并完成相应结点的链接？基本思想：输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接遍历算法应用应用1：按先序遍历序列建立二叉树的二叉链表∧

D

A

B∧C

∧∧

E∧∧

F∧T

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

A

F

E

D

C

B*******

A

F

E

D

C

B①②使得原二叉树中每个结点，（包括叶子结点）都有左右孩子StatusCreateBiTree(BiTree&T){//输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字//符）按先序遍历的顺序，建立二叉链表，并将该二叉链表根结点指针//赋给Tscanf(&ch);if(ch==‘*’)T=NULL;//若ch==‘*’则T=NULL返回

else{//若ch!=‘*’if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->date=ch;//建立（根）结点

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

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

CreateBiTree(T->rchild);//构造右子树链表，并将右子树根结点指针

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

}returnOK;}//CreateBiTree如果输入字符不是“*”，则建立一个新结点，然后建立其左子树和右子树；如果是“*”则返回，继续进行下一次操作。AB

C

D

ABCD上页算法执行过程举例如下：ATBCD^^^^^应用2：统计二叉树中结点总数m，叶子结点个数n0分析：每当访问一个结点时，在原访问语句printf后边，加上一条计数器语句m++和一个判断该结点是否叶子的语句，便可解决问题假设用中根遍历方法统计叶子结点个数，算法如下：算法1：Voidinjishu(Bnode*t)

｛if(t!=NULL)

｛injishu(t->lch)；/*统计左子树结点数*/printf("%6c"，t->data)；/*访问根结点*/m++; /*结点记数*/if((t->lch==NULL)&&(t->rch==NULL))n0++；/*叶结点记数*/

injishu(t->rch)；/*统计右子树节点数*/

｝｝/*injishu*/

算法2：voidCountLeaf

(BiTreeT,int*count){//求叶子节点的个数，T为根节点的指针

if(T){if((!T->lchild)&&(!T->rchild))*count++;//对叶子结点计数

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeafintHeight(BitreeT)//Heightofatree{if(T==NULL)return0;else { intm=Height(T->lchild); intn=Height(T->rchild); return(m>n)?m+1:n+1; }}应用3：求二叉树高度(递归算法)输入：二叉树的二叉链表结果：二叉树的高度分析如下：（1）若二叉树为空，则其高度为0，求解结束（2）若二叉树不为空，则其高度为左右子树高度最大值加1

对于一个完全二叉树来说，利用先序序列、中序序列和后序序列可以确定此树。然而，对于一个一般的二叉树，仅知二叉树的先序序列“abcdefg”

不能唯一确定一棵二叉树。如果同时已知二叉树的中序序列“cbdaegf”，则会如何？

应用4：由二叉树的先序和中序序列建树

二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根P154,例6-5abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列例1.已知树的前序序列为abdcegf

中序序列为bdaegcf

则树为？abdcfeg例2.已知树的后序序列为dbgefca

中序序列为bdaegcf则树为？我们可以利用前序序列和中序序列、后序序列和中序序列

来确定一棵二叉树。注意：若只是知道前序和后序的序列就不能唯一的确定一个二叉树。问题的提出遍历是二叉树最基本最常用的操作。

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

2）检索（查找）二叉树某个结点，可通过遍历实现；遍历的过程就是将非线性序列转化为一个线性序列，使得每个结点只有一个直接前驱和一个直接后继。那么当我们采用二叉链表作为存储结构时，只能找到结点的左、右孩子，不能直接得到它的前驱和后继，那么我们如何来保存在某种遍历过程中得到的前驱和后继信息呢？？为了保留结点在某种遍历序列中直接“前驱”和直接“后继”的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示二叉链表的2n个孩子指针域中只用到了n-1个域，还有另外n+1个指针域为空，被闲置现设法将这些空闲的指针域利用起来。当某结点无左孩子时，令左指针指向它的前趋结点；当该结点无右孩子时，令右指针指向它的后继结点。为了严格区分结点的孩子指针域究竟指向孩子结点还是指向前趋或后继结点，需在原结点结构中增加两个标志域。解决办法定义：前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~线索：指向前驱或后继结点的指针称为~线索二叉树：加上线索的二叉树叫~线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~实现在有n个结点的二叉链表中必定有n+1个空链域在线索二叉树的结点中增加两个标志域ltag:若ltag=0,lc域指向左孩子；若ltag=1,lc域指向其前驱rtag:若rtag=0,rc域指向右孩子；若rtag=1,rc域指向其后继结点定义：typedefstructnode{intdata;intltag,rtag;structnode*lc,*rc;}JD;lcltagdatartagrc6.4线索二叉树ABCDEABDCET先序序列：ABCDE00001111^11先序线索二叉树ABCDEABDCET中序序列：BCAED00001111^11^ABDCET后序序列：CBEDA0000111111^ABCDE中序线索二叉树后序线索二叉树为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点

约定：

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

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

③中序序列第一结点lc域：指向头结点;

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

0

1头结点：ltag=0,lc指向根结点rtag=1,rc指向中序序列中最后一个结点中序遍历序列中第一个结点的lc域和最后一个结点的rc域都指向头结点ABDCET中序序列：BCAED中序线索二叉树00001111^11^3．线索二叉树的遍历

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

下面是P134线索链表的遍历算法6.5。

在中序线索二叉树上遍历二叉树，其基本步骤：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==0)p=p->lchild;//找到最左下结点；访问之

if(!Visit(p->data))returnERRORwhile(p->Rtag==1&&p->rchild!=T){//若p所指结点的右孩子域为线索且不是最后一个结点

p=p->rchild;Visit(p->data);//访问后继结点

}p=p->rchild;}returnOK;}//InOrderTraverse_Thr1在中序线索二叉树中查找任意结点的中序前驱结点对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况：如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点（左子树最后一个访问结点），即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。线索二叉树的基本操作实现BithrtreeInprenode(Bithrtreep){ Bithrtreepre; pre=p->lchild; if(p->ltag!=1) while(pre->rtag==0) pre=pre->rchild; return(pre);}在中序线索二叉树中查找任意结点的中序前驱结点2在中序线索二叉树中查找任意结点的中序后继结点对于中序线索二叉树上的任一结点，寻找其中序的后继结点，也有以下两种情况：如果该结点的右标志为1，那么其右指针域所指向的结点便是它的后继结点；如果该结点的右标志为0，表明该结点有右孩子，根据中序遍历的定义，它的后继结点是以该结点的右孩子为根结点的子树的最左结点（右子树第一个访问结点），即沿着其右子树的左指针链向下查找，当某结点的左标志为1时，它就是所要找的后继结点。BithrtreeInpostnode(Bithrtreep){ Bithrtreepost; post=p->rchild; if(p->rtag!=1)

while(post->ltag==0) post=post->lchild; return(post);}在中序线索二叉树中查找任意结点的中序后继结点6.5树的存储结构在计算机中，树的存储通常采用顺序存储结构和链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系

双亲表示法实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置特点：找双亲容易，找孩子难typedefstructnode{datatypedata;intparent;}JD;JDt[M];abcdefhgiacdefghib-101124440501234678dataparent如何找孩子结点图中用parent域的值为-1表示该结点无双亲结点，即该结点是一个根结点。孩子表示法多重链表：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度D,浪费内存结点不同构：结点指针个数不等，为该结点的度d，实现不放便datachild1child2……….childDdatadegreechild1child2……….childd孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表其主体是一个与结点个数一样大小的一维数组 数组的每一个元素有两个域组成，一个域用来存放结点信息；另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。孩子结点单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的下标；另一个是指针域，指向下一个孩子。abcdefhgi501234678acdefghibdatafirstchild12^34^^867^5^^^^^如何找双亲结点孩子结点：typedefstructnode{intchild;//该结点在表头数组中下标

structnode*next;//指向下一孩子结点}ChildNode;表头结点：typedefstructtnode{datatypedata;//数据域

ChildNode*firstchild;//指向第一个孩子的指针}NodeType;

NodeType

t[M];带双亲的孩子链表501234678acdefghibdatafirstchild12348675^^^^^^^^^-101124440parentabcdefhgi孩子兄弟表示法（二叉链表表示法）实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点特点操作容易破坏了树的层次typedefstructnode{datatypedata;structnode*fch,*nsib;}JD;abcdefhgiabcdefghi^^^^^^^^^^IACBDHGFE此二叉链表既是树(a)的孩子兄弟表示又是二叉树(b)的二叉链表(a)(b)由此可将树与二叉树对应起来AIHDGFCEBFIABDHGCE二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。树与二叉树转换方法树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子IACBDHGFEFIABDHGCE树与二叉树转换树与二叉树转换ACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应存储存储解释解释将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ练习： 对下图中的二叉树进行后序线索化，为每个空指针建立相应的前驱或后继？ADCBFEGH将下图中的森林转换为对应的二叉树。ADCBFEGJKLMNOPIH将下图中二叉树转换为森林。ADCBFEGJKLMNOIH1树的遍历先序遍历树和森林的遍历在树和森林中，一个结点可能有两棵以上的子树，所以不讨论其中序遍历，只讨论先序遍历和后序遍历。AFEDCB访问根结点；按照从左到右的顺序先序遍历根结点的每一棵子树。

ABECFD后序遍历按照从左到右的顺序后序遍历根结点的每一棵子树。访问根结点；

EBFCDA树的遍历与转换的相应二叉树的遍历序列有什么关系？与对应二叉树的中序序列相同与对应二叉树的先序序列相同2森林的遍历先序遍历访问森林中第一棵树的根结点；先序遍历第一棵树的根结点的子树；先序遍历去掉第一棵树后的子森林。

ABCDEFGHI后序遍历后序遍历第一棵树的根结点的子树；访问森林中第一棵树的根结点；后序遍历去掉第一棵树后的子森林。

BCDAFEHIGFEADCBGIH森林的遍历与转换的相应二叉树的遍历序列有什么关系？ABCDEFGHIJKLMNO先序遍历：后序遍历：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDA6.5二叉树的应用哈夫曼树(Huffman)——带权路径长度最短的树定义路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的~路径长度：路径上的分支数目若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1树的路径长度：从树根到每一个结点的路径长度之和PL树的外部路径长度是各叶结点(外结点)到根结点的路径长度之和EPL。树的内部路径长度是各非叶结点(内结点)到根结点的路径长度之和IPL。

树的路径长度PL=EPL+IPL12345678树的外部路径长度EPL=3*1+2*3=9树的内部路径长度IPL=1*2+2*1=4树的外部路径长度EPL=1*1+2*1+3*1+4*1=1023456781结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。从根结点到该结点之间的路径长度与该结点的权的乘积称为结点的带权路径长度。树的带权路径长度（WeightedPathLength

，WPL）：树的各叶结点所带的权值

wi与该结点到根的路径长度

li的乘积的和。Huffman树——带权路径长度达到最小的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。例有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35对于已知的一组叶子的权值W1，W2，…，Wn：构造Huffman树的方法——Huffman算法构造Huffman树步骤以权值分别为W1,W2．．．,Wｎ的ｎ个结点，构成n棵二叉树T1,T2,．．．,Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树Ti仅有一个权值为Wi的根结点；在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值=Wi）从F中删除这两棵二叉树，同时将新二叉树加入到F中;重复(2)、(３)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman树。F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}

7524初始合并{2}{4}75246F:{18}

1175246合并{5}{6}5合并{7}{11}27461118举例霍夫曼树的构造过程例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100

由哈夫曼树构造思想得知，初始森林中共有n棵二叉树，每棵树中都仅有一个孤立的结点，接着将当前森林中的两棵根结点权值最小的二叉树合并成一棵新的二叉树。每次都是将两个子树合并，所以不存在度为1的结点特点1：哈夫曼树中不存在度为1的结点由哈夫曼树构造思想得知，初始森林中共有n棵二叉树，每棵树中都仅有一个孤立的结点，接着将当前森林中的两棵根结点权值最小的二叉树合并成一棵新的二叉树。每合并一次，森林中就减少一棵树。显然要进行n-1次合并，才能使森林中的二叉树的数目，由n棵减少到只剩下一棵最终的哈夫曼树。并且每次合并，都要产生一个新结点。合并n-1次共产生n-1个新结点，并且它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中共有2n-1个结点。特点2：n个叶子结点构造的哈夫曼树中，共有2n-1个结点特点3：任一棵哈夫曼树的带树路径长度等于所有分支结点（非叶子结点）值的累加和。11358192342291487152958100哈夫曼结点结构(采用静态链表)w