實驗三 二叉樹操作

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