數(shù)據(jù)結(jié)構(gòu)試驗三樹與二叉樹的操作試驗指導(dǎo)

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)試驗三樹與二叉樹的操作試驗指導(dǎo)試驗六樹與二叉樹

6.1試驗?zāi)康模?/p>

（1）把握二叉樹鏈表的結(jié)構(gòu)和二叉樹的建立過程；

（2）把握二叉樹的基本操作，加深對二叉樹的理解，逐步培養(yǎng)解決實際問題的編程能力。

6.2試驗要求：

（1）復(fù)習(xí)課本中有關(guān)樹與二叉樹的知識；

（2）用C語言完成算法和程序設(shè)計并上機調(diào)試通過；

（3）撰寫試驗報告，給出算法思路或流程圖和具體實現(xiàn)（源程序）、算法分析結(jié)果（包括

時間繁雜度、空間繁雜度以及算法優(yōu)化設(shè)想）、輸入數(shù)據(jù)及程序運行結(jié)果（必要時給出多種可能的輸入數(shù)據(jù)和運行結(jié)果）。

6.3基礎(chǔ)試驗

[試驗1]二叉樹的構(gòu)造

試驗內(nèi)容與要求:

按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹T；分析:

二叉樹是每個結(jié)點至多只有兩棵子樹，并有左、右之分，順序不能任意顛倒的一種非線性結(jié)構(gòu)。二叉樹常用的存儲結(jié)構(gòu)是二叉鏈表形式，二叉鏈表由一個數(shù)據(jù)項data（用于存放結(jié)點的值）和兩個指針項lchild、rchild（分別指向該結(jié)點的左、右子樹）。結(jié)點及結(jié)構(gòu)如圖6-1所示：

datalchildrchilddata

rchildlchild圖6-1含有兩個指針的二叉樹的結(jié)點及結(jié)構(gòu)

//------二叉樹的二叉鏈表存儲表示模型-------typedefstructBiTNode{TElemTypedata;

StructBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;

將此結(jié)構(gòu)定義放在一個頭文件BiTNode.h里，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出二叉鏈表的初始化及常量的定義。實現(xiàn)提醒

按先序序列建立一棵二叉樹，先構(gòu)造根結(jié)點，再構(gòu)造根的左、右子樹；每一棵子樹又都是一顆二叉樹，所以構(gòu)造一棵子樹的過程與構(gòu)造整棵二叉樹的過程完全一致，依照先序序列，先構(gòu)造根，再構(gòu)造左子樹，然后構(gòu)造右子樹；采用遞歸形式直到葉子結(jié)點為止。以下是算法描述：

StatusCreateBiTree(BiTree

if(ch=='＃')T=NULL;else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//生成根結(jié)點CreateBiTree(T->lchild);//生成左子樹CreateBiTree(T->rchild);//生成右子樹}

returnOK;

}//CreateBiTree參考程序：

//頭文件BiTNode.h的內(nèi)容如下：

#include#include#include#defineMAX20#defineOK1#defineERROR0#defineNULL0

#defineOVERFLOW0typedefcharTElemType;typedefintStatus;typedefstructBiTNode{TElemTypedata;

structBiTNode*lchild,*rchild;}BiTNode,*BiTree;

BiTreeCreateBiTree(BiTreeT){

charch;

scanf(\

if(ch=='#')T=NULL;/*#代表空指針*/else{

T=(BiTNode*)malloc(sizeof(BiTNode));

if(!T)exit(OVERFLOW);/*申請結(jié)點*/T->data=ch;/*生成根結(jié)點*/T->lchild=CreateBiTree(T->lchild);/*構(gòu)造左子樹*/T->rchild=CreateBiTree(T->rchild);/*構(gòu)造右子樹*/}}

//以下是主程序shiyan6_1_1.c#include\main(){

2

BiTreeT=NULL;

printf(\請讀入構(gòu)造二叉樹的字符序列：\CreateBiTree(T);/*建立一棵二叉樹T*/

}

[試驗2]二叉樹的遍歷

試驗內(nèi)容與要求:

對一棵二叉鏈表表示的二叉樹進行先序遍歷、中序遍歷、后序遍歷和層序遍歷并分別輸出遍歷的結(jié)點順序。

分析：

二叉樹的先序遍歷是：若二叉樹為空，則空操作；否則，訪問根結(jié)點，先序遍歷左子樹，先序遍歷右子樹。

二叉樹的中序遍歷是：若二叉樹為空，則空操作；否則，中序遍歷左子樹，訪問根結(jié)點，中序遍歷右子樹。

二叉樹的后序遍歷是：若二叉樹為空，則空操作；否則，后序遍歷左子樹，后序遍歷右子樹；訪問個結(jié)點。

二叉樹的層序遍歷是：在訪問二叉樹的結(jié)點時依照自上而下，從左至右的順序。根作為第一層，根的孩子作為其次層，以此類推。先序遍歷二叉樹遞歸算法

StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)，//先序遍歷二叉樹T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦visit()失敗，則操作失敗。if(T){

