實(shí)驗(yàn)四 二叉樹的建立與遍歷.doc

《實(shí)驗(yàn)四 二叉樹的建立與遍歷.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、實(shí)驗(yàn)四二叉樹的建立與遍歷【實(shí)驗(yàn)?zāi)康摹縧掌握二叉樹的定義、性質(zhì)及存儲(chǔ)方式，各種遍歷算法?！緦?shí)驗(yàn)內(nèi)容】１．采用二叉樹鏈表作為存儲(chǔ)結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序遍歷的遞歸操作。２．分別求所有葉子結(jié)點(diǎn)及結(jié)點(diǎn)總數(shù)的操作。提示：設(shè)計(jì)一顆二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(diǎn)（空指針），如ABD###CE##F##，建立二叉樹，求出先序、中序和后序遍歷序列，求所有葉子及結(jié)點(diǎn)總數(shù)?！境绦蛟创a】#include#includetypedefcharTElemType;typedefintStatus;#defi

2、neOK1#defineERROR0#defineOVERFLOW0typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;StatusCreateBiTree(BiTree&BT);voidCountLeaves(BiTreeBT,int&count);intNodeCount(BiTreeBT);voidPreOrder(BiTreeBT);voidInOrder(BiTreeBT);voidPostOrder(BiTreeBT);intmai

3、n(){BiTreeBT;intchoice,cho;intlogo=1;printf("輸入二叉樹結(jié)點(diǎn)，以'#'為空指針");CreateBiTree(BT);do{printf("t1:遍歷二叉樹");printf("t2：二叉樹總結(jié)點(diǎn)數(shù)及葉子節(jié)點(diǎn)數(shù)");printf("t3：退出程序");printf("t輸入選項(xiàng):");scanf("%2d",&choice);switch(choice){case1:printf("1:先序遍歷");printf("2:中序遍歷");printf("3:后序遍歷");sca

4、nf("%2d",&cho);switch(cho){case1:PreOrder(BT);printf("");break;case2:InOrder(BT);printf("");break;case3:PostOrder(BT);printf("");break;default:printf("輸入錯(cuò)誤!");}break;case2:intcount;printf("總結(jié)點(diǎn)數(shù)為:%2d",NodeCount(BT));CountLeaves(BT,count);printf("葉子結(jié)點(diǎn)數(shù)為:%2d",count);bre

5、ak;case3:exit(0);break;default:printf("輸入錯(cuò)誤!");}}while(logo==1);return0;}StatusCreateBiTree(BiTree&BT){charch;scanf("%c",&ch);if(ch=='#')BT=NULL;else{if(!(BT=(BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);BT->data=ch;CreateBiTree(BT->lchild);CreateBiTree(BT->rchild);}returnOK

6、;}voidPreOrder(BiTreeBT){if(BT!=NULL){printf("%c",BT->data);PreOrder(BT->lchild);PreOrder(BT->rchild);}}voidInOrder(BiTreeBT){if(BT!=NULL){PreOrder(BT->lchild);printf("%c",BT->data);PreOrder(BT->rchild);}}voidPostOrder(BiTreeBT){if(BT!=NULL){PreOrder(BT->lchild);PreOrder(BT->rch

7、ild);printf("%c",BT->data);}}voidCountLeaves(BiTreeBT,int&count){if(BT){if(!BT->lchild&&!BT->rchild)count++;CountLeaves(BT->lchild,count);CountLeaves(BT->rchild,count);}}intNodeCount(BiTreeBT)//統(tǒng)計(jì)總結(jié)點(diǎn)數(shù){if(BT==NULL)return0;elsereturn(NodeCount(BT->lchild)+NodeCount(BT->rchild)+1);

8、}【運(yùn)行結(jié)果分析】【實(shí)驗(yàn)收獲與心得】在本次實(shí)驗(yàn)中，我對(duì)遞歸這個(gè)概念有了較為深刻的認(rèn)識(shí)，對(duì)二叉樹