1、二叉樹的創建與遍歷一、試驗內容 根據輸入的字符串創建樹或二叉樹，輸出樹或二叉樹的先序遍歷和后 序遍歷序列。二、運行環境Visual C+三、需求分析1、建立一棵用二叉鏈表方式存儲的二叉樹。2、從鍵盤接受擴展先序序列，以二叉鏈表作為存儲結構。3、建立二叉樹，并將遍歷結果打印輸出。采用遞歸和非遞歸兩種 方法實現。四、設計概要/二叉樹的二叉鏈表存儲表示typedef struct BiTBodeTElemType data;Struct BiTNode *lchild, *rchild /左右孩子指針BiTNode, *BiTree;/基本操作的函數原型說明Status CreateBiTree(B

2、iTree &T); /按先序次序輸入二叉樹中結點的值(一個字符)，空格字符表示空樹。/構造二叉樹鏈表表示的二叉樹 T。Status PreOrderTraverse(BiTree T, status(*visit)(TElemType e);采用二叉鏈表存儲結構，visit是對結點操作的應用函數。先序遍歷二叉樹T,對每個結點調用函數visit一次且僅以次。一旦visit ()失敗，則操作失敗。Status PostOrderTraverse(BiTree T, status(*visit)(TElemType e);采用二叉鏈表存儲結構，visit是對結點操作的應用函數。后序遍歷二叉樹T,對

3、每個結點調用函數visit一次且僅以次。一旦visit ()失敗，則操作失敗。先序遍歷二叉樹基本操作的遞歸算法Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)采用二叉鏈表存儲結構，visit是對數據元素操作的應用函數，/先序遍歷二叉樹 T 的遞歸算法，對每個數據元素調用函數 visit。/最簡單的 visit 函數是：/ Status PrintElement(TElemType e) /輸出元素 e 的值/ printf(e);/實用時，加上格式竄/ return OK;/ 調用實例：PreOrderTraverse(T

4、,PrintElement); if(T) if (visit(T-data)if(PreOrderTraverse(T-lchild,visit) if(PreOrderTraverse(T-rchild,visit) return OK;return ERROR;else return OK; /PreOrderTraverse五、源程序代碼#include#includetypedef struct BiTNode char data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;void CreatBiTree(BiTree &T) /

5、 先序創建二叉樹 char ch;if(ch=getchar()=n) T=NULL;else T=(BiTNode*)malloc(sizeof(BiTNode); if(!T) exit(1);T-data=ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);void PreTravel(BiTree &T) / 先序遍歷 if(T)printf(%c,T-data);PreTravel(T-lchild);PreTravel(T-rchild);void PostTravel(BiTree &T) / 后序遍歷if(T)PostTravel(T-lchild);PostTravel(T-rchild); printf(%c,T-data);void main() BiTree T;printf(請輸入字符串:n);CreatBiTree(T);printf (“先序遍歷序列:n);PreTravel(T);printf(n);printf (“后序遍歷序列:n);Po