實驗四二叉樹的建立與遍歷.doc

《實驗四二叉樹的建立與遍歷.doc》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、..實驗四二叉樹的建立與遍歷【實驗目的】l掌握二叉樹的定義、性質及存儲方式，各種遍歷算法?！緦嶒瀮热荨浚保捎枚鏄滏湵碜鳛榇鎯Y構，完成二叉樹的建立，先序、中序和后序遍歷的遞歸操作。２．分別求所有葉子結點及結點總數(shù)的操作。提示：設計一顆二叉樹，輸入完全二叉樹的先序序列，用#代表虛結點（空指針），如ABD###CE##F##，建立二叉樹，求出先序、中序和后序遍歷序列，求所有葉子及結點總數(shù)?！境绦蛟创a】#include#includetypedefcharTElemType;typed

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

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

4、先序遍歷");printf("2:中序遍歷");printf("3:后序遍歷");scanf("%2d",&cho);switch(cho){case1:PreOrder(BT);printf("");break;case2:InOrder(BT);printf("");break;case3:a..PostOrder(BT);printf("");break;default:printf("輸入錯誤!");}break;case2:intcount;printf("總結點數(shù)為:%2d",N

5、odeCount(BT));CountLeaves(BT,count);printf("葉子結點數(shù)為:%2d",count);break;case3:exit(0);break;default:printf("輸入錯誤!");}}while(logo==1);return0;}StatusCreateBiTree(BiTree&BT){charch;scanf("%c",&ch);a..if(ch=='#')BT=NULL;else{if(!(BT=(BiTree)malloc(sizeof(BiTNode))))

6、exit(OVERFLOW);BT->data=ch;CreateBiTree(BT->lchild);CreateBiTree(BT->rchild);}returnOK;}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->da

7、ta);PreOrder(BT->rchild);a..}}voidPostOrder(BiTreeBT){if(BT!=NULL){PreOrder(BT->lchild);PreOrder(BT->rchild);printf("%c",BT->data);}}voidCountLeaves(BiTreeBT,int&count){if(BT){if(!BT->lchild&&!BT->rchild)count++;CountLeaves(BT->lchild,count);CountLeaves(BT->rchild

8、,count);}}intNodeCount(BiTreeBT)//統(tǒng)計總結點數(shù){if(BT==NULL)return0;elsea..return(NodeCount(BT->lchild)+NodeCount(BT->rchild)+1);}【運行結果分析】a..【實驗收獲與心得】在本次實驗中，我對