實(shí)驗(yàn)三 二叉樹(shù)操作

實(shí)驗(yàn)三二叉樹(shù)操作實(shí)驗(yàn)時(shí)間：2011年4月28日12:50-15:50（地點(diǎn)：7-215）實(shí)驗(yàn)?zāi)康模豪斫舛鏄?shù)的邏輯特點(diǎn)和二叉樹(shù)的性質(zhì)；掌握二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)，掌握二叉樹(shù)的遍歷算法的遞歸與非遞歸實(shí)現(xiàn)具體實(shí)驗(yàn)題目：（任課教師根據(jù)實(shí)驗(yàn)大綱自己指定）每位同學(xué)按下述要求實(shí)現(xiàn)相應(yīng)算法：以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)二叉樹(shù)的創(chuàng)建、遍歷算法1）問(wèn)題描述：在主程序中提供下列菜單： 1…建立樹(shù) 2…前序遍歷樹(shù) 3…中序(非遞歸)遍歷樹(shù)4…后序遍歷樹(shù) 0…結(jié)束2）實(shí)驗(yàn)要求：定義下列過(guò)程：CreateTree():按從鍵盤輸入的前序序列，創(chuàng)建樹(shù)PreOrderTree()：前序遍歷樹(shù)（遞歸）InOrderTree()：中序(非遞歸)遍歷樹(shù)LaOrderTree():后序遍歷樹(shù)（遞歸）1）算法設(shè)計(jì)思路簡(jiǎn)介在建立建立二叉樹(shù)的函數(shù)時(shí)，開(kāi)始使二叉樹(shù)為空，str掃描完成循環(huán)，先定義左節(jié)點(diǎn)，再定義右節(jié)點(diǎn)，p指向二叉樹(shù)的根結(jié)點(diǎn)，在建立輸出二叉樹(shù)的函數(shù)時(shí)，用括號(hào)法表示，先序遍歷遞歸順序是根，左，右，中序是左，根，右，后序是左，右，根。2）算法描述：可以用自然語(yǔ)言、偽代碼或流程圖等方式voidCreateBTNode(BTNode*&b,char*str)//由str串創(chuàng)建二叉樹(shù)voidDispBTNode(BTNode*b)//以括號(hào)表示法輸出二叉樹(shù)voidPreOrder(BTNode*b)//先序遍歷遞歸算法voidInOrder1(BTNode*b)//中序遍歷非遞歸算法voidPostOrder(BTNode*b)//后序遍歷遞歸算法3）算法的實(shí)現(xiàn)和測(cè)試結(jié)果：包括算法運(yùn)行時(shí)的輸入、輸出，實(shí)驗(yàn)中出現(xiàn)的問(wèn)題及解決辦法等二叉樹(shù)不能完全輸出，見(jiàn)截圖，我考慮過(guò)是由于字符串的長(zhǎng)度問(wèn)題影響，但經(jīng)過(guò)調(diào)整發(fā)現(xiàn)不是這里的問(wèn)題。代碼源：#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;//數(shù)據(jù)元素structnode*lchild;//指向左孩子structnode*rchild;//指向右孩子}BTNode;voidCreateBTNode(BTNode*&b,char*str)//由str串創(chuàng)建二叉樹(shù){BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;//建立二叉樹(shù)初始時(shí)為空ch=str[j];while(ch!='\0')//str未掃描完成循環(huán){switch(ch){case'(':top++;St[top]=p;k=1;break;//為左節(jié)點(diǎn)case')':top--;break;case',':k=2;break;//為右節(jié)點(diǎn)default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)//p指向二叉樹(shù)根結(jié)點(diǎn)b=p;else//以建立二叉樹(shù)根結(jié)點(diǎn){switch(k){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}voidDispBTNode(BTNode*b)//以括號(hào)表示法輸出二叉樹(shù){ if(b!=NULL) {printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) {printf("("); DispBTNode(b->lchild); if(b->rchild!=NULL)printf(","); printf(")"); } } }voidPreOrder(BTNode*b)//先序遍歷遞歸算法{ if(b!=NULL) {printf("%c",b->data);//訪問(wèn)根結(jié)點(diǎn) PreOrder(b->lchild);//遞歸訪問(wèn)左子數(shù) PreOrder(b->rchild);//遞歸訪問(wèn)右子數(shù) }}voidInOrder1(BTNode*b)//中序遍歷非遞歸算法{ BTNode*St[MaxSize],*p; inttop=-1; if(b!=NULL) {p=b; while(top>-1||p!=NULL) {while(p!=NULL) {top++; St[top]=p; p=p->lchild; } if(top>-1) {p=St[top]; top--; printf("%c",p->data); p=p->rchild; } }printf("\n"); }}voidPostOrder(BTNode*b)//后序遍歷遞歸算法{ if(b!=NULL) {PostOrder(b->lchild);//遞歸訪問(wèn)左子數(shù) PostOrder(b->rchild);//遞歸訪問(wèn)右子數(shù) printf("%c",b->data);//遞歸訪問(wèn)根結(jié)點(diǎn) }}voidmain(){ BTNode*b; CreateBTNode(b,"A(B(D,E(H(J,k(L,M(,N))))),C(F,G(,I)))"); printf("二叉樹(shù)b:"); DispBTNode(b); printf("\n"); printf("先序遍歷序列：\n"); print