二叉樹的創(chuàng)建與遍歷操作.doc

年級11級班號 2學(xué)號11064061專業(yè)自動(dòng)化姓名馬俊杰實(shí)驗(yàn)名稱二叉樹的創(chuàng)建和遍歷實(shí)驗(yàn)類型設(shè)計(jì)型綜合型創(chuàng)新型實(shí)驗(yàn)?zāi)康幕蛞髮?shí)驗(yàn)要求：1）從鍵盤輸入二叉樹的各結(jié)點(diǎn)值，按先序遞歸方式創(chuàng)建二叉樹2）分別實(shí)現(xiàn)先序、中序、后序遞歸遍歷二叉樹3）輸出二叉樹的高度4）輸出二叉樹的按層次遍歷序列*5）以菜單方式運(yùn)行先序方式創(chuàng)建二叉樹： 輸入結(jié)點(diǎn)值的順序必須對應(yīng)二叉樹先序遍歷的順序，并約定以某個(gè)字符（如 或等）作為空子樹. 例如：對于右圖中的二叉樹, 按下列順序輸入字符: ABCDEGF ，創(chuàng)建二叉樹。ABCDEFG實(shí)驗(yàn)原理（算法流程）#include #include #include #define maxsize 1024typedef char datatype;typedef struct nodedatatype data;struct node *lchild,*rchild;bitree;void menu()printf(本代碼實(shí)現(xiàn)二叉樹的如下基本功能，請選擇對應(yīng)的功能選項(xiàng)進(jìn)行相應(yīng)操作：n);printf(1.按先序遞歸方式創(chuàng)建二叉樹n);printf(2.先序遞歸遍歷n);printf(3.中序遞歸遍歷n);printf(4.后序遞歸遍歷n);printf(5.按層次遍歷n);printf(6.輸出二叉樹高度n);printf(0.退出程序n);bitree *Creat()char ch;bitree *T;scanf(%c,&ch);if(ch=)T=NULL;elseT=(bitree*)malloc(sizeof(bitree);T-data=ch;T-lchild=Creat();T-rchild=Creat();return T; void preorder(bitree *T)if(T!=NULL)printf(%c,T-data);preorder(T-lchild);preorder(T-rchild);return;void inorder(bitree *T)if(T!=NULL)inorder(T-lchild);printf(%c,T-data);inorder(T-rchild);return;void postorder(bitree *T)if(T!=NULL)postorder(T-lchild);postorder(T-rchild);printf(%c,T-data);return;void levelorder(bitree *T) bitree *q20;int front=0,rear=0;if(T!=NULL) rear+;qrear=T;while(front!=rear)front+;T=qfront; printf(%c,T-data);if(T-lchild)rear+;qrear=T-lchild;if(T-rchild)rear+;qrear=T-rchild;int fstdepth(bitree *T)int d1,d2;if(T=NULL) return 0;elsed1=fstdepth(T-lchild);d2=fstdepth(T-rchild);return 1+(d1d2?d1:d2); void main()int choice=0,dep;bitree *T;menu();printf(本代碼實(shí)現(xiàn)二叉樹的幾個(gè)基本功能，請選擇對應(yīng)的功能選項(xiàng)進(jìn)行相應(yīng)操作：);fflush(stdin);scanf(%d,&choice);getchar();while(1)switch(choice)case 1:printf(請按先序遞歸方式輸入二叉樹各結(jié)點(diǎn)：n);T=Creat();printf(二叉樹創(chuàng)建n);break;case 2:preorder(T);break;case 3:inorder(T);break;case 4:postorder(T);break;11111111111111case 5:levelorder(T);break;case 6:dep=fstdepth(T);printf(二叉樹的深度dep=%dn,dep);break;case 0:exit(0);menu();printf(本代碼實(shí)現(xiàn)二叉樹的幾個(gè)基本功能，請選擇對應(yīng)的功能選項(xiàng)進(jìn)行相應(yīng)操作：);