大學(xué)c語言程序設(shè)計(jì)第五版課件 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)六

實(shí)驗(yàn)六二叉樹實(shí)驗(yàn)六二叉樹抽象數(shù)據(jù)類型的定義與實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康呐c要求（1）熟練掌握建立二叉樹的方法和實(shí)現(xiàn)算法。（2）熟練掌握二叉樹在二叉鏈表存儲(chǔ)結(jié)構(gòu)中的常用遍歷方法：先序遍歷、中序和層次遍歷、后序遍歷。（3）掌握遍歷算法的應(yīng)用：統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)數(shù)目、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)數(shù)目、輸出二叉樹中葉子結(jié)點(diǎn)、計(jì)算二叉樹的深度等。

（4）思考并記錄實(shí)驗(yàn)中遇到的問題，討論解決的方法。

（5）加深對(duì)“數(shù)據(jù)結(jié)構(gòu)+算法=程序”的理解和認(rèn)識(shí)，提高編寫較復(fù)雜程序的能力。實(shí)驗(yàn)內(nèi)容二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)定義如下：#defineTRUE1#defineFLASE0typedef

structNode{

chardata;

structNode*LChild;

structNode*RChild;}BiTNode,*BiTree;1.測(cè)試數(shù)據(jù)為了實(shí)現(xiàn)對(duì)二叉樹的有關(guān)操作，首先要在計(jì)算機(jī)中建立所需的二叉樹。建立二叉樹有各種不同的方法。一種算法是采用擴(kuò)展的先序遍歷結(jié)果建立二叉樹。當(dāng)某結(jié)點(diǎn)的某孩子為空時(shí)以數(shù)據(jù)@來充當(dāng)，也要輸入。測(cè)試數(shù)據(jù)：ABC@@DE@G@@F@@@(其中@表示空格字符)1.測(cè)試結(jié)果2.建立二叉樹voidCreateBiTree(BiTree*bt){}3.先序遍歷二叉樹voidPreOrder(BiTreeroot){}4.中序遍歷二叉樹voidInOrder(BiTreeroot){}5.后序遍歷二叉樹voidPostOrder(BiTreeroot){}6.統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)數(shù)目int

leaf(BiTreeroot){}7.計(jì)算二叉樹深度int

PostTreeDepth(BiTree

bt){}8.按層次遍歷二叉樹（需要隊(duì)列實(shí)現(xiàn)）voidPrintTree1(BiTreeroot){}9.二叉樹遍歷voidPrintTree2(BiTreeroot,int

nLayer){}9.二叉樹遍歷voidPrintTree2(BiTreeroot,int

nLayer){}10.主函數(shù)voidmain(){

BiTreeR;

int

number,height;

R=(BiTree)malloc(sizeof(BiTNode));

printf("TheTreeis:\n");

CreateBiTree(&R);

printf("The

PreOrderis:\n");

PreOrder(R);

printf("\n");

printf("The

InOrderis:\n");

InOrder(R);

printf("\n");

printf("The

PostOrderis:\n");

PostOrder(R);

printf("\n");

printf("TheLeafsofthetree:\n");

preorderleaf(R);

printf("\n");number=leaf(R);

printf("Thenumberofleafsis%5d",number);

printf("\n");height=PostTreeDepth(R);

printf("Theheightofzhetreeis:%5d",height);

printf("\n");

printf("Theleveltraverseresultis:\n");PrintTree1(R);

printf("\n**