计算机考研：数据结构常用算法精析（6）

第六章

结点的出度(OD)：结点拥有的非空子树数目。

结点的入度(ID)：指向结点的分支(或有向弧、指针)的数目。

树的度(TD)：树中结点出度的最大值。

结点的度：该结点的出度

例如 在下述结论中，正确的是( D )【南京理工大学 1999 一、4 (1分)】

①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③ B.②③④ C.②④ D.①④

有关二叉树下列说法正确的是( B )【南京理工大学 2000 一、11 (1.5分)】

A.二叉树的度为2 B.一棵二叉树的度可以小于2

C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2

有序树和无序树：若树中任一结点的各子树从左到右有序，则该树为有序树(强调子树的次序)，否则为无序树。(只强调各子树之间相对有序，而并不像二叉树那样，当只有一个子树是要么是左子树要么是右子树。而在有序树中，只有一个子树的有序树就不唯一了。)

例题：在下列情况中，可称为二叉树的是( B )

A.每个结点至多有两棵子树的树 B. 哈夫曼树 C.每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E.以上答案都不对

C错在有序树不一定是二叉树，有序只是子树的相对保持有序，并没有严格定义具体那颗子树就是第几颗子树。

森林(或树林)：m(m0) 棵互不相交的有序树的有序集合。

深度=h(h1)的K(K1)叉树至多有( -1)/(K-1)个结点。

包含n(n0)个结点的K(K1)叉树的最小深度为：

证：设有n个结点的K叉树的深度为h，若该树h-1层都是满的，即每层有最大结点数 -1(1h-1)，且其余结点都落在第h层，则该树的深度达最小，如图6.11所示：

或：(Kh-1 -1)

即：Kh-1

取对数：(h-1)

因为h为正整数，所以：h=

含有n(n 1)个结点的完全二叉树的深度

n个叶结点的非满的完全二叉树的高度是log2n+1。(最下层结点数=2)。

设完全二叉树BT结点数为n，结点按层编号。对BT中第i结点(1n)，注意结点编号从1开始，在数组存储时也是从数组1开始,若题目已然确定从0开始，则在计算孩子父亲结点时都需要重新变换一下。

有：

(1)若i=1，则i结点(编号为i的结点)是BT之根，无双亲;否则( i1)，parent(i)= ，即i结点双亲的编号为 ;

(2)若2in，则i结点无左子，否则Lchild(i)=2i，即i结点的左子位于第2i号结点;

(3)若2i+1n，则i结点无右子，否则Rchild(i)=2i+1，即i结点的右子位于第2i+1号结点。

证明：采用数学归纳法，先证(2)和(3)。

设n个结点的完全二叉树如图所示。

i=1时,显然 i 结点的左子编号为2，i的右子编号为2+1=3，除非2n , 3n 。

设对i结点，命题(2)、(3)成立，即Lchild(i)=2i，Rchild(i)=2i+1。根据按层编号规则，i+1时有：

Lchild(i+1)=(2i+1)+1=2(i+1)，除非2(i+1)n,

Rchild(i+1)=(2i+1)+1+1=2(i+1)+1，除非2(i+1)+1n，

故(2)、(3)得证。

再证(1)，它可看作是(2)、(3)的推广。

因Lchild(j)=2j，所以Parent(2j)=j,令2j=i，有 Parent(i)=i/2= (i/2为正整数);

又：Rchild(j)=2j+1，所以Parent(2j+1)=j，令2j+1=i (i=3,5,7)，有:

Parent(i)=(i-1)/2= ，证毕。

n

2i

2i+1

1

2

3

2i+1+1

2i+1+2

i

i+1

例题：一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )【西安交通大学 1996 三、2 (3分)】

A. 250 B. 500 C.254 D.505 E.以上答案都不对 501

例题1：由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。

