二叉樹實(shí)驗(yàn)報(bào)告

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

2、iTree &T); /按先序次序輸入二叉樹中結(jié)點(diǎn)的值(一個(gè)字符)，空格字符表示空樹。/構(gòu)造二叉樹鏈表表示的二叉樹 T。Status PreOrderTraverse(BiTree T, status(*visit)(TElemType e);采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。先序遍歷二叉樹T,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅以次。一旦visit ()失敗，則操作失敗。Status PostOrderTraverse(BiTree T, status(*visit)(TElemType e);采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。后序遍歷二叉樹T,對(duì)

3、每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit一次且僅以次。一旦visit ()失敗，則操作失敗。先序遍歷二叉樹基本操作的遞歸算法Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)，/先序遍歷二叉樹 T 的遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù) visit。/最簡單的 visit 函數(shù)是：/ Status PrintElement(TElemType e) /輸出元素 e 的值/ printf(e);/實(shí)用時(shí)，加上格式竄/ return OK;/ 調(diào)用實(shí)例：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、 先序創(chuàng)建二叉樹 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(請(qǐng)輸入字符串:n);CreatBiTree(T);printf (“先序遍歷序列:n);PreTravel(T);printf(n);printf (“后序遍歷序列:n);Po