if(Visit(T->data))

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

if(PreOrderTraverse(T->rchild，Visit))returnOK;

returnERROR;}elsereturnOK;}//PreOrderTraverse中序遍歷的遞歸算法

StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){

if(InOrderTraverse(T->rchild，Visit))

3

if(Visit(T->data))

if(InOrderTraverse(T->rchild，Visit))returnOK;returnERROR;}elsereturnOK;}//InOrderTraverse后序遍歷遞歸算法

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

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

if(PostOrderTraverse(T->rchild，Visit))if(Visit(T->data))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse

層次遍歷二叉樹的非遞歸算法StatusLevelOrder(BiTreeT){//按層次遍歷二叉樹T，Q為隊列InitQueue(Q);

If(T!=NULL){//若樹非空

EnQueue(Q,T);//根結(jié)點入隊列While(!QueueEmpty(Q)){

DeQueue(Q,b);//隊首元素出隊列Visit(b->data);//訪問結(jié)點

If(b->lchild!=NULL)EnQueue(Q,b->lchild);//左子樹非空，則入隊列If(b->rchold!=Null)EnQueue(Q,b->rchild);//右子樹非空，則入隊列}//while}//if}LevelOrder

參考程序：

//以下代碼保存在文件shiyan6_1_2.c

#include#include\

StatusPrintElement(TElemTypee){

4

printf(\returnOK;}

StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){

inti,j,k;

if(T==NULL)returnOK;else{

i=Visit(T->data);if(i){

j=PreOrderTraverse(T->lchild,Visit);/*先序遍歷左子樹*/if(j){

k=PreOrderTraverse(T->rchild,Visit);/*先序遍歷右子樹*/if(k)returnOK;}}

elsereturnERROR;}}

StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){/*中序遍歷*/if(T){

if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))

if(InOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}

elsereturnOK;}

StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){/*后序遍歷*/if(T){

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

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

elsereturnOK;

5

{//對str所代表的字符串進行編碼并寫入磁盤文件inti,j;FILE*fp;

fp=fopen(“codefile.txt〞,〞w〞);while(*str){

for(i=1;i=’A’tepm[k]++;}j=0;

for(i=1,j=0;i0)//直至回朔到HT[c]的根為止{//若HT[c]是HT[p]的左孩子,則生成0,否則生成代碼1cd[--start]=(HT[p].lchild==c)?’0’:’1’;c=p;}

strcpy(HC[i].bits,HC[i].len=num-start;}}

voidcoding(HuffmanCodeHC,char*str)

{//對str所代表的字符串進行編碼并寫入磁盤文件inti,j;FILE*fp;

fp=fopen(“codefile.txt〞,〞w〞);while(*str){

for(i=1;iinti,j,k=0,cjs;

fp=fopen(“codefile.txt〞,〞r〞);while(!fopen(fp)){

cjs=0;//一個字符的編碼是否讀終止for(i=0;i#include

#include“shiyan6_2_1.h〞#include“shiyan6_2_2.h〞voidmain(){

charst[254],*s,str[27];intcn[27];

HuffmanTreeHT;HuffmanCodeHC

21

printf(“輸入電文（均為大寫字母）：\\n〞);gets(st);

num=jsp(st,cn,str);

ChuffmanTree(HT,HC,cn,str);HuffmanEncoding(HT,hc);coding(HC,st);s=decode(HC);

printf(“譯碼后的字符串：\\n〞);printf(“%s\\n〞,s);}

6.5思考題：

（1）若以中序序列該如何建立一棵二叉樹?（試驗1）

（2）如何實現(xiàn)二叉樹中序遍歷的非遞歸形式？（試驗2）中序遍歷非遞歸算法之一

StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);

Push(S,T);//根指針進棧While(!StackEmpty(S)){

While(GetTop(S,p)//向左走到終點Pop(S,p);//空指針退棧

If(!StackEmpty(S)){//訪問結(jié)點，向右一步Pop(S,p);

If(!Visit(p->data))returnER