二叉樹實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)題目建立一棵用二叉鏈表方式存儲(chǔ)的二

叉樹，并進(jìn)行遍歷（先序、中序、后通工班內(nèi)序號(hào)：學(xué)生姓名:一、 實(shí)驗(yàn)?zāi)康恼莆沼枚骀湵韯?chuàng)建二叉樹；掌握對(duì)樹的遍歷，先序、中序、后序、層次，用遞歸和算法。二、 實(shí)驗(yàn)內(nèi)容從鍵盤接受輸入先序序列，以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以先序來(lái)建立）并對(duì)其進(jìn)行遍歷（先序、中序、后序、層次），然后將遍歷結(jié)果打印輸出。要求采用遞歸和非遞歸兩種方法實(shí)現(xiàn)。例如：測(cè)試數(shù)據(jù)：ABC..DE.G.F…輸出結(jié)果：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA層次：ABCDEFG三、 數(shù)據(jù)結(jié)構(gòu)及算法思想創(chuàng)建函數(shù)的思想：首先讀入當(dāng)前根結(jié)點(diǎn)的數(shù)據(jù)，如果是''，則將當(dāng)前樹根置為空，否則申請(qǐng)一個(gè)空結(jié)點(diǎn)，存入當(dāng)前根結(jié)點(diǎn)的數(shù)據(jù)，分別用當(dāng)前根結(jié)點(diǎn)的左子域和右子域進(jìn)行遞歸調(diào)用，創(chuàng)建左右子樹。二叉樹的遍歷方法是：按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次的過程。根據(jù)訪問結(jié)點(diǎn)的順序分為先序遍歷、中序遍歷和后序遍歷先序遍歷：訪問根結(jié)點(diǎn)按先序遍歷左子樹；按先序遍歷右子樹；中序遍歷：按中序遍歷左子樹；訪問根結(jié)點(diǎn)；按中序遍歷右子樹；后序遍歷：按后序遍歷左子樹；按后序遍歷右子樹；訪問根結(jié)點(diǎn)；四、 模塊劃分對(duì)各個(gè)模塊進(jìn)行功能的描述voidGreateBiTree(BiTree*bt)〃建立二叉樹voidPreOrder(BiTreeroot)//先序遍歷voidInOrder(BiTreeroot)//中序遍歷voidPostOrder(BiTreeroot)//后序遍歷模塊之間關(guān)系及其相互調(diào)用的，定義結(jié)構(gòu)主函數(shù)先序遍歷中序遍歷后序遍歷該樹可以表示為:運(yùn)用遞歸算法，以先序?yàn)槔?五、詳細(xì)設(shè)計(jì)及運(yùn)行結(jié)果程序設(shè)計(jì)及編碼，測(cè)試數(shù)據(jù)，運(yùn)行結(jié)果測(cè)試數(shù)據(jù)：ABC..DE.G.F…輸出結(jié)果：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA層次：ABCDEFG六、調(diào)試情況，設(shè)計(jì)技巧及體會(huì)這次試驗(yàn)讓我對(duì)二叉樹的遍歷有了很好的了解，對(duì)于先序，中序，后序和層次遍歷有了好的掌握。編寫代碼前，應(yīng)簡(jiǎn)單的畫一個(gè)二叉樹，先弄清算法思想，在開始編程，應(yīng)先對(duì)于各個(gè)模塊進(jìn)行設(shè)計(jì)，調(diào)試，消除錯(cuò)誤，當(dāng)所有模塊都設(shè)計(jì)完成后，選擇正確的變量把所有模塊連接在一起，程序就設(shè)計(jì)完成，這樣才不會(huì)出現(xiàn)太多的錯(cuò)誤，編程完以后，出現(xiàn)錯(cuò)誤要知道調(diào)試，以得到正確結(jié)果。附:代碼#include<stdio.h>#include<stdlib.h>#include<string.h>#defineStack_Size50#defineMAXSIZE50typedefstructNode{chardata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;voidGreateBiTree(BiTree*bt){charch;ch=getchar();if(ch=='')*bt二NULL;else{(*bt)=(BiTree)malloc(sizeof(BiTNode));(*bt)->data二ch;GreateBiTree(&((*bt)->LChild));GreateBiTree(&((*bt)->RChild));}}voidPreOrder(BiTreeroot){if(root!二NULL){printf("%c",root->data);PreOrder(root->LChild);PreOrder(root->RChild);}}voidInOrder(BiTreeroot){if(root!二NULL){InOrder(root->LChild);printf("%c",root->data);InOrder(root->RChild);}}voidPostOrder(BiTreeroot){if(root!二NULL){PostOrder(root->LChild);PostOrder(root->RChild);printf("%c",root->data);}}voidmain(){inti;BiTreeroot;printf("CreateBin_Tree;InputPreOrder:");GreateBiTree(&root);do{printf("\t**********select************\n");printf("\tl:PreOrderTraversal\n");printf("\t2:InOrderTraversal\n");printf("\t3:PostOrdertraversal\n");printf("\tO:Exit\n");printf("\t*******************************\n");scanf("%d"，&i);switch(i){case1:printf("PrintBin_treePreOrder:");PreOrder(root);break;case2:printf("PrintBin_TreeInOrder:");InOrder(root);break;cas