例题2：高度为K的完全二叉树至少有_ __个叶子结点。(刚好第K上只有一个叶子时，高度为K，N= -1+1= 例题3：在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是

用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加虚结点。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是log2s=log2t。

二叉树的存储结构

1.顺序存储结构

用一组连续的存储单元(一维数组)存储二叉树中元素，称为二叉树的顺序存储结构。描述如下：

#define maxsige 1024 //二叉树结点数最大值//

typedef datatype sqtree [maxsize];

若说明sqtree bt; 则( bt[o] bt[1] bt[maxsize-1])为二叉树的存储空间。每个单元bt[i] 可存放类型为datatype的树中元素。

2.链式存储结构

二叉结中结点的一般形式为：

lchild

data

rchild

遍历的递归算法

void preorder( BTptr T) //对当前根结点指针为T的二叉树按前序遍历//

{

if (T) { visit(T); // 访问T所指结点 //

preorder(TLchild); //前序遍历T之左子树//

preorder(TRchild); //前序遍历T之右子树//

}

}

void Inorder (BTptr T) //对当前根结点指针为T的二叉树按中序遍历//

{

if (T) { Inorder( T- //中序遍历T之左子树//

visit(T); //访问T所指结点//

Inorder(T- //中序遍历T之右子树//

}

}

void postorder ( BTptr T) //对当前根结点指针为T的二叉树按后序遍历//

{

if (T) { postorder(TLchild); //后序遍历T之左子树//

postorder(TRchild); //后序遍历T之右子树//

visit(T); //访问T所指结点//

}

}

从上述三个算法中看出，若抹去 visit(T)语句，则三个算法是一样的，可以推断，这三个算法的递归路线是一致的(走的线路是一样的，只是对结点的访问时间不同而已，前序是第一次碰到就访问，中序是第一次返回时访问，后序是第二次返回时访问。

遍历非递归算法

1.前序遍历二叉树的非递归算法

算法思路：设一存放结点指针的栈S。从根开始，每访问一结点后，按前序规则走左子树，但若该结点右子树存在，则右子指针进栈，以便以后能正确地遍历相应放回到该右子树上访问。

算法描述: void Preoder-1(BTptr T) //前序非递归遍历二叉树T//

{ BTptr p;stacktype s;

Clearstack(s);

push(s,T); //置栈S为空、根指针T进栈//

while (!Emptystack(s) )

{ p=pop(s); //出栈,栈顶=P//

while (p)

{

visit (p); //访问p结点//

if (pRchild) push(s,pRchild); //右子存在时,进栈//

p=pLchild;

} //向左走//

}

}

说明：内部循环是从P结点出发一直走到最左，走的过程中保存了每一个右子树的地址，(因为右子树还没有被访问)而且是先进后出的，即先保存的比后保存的更先被用作返回地址，所以是用栈。外循环正好是当内部循环不下去的时候，退一栈的情形。即换成他的右子树

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

算法思路：同前序遍历,栈S存放结点指针。对每棵子树(开始是整棵二叉树)，沿左找到该子树在中序下的第一结点(但寻找路径上的每个结点指针要进栈)，访问之;然后遍历该结点的右子树，又寻找该子树在中序下的第一结点，...直到栈S空为止。

算法描述: void Inorder-1 (BTptr T) // 中序非递归遍历二叉树T//

{ BTptr p; stacktype s;

Clearstack(s);

push (s,T); //置栈S空、根指针进栈//

while (!Emptystack(s))

{

while ((p=Getstop (s)) p) // 取栈顶且栈顶存在时//

push(s,p- //p之左子指针进栈//

p=pop(s); //去掉最后的空指针//

if (!Emptystack (s))

{ p=pop(s); //取当前访问结点的指针=P//

visit(p); //访问P结点//

push(s,p- Rchild); //遍历P之右子树//

}

}

}

说明：和前序不一样，这里的栈保存的是根结点的地址(因为中序遍历先访问左子树，而根结点没有被访问到。而前序遍历不一样，他一开始就访问根结点，所以他不保存根结点的地址而是保存右子树的地址，因为右子树还没有被访问。总之，用栈就是为了帮我们保存还没有被访问的地址，以便将来我们能找到返回的地址)

3.后序遍历二叉树的非递归算法

算法思路：后序非递归遍历较之前序、中序算法要复杂一些。原因是对一个结点是否能访问，要看它的左、右子树是否遍历完，所以每结点对应一个标志位tag。tag=0，表示该结点暂不能访问;tag=1，表示该结点可以访问。其实是区分这次返回是遍历完左子树返回的还是遍历完右子树返回的，如果是左子树返回那么就不能访问根结点，如果是右子树返回的就能访问根结点。

当搜索到某P结点时，先要遍历其左子树，因而将结点地址P 及tag=0进栈;当P结点左子树遍历完之后，再遍历其右子树，又将地址P及tag=1进栈;当P结点右子树遍历完后(tag=1)，便可以对P结点进行访问。

栈元素类型： typedef struct

{BTptr q; // 存放结点地址 //

int tag; //存放当前状态位//

}stype ;

算法步骤如下：

①若二叉树T=(空树)，返回，算法终止;

②初始化：置栈S空，根指针T=

③反复以下过程，直到p=且栈S=时算法终止：

若p，(p,o)进栈，p=pLchild (遍历左子树) ，，直到 p=出栈, 栈顶=(p, tag);若tag=0，(p,1)进栈，p=pRchild(遍历右子树)，否则，访问p结点，并置p=。

算法描述：void postorder-1(BTptr T) //后序非递归遍历二叉树T//

{

int tag; BTptr p; stype sdata;

Clearstack (s); // 置栈空 //

p=T;

do {

while (p)

{

sdata.q=p; sdata.tag=0;

push (s, sdata); // (p,0)进栈//

p=pLchild; //遍历p之左子树//

}

sdata=pop(s); //退栈

p=sdata.q; //取指针

tag=sdata.tag;//状态位//

if (tag= =0)//从左子树返回时，根的tag=0

{

sdata. q=p;

sdata.tag=1; //这时要进入根的右子树了，所以将根的tag=1，

//下次碰到根时就可以访问了

push(s,sdata); // (p,1) 进栈,根还得进一次栈

p=pRchild; //遍历右子树//

}

else //tag=1，这时说明右子树访问完了后返回，所以这次要对根访问了

{

visit(p); //访问p结点//

p=NULL;//要再退到上层，因为该棵树已经彻底访问完了

} //之所以把p=null是不让他进入while

}while ( p|| !Emptystack(s));

}

例题：假设二叉树采用链式存储结构进行存储，root^为根结点，p^为任一给定的结点，

写出求从根结点到p^之间路径的非递归算法。

[题目分析]采用后序非递归遍历二叉树，栈中保留从根结点到当前结点的路径上所有结点。

void PrintPath(BiTree bt,p) //打印从根结点bt到结点p之间路径上的所有结点

{

BiTree q=bt,s[]; //s是元素为二叉树结点指针的栈，容量足够大

int top=0; tag[];//tag数组元素值为0或1，访问左、右子树标志，tag和s同步

if (q==p)

{ printf(q-

return;

} //根结点就是所找结点

while(q!=null || top0)

{

while(q!=null) //左子女入栈，并置标记

if(q==p) //找到结点p，栈中元素均为结点p 的祖先

{ printf(从根结点到p结点的路径为n

for(i=1;ii++)

printf(s[i]-

printf(q-

return;

}

else

{ s[++top]=q;

tag[top]=0;

q=qlchild;

} //沿左分支向下

while(top tag[top]==1))

top--;//本题不要求输出遍历序列，这里只退栈

if (top0)

{ q=s[top];

q=q-

tag[top]=1;

} //沿右分支向下

}//while(q!=null || top0)

}//结束算法PrintPath

按层次遍历二叉树

算法描述：

void Layerorder(BTptr T) //对二叉树T按层次遍历//

{

BTpfr p; qtype Q;

if (T)

{

Clearqueue (Q); //置队Q空//

Enqueue (Q,T); //将根指针进队//

while (!Emptyqueue(Q) )

{

p=Dequeue(Q); //出队，队头元素p//

visit (p); //访问p结点//

if (p-Lchild) Enqneue (Q,p- //左子指针进队//

if (p-Rchild) Enqneue (Q,p- //右子指针进队//

}

}

}

遍历算法的应用

凡是对二叉树中各结点进行一次处理的问题，都可以用遍历算法来完成。

1.利用遍历算法对二叉树中各类结点计数

设二叉树中出度=0、1、2的结点数分别为n0、 n1 和n2 ，初值均为0。

套用遍历算法(前序、中许、后序均可)，扫描到树中某p结点时，若：

if ((p-Lchild==NULL)(p-Rchild==NULL))

n0++; //p为叶子//

else if((p-Lchild)(p-Rchild))

n2++; //p为出度=2的结点//

else n1++; // p为出度=1的结点//

如：只要把遍历算法在遍历时稍微改变一下。

n0=n1=n2=0;

void preorder( BTptr T) //对当前根结点指针为T的二叉树按前序遍历//

{

if (T) { // visit(T); 访问T所指结点 //

if ((T-Lchild==NULL)(T-Rchild==NULL))

n0++; //p为叶子//

else if((T-Lchild)(T-Rchild))

n2++; //p为出度=2的结点//

else

n1++; // p为出度=1的结点//

preorder(TLchild); //前序遍历T之左子树//

preorder(TRchild); //前序遍历T之右子树//

}

}

2.前序遍历算法交换二叉树中各结点左、右子树(递归的交换)，对每一个结点都只需要一次访问就够了，所以用遍历算法稍微改一下，把VISIT改成我们要做的事就OK了

void preexchange (BTpfr T)

{

BTptr p;

if(T)

{ p=T-T-Lchild=T-T-Rchild = p;//交换当前T的左右子树//

preexchage(T- //处理左子树//

preexchage(T- //处理右子树//

}

}

例题1：一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )【南开大学 2000 一、2】

A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树

前序序列是根左右，后序序列是左右根，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B都不全。

例题2：某二叉树的前序序列和后序序列正好相反，则该二叉树一定是()的二叉树。【武汉大学2000二、4】

A.空或只有一个结点 B.任一结点无左子树 C.高度等于其结点数 D.任一结点无右子树

和上题类似的BD都可以但是是单选题就只能选C了

例题3：在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( )

A.都不相同　　B.完全相同 C.先序和中序相同，而与后序不同

D.中序和后序相同，而与先序不同

二叉树的线索化

线索化分成，前序线索化和中序线索化后序线索化，他们的区别在于每个结点的前驱和后继的不同，各种不同的遍历得到不同的前驱和后继。如果考手画线索化二叉树，则三种都有可能，如果考算法描述，那么就只能考中序线索化二叉树了(其它两个的比较繁琐)。

LchildLtagdataRtagRchild

我们讨论建立中序线索二叉树。

算法思路：利用中序递归遍历算法，即：

1线索化根的左子树 2 线索化当前结点 3 线索化根的右子树。

其中pre为外部指针(初值=NULL)，在算法运行中，pre为当前搜索结点的前驱指针。

算法描述：

typedef struct Bnode

{ int Ltag,Rtag; //左右特征位//

datatype data;

struct Bnode *Lchild,*Rchild ;

}BTnode , *BTptr;

总控函数:中序线索化二叉树另外加了一个结点(相当于循环链表的头结点)。

Status InorderTheaing(BinThrtree Thrt,BiThrTree T)

{

if(!(Thr=(BinThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);

Thrt-LTag=Link;Thrt-RTag=Threak;

Thrt-rchild=Thrt;//相当于空的循环链表，先将尾指针指向头结点。

if(!T) Thrt-lchild=Thrt;//空树那么整个也是空的了，只有一个附加的头结点了

else

{

Thrt-lchild=T;

pre=Thrt;//因为pre始终是当前结点的前驱结点，那么初始值就应该是头结点

Inthreadbt(T);将整个树线索化

pre-RTag=Thread;//当整个树都线索化了那么，pre肯定指向最后一个结点了

pre-rchhild=Thrt;//所以pre的后继应该是头结点

}

return OK;

}

void Inthreadbt (BTptr T) //中序线索二叉树//

{

if (T)

{

Inthreadbt(T-//线索化左子树//

visit(T); 改成 if(T-Lchild==NULL)

{

T-Ltag=Thread;

T-Lchild=pre;

}

if(pre -rchild= =NULL)

{ pre-RTag=Thread;

pre-Rchild=T;

}

pre=T;

Inthreadbt(T- //线索化右子树//

}

}

线索化二叉树的遍历

有了线索的二叉链表那么遍历就方便多了，不需要借助栈也不需要用递归了，因为他已经把前驱后继都连起来了，而不像二叉树那样，走不动的时候就只能退栈了。 而且遍历速度快。

算法思路：先找到中序下的第一结点，访问之;若被访问的结点的右指针为线索指针，直接取其后继结点访问;，直到被访问结点的右子树存在，再从相应右子起找中序下的第一结点，，依次类推，直到整个树遍历完毕。

算法描述：

BTptr Tinorder(BTptr Thrt) //对中序线索二叉树的遍历//

{

BTptr p=T- //P 指向的是根结点

while(p!=Thrt) //循环链表没有到头结点

{

while(p-Ltag==Link) p=p- //找到中序下的第一结点//

visit(p);

while(p-Rtag==Threadp-Rchild!=Thrt)//如果右指针指向的是后继结点

{ p=p- //那么就大胆的访问吧，取p后继结点,访问之//

visit(p);

}

p=p- // 如果不是后继结点，那么还得按照中序遍历的方法求得后继//

}

}

在中序线索二叉树中，每一非空的线索均指向其祖先结点。

在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点(该结点的后继指针指向祖先)，中序后继是其右子树上按中序遍历的最左边的结点(该结点的前驱指针指向祖先)。

非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。

树的存储结构

1.双亲表示法

树中结点形式：

其中data域存放结点的数据值(意义同前);parent域为该结点之父结点的地址(或序号)。描述如下：

typedef struct tnode

{ datatype data;

int parent ;

} PTnode ;

typedef struct

{ PTnode nodes[maxsize]; //树存储空间//

int n ; //当前树的结点数//

}Ptree ;

2孩子表示法

该表示法是采用链表结构来存储树的信息。

(1)固定指针数表示法：设树T的度为d(d叉树)，即树中任一结点最多发出d个分支，所以结点定义为： data

ch1

chd

(2)可变指针数表示法

结点形式： data

ch1

chd

d

其中d为本结点的出度，chi为第i个孩子结点的指针。

(3)孩子链表示法

该表示法将树中每一结点的诸孩子组成单链表，若树中结点数为n，则有n个孩子链表(叶结点的链表为空)。又将n个链表的头结点组成头结点表。

头结点形式： data

parent

fchild

其中data域存放结点的数据值;parent域为该结点之父结点的序号;fchild为指向本结点第一个孩子的指针。

typedef struct CTnode //链表结点//

{ int child;

struct CTnode * next;

} *Childptr ;

typedef struct //头结点//

{ datatype data; int parent;

Childptr firstchild;

} CTBox ;

typedef struct

{ CTBox nodes[maxsize]; //头结点数组//

int n ,root; //n为当前树中结点数，root为根结点所在位置//

}CTree;

..

3.孩子-兄弟表示法(或二叉树表示法

data

nextsibiling

fchild

结点形式(同二叉树链式结构)：

其中fchild为指向本结点第一孩子的指针，而nextsiling为指向本结点右兄弟的指针。

1.树T转换成二叉树BT(TBT)

转换方法：对树T中每一结点，除保留第一孩子外，断开它到其它孩子的指针，并将各兄弟连接起来。转换后，原结点的第一孩子为左子，而原结点的右兄弟为其右子。

在转换成的二叉树中，根结点的右子一定为空

2森林F转换成二叉树BT(FBT)

方法：先将F中各树转换成二叉树;然后各二叉树通过根的右指针相连。

3.二叉树BT恢复成森林F(BTF)

这是FBT的逆变换。

方法：对BT中任一结点，其Lchild所指结点仍为孩子，而Rchild所指结点为它的右兄弟，即左孩子，右兄弟。

先序遍历森林F

设F={ T1,T2,..,Tm }，其中Ti(1m)为F中第i棵子树。

方法：若F，则：

(1)访问F中T1之根;

(2)先序遍历T1之根下的各子树(子森林);

(3)先序遍历除T1之外的森林(T2,,Tm)。

显然(2)、(3)为递归调用，即：若子森林存在，仍按先序遍历方法对其遍历。

方法等价为：先将F转换二叉树BT，然后对BT按前序(DLR)遍历，其结果是一样的。

后序遍历森林F

方法：若F，则：

(1)后序遍历F中T1之根下的各子树(子森林);

(2)访问T1之根;

(3)后序遍历除T1之外的森林{ T2,,Tm }。

显然，(1)、(3)递归调用，即：若子森林存在，仍按后序遍历方法对其遍历。

此方法等价为：先将F转换成二叉树BT，然后对BT按中序(LDR)遍历

例题：设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有( C )个。 我不明白的题

A. n-1 B.n C. n+1 D. n+2

Huffman树

设H树中叶结点数为n(即给定的权值个数)，因H树中出度=1的结点数为0，出度=2的结点数为n-1，故H树中总的结点数m=2n-1。因而可将树中全部结点存储在一个一维数组中。因而可将树中全部结点存储在一个一维数组中。

由此写出构造H树的C语言描述算法：

void HuffmTree (huffm HT[m+1] ) //构造H树的算法//

{

int i, j, p1, p2; int w, s1, s2;

for (i=1,i=m,i++) //初始化//

{

HT[i]. wi=0;

HT[i].parent=0;

HT[i].Lchild=HT[i].Rchild=0;

}

for (i=1; i i++)

scanf(%d, HT[i]. wi ); //读入权值//

for (i=n+1; i i++) //进行n-1次循环，产生n-1个新结点，构造H树//

{

p1=p2=0; //p1、p2 为所选权值最小的根结点序号//

s1=s2=max; //设max为机器能表示的最大整数//

for(j=1;jj++) //从HT[1]~HT[i-1]中选两个权值最小的根结点//

if (HT[j].parent==0)

if (HT[j]. wi

{ s2=s1; p2=p1; //以j结点为第一个权值最小的根结点//

s1=HT[j].wi; p1=j;

}

else if (HT[j].wi

{

s2=HT[j].wi ;

p2=j; //以j为第二个权值最小的根//

}

HT[p1].parent=HT[p2].parent=i; //构造新树//

HT[i].Lchild=p1; HT[i].Rchild=p2;

HT[i].wi =HT[p1].wi +HT[p2].wi; //权值相加送新结点//

}

}

求Huffman编码的算法：

typedef struct

{ char bits[n+1]; //存放一个字符的Huffman编码

int start; //存放该字符编码的最后一个位置

char ch; //待编码字符//

}ctype;

void Huffmcode(ctype code[n+1]) //求n个字符的Huffman编码的算法//

{

int i, j, p, s; huffm HT[m+1]; //H树存储空间//

ctype md; //存放当前编码的变量//

for (i=1;i i++) //读入待编码的字符//

HT[i].data=code[i].ch=getchar( );

//从叶子到根逆向求每个字符的哈佛满编码

HuffmanTree(HT); //构造H树//

for (i=1;ii++) //求n个字符的Huffman编码//

{

md.ch=code[i].ch;

md.start=n-1; //就算是单支树最多也就是 n-1

s=i; //第i个字符地址(或下标)s//

p=HT[i].parent; //p为s之父结点地址//

while (p!=0) //p存在时//

{

md.start-- ;

if (HT[p].Lchild= =s)

md.bits[md.start]=0 //左走一步为0//

else

md.bits[md.start]=1 //右走一步为1//

s=p;

p=HT[p].parent; //求下一位//

}

strcpy(code[i],md) ; //存入第i字符的编码//

}

}

Huffman译码

译码是编码的逆运算。设电文(二进制码)已存入字符型文件fch中，译码过程：根据编码时建造的H树和相应的Huffman编码，从H树的根(序号为m)出发，逐个取电文中的二进制码，若当前二进制码=0，则走左子，否则走右子，一旦到达H树的叶结点，取相应叶结点中字符code[i].ch。重复上述译码过程，直到电文结束。算法如下：

void Transcode(HuffmTree HT[m+1],ctype code[n+1])

{ int i, chat c; FILE *fp;

if ((fp=fopen(fch,r))==NULL) Error(fch);

//打开文件fch，只读，文件指针fp，打不开时出错处理//

i=m; //取H树根结点序号//

while ((c=fgetc(fp))!=EOF) //读入一个二进制码//

{

if(c= =0)

i=HT[i].Lchild; //向左走//

else

i=HT[i].Rchild; //向右走//

if(HT[i].Lchild= =0) //HT[i]为叶子//

{ putchar (code[i].ch); //输出译出的字符//

i=m;

}

}

fclose(fp); //关闭文件fch//

if (HT[i].Lchild!=0) Error(HT); //电文结束i未达到叶结点，则电文有误//

}

第6章节有关数据结构算法，上文中为大家作了分析，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作，预祝大家都能够取得好成绩，加油!