數(shù)據(jù)結構實驗7：二叉樹子系統(tǒng)

1、驗證性實驗7：二叉樹子系統(tǒng)班級學號 BX100420 姓名 施程程 成績 1實驗目的（1）掌握二叉樹的特點及其存儲的方式。（2）掌握二叉樹的創(chuàng)建和顯示方法。（3）復習二叉樹遍歷的概念，掌握二叉樹遍歷的基本方法（4）掌握求二叉樹的葉結點數(shù)、總結點數(shù)和深度等基本算法。2實驗內容（1）按屏幕提示用前序方法建立一棵二叉樹，并能按凹入法顯示二叉樹結構。（2）編寫前序遍歷、中序遍歷、后序遍歷、層次遍歷程序。（3）編寫求二叉樹的葉結點數(shù)、總結點數(shù)和深度的程序。（4）設計一個選擇式菜單，以菜單方式選擇下列操作。 二 叉 樹 子 系 統(tǒng)*");* 1-建 二 叉 樹 *");* 2-凹 入

2、顯 示 *");* 3-先 序 遍 歷 *");* 4-中 序 遍 歷 *");* 5-后 序 遍 歷 *");* 6-層 次 遍 歷 *");* 7-求 葉 子 數(shù) *");* 8-求 結 點 數(shù) *");* 9-求 樹 深 度 *");* 0-返 回 *");*");請選擇菜單號（0-9）：3實驗步驟：（1）輸入并調試程序；（2）按下圖建立二叉樹；abcdef 二 叉 樹 子 系 統(tǒng) * * 1-建 二 叉 樹 * * 2-凹 入 顯 示 * * 3-先 序 遍 歷 * * 4-中 序 遍

3、歷 * * 5-后 序 遍 歷 * * 6-層 次 遍 歷 * * 7-求 葉 子 數(shù) * * 8-求 結 點 數(shù) * * 9-求 樹 深 度 * * 0-返 回 * * 請選擇菜單號：1<CR>請輸入按先序建立二叉樹的結點序列：說明：'0'代表后繼結點為空，請逐個輸入，按回車鍵輸入下一結點。請輸入根結點：a<CR>請輸入a結點的左子結點：b<CR>請輸入b結點的左子結點：d<CR>請輸入d結點的左子結點：0<CR>請輸入d結點的右子結點：0<CR>請輸入b結點的右子結點：0<CR>請輸入a結點

4、的右子結點：c<CR>請輸入c結點的左子結點：e<CR>請輸入e結點的左子結點：0<CR>請輸入e結點的右子結點：0<CR>請輸入c結點的右子結點：f<CR>請輸入f結點的左子結點：0<CR>請輸入f結點的右子結點：0<CR>（3）檢查凹入法顯示的二叉樹是否正確； 二 叉 樹 子 系 統(tǒng) * * 1-建 二 叉 樹 * * 2-凹 入 顯 示 * * 3-先 序 遍 歷 * * 4-中 序 遍 歷 * * 5-后 序 遍 歷 * * 6-層 次 遍 歷 * * 7-求 葉 子 數(shù) * * 8-求 結 點 數(shù) *

5、 * 9-求 樹 深 度 * * 0-返 回 * * 請選擇菜單號：2<CR>凹入表示法： a b d c e f 按回車鍵返回主菜單! <CR>（4）檢查其他算法的正確性舉例： 二 叉 樹 子 系 統(tǒng) * * 1-建 二 叉 樹 * * 2-凹 入 顯 示 * * 3-先 序 遍 歷 * * 4-中 序 遍 歷 * * 5-后 序 遍 歷 * * 6-層 次 遍 歷 * * 7-求 葉 子 數(shù) * * 8-求 結 點 數(shù) * * 9-求 樹 深 度 * * 0-返 回 * * 請選擇菜單號：3<CR>該二叉樹的先序遍歷序列為：a b d c e f4實驗程

6、序 #include<stdio.h>#define TREEMAX 100typedef struct BTchar data;BT *lchild;BT *rchild;BT;BT *CreateTree();void ShowTree(BT *T);void Preorder(BT *T);void Postorder(BT *T);void Levelorder(BT *T);void Inorder(BT *T);void Leafnum(BT *T);void Nodenum(BT *T);int TreeDepth(BT *T);int count=0;void ma

7、in()BT *T=NULL;char ch1,ch2,a;ch1='y'while(ch1='y'|ch1='y')printf("n");printf("ntt 二叉樹子系統(tǒng)");printf("ntt*");printf("ntt* 1-建 二 叉 樹 *");printf("ntt* 2-凹 入 顯 示 *");printf("ntt* 3-先 序 遍 歷 *");printf("ntt* 4-中 序 遍 歷

8、*");printf("ntt* 5-后 序 遍 歷 *");printf("ntt* 6-層 次 遍 歷 *");printf("ntt* 7-求 葉 子 數(shù) *");printf("ntt* 8-求 結 點 數(shù) *");printf("ntt* 9-求 樹 深 度 *");printf("ntt* 0-返 回 *");printf("ntt*");printf("ntt 請選擇菜單號（0-9）：");scanf("

9、;%c",&ch2);getchar();printf("n");switch(ch2)case '1':printf("ntt請按先序序列輸入二叉樹的結點：n");printf("ntt說明：輸入結點('0'代表后繼結點為空)后按回車.n");printf("ntt請輸入根結點：");T=CreateTree();printf("ntt二叉樹成功建立！n");break;case '2':ShowTree(T);break;ca

10、se '3':printf("ntt該二叉樹的先序遍歷序列為：");Preorder(T);break;case '4':printf("ntt該二叉樹的中序遍歷序列為：");Inorder(T);break;case '5':printf("ntt該二叉樹的后序遍歷序列為：");Postorder(T);break;case '6':printf("ntt該二叉樹的層次遍歷序列為：");Levelorder(T);break;case '7&

11、#39;:count=0;Leafnum(T);printf("ntt該二叉樹有%d個葉子。n",count);break;case '8':count=0;Nodenum(T);printf("ntt該二叉樹總共有%d個結點。n",count);break;case '9':printf("ntt該樹的深度是：%d",TreeDepth(T);break;case '0':ch1='n'break;default:printf("ntt*請注意：輸入有誤！*&

12、quot;);if(ch2!='0')printf("nntt按【Enter】鍵繼續(xù)，按任意鍵返回主菜單！n");a=getchar();if(a!='xA')getchar();ch1='n'BT *CreateTree()BT *t;char x;scanf("%c",&x);getchar();if(x='0')t=NULL;elset=new BT;t->data=x;printf("ntt請輸入%c結點的左子結點：",t->data);t-&

13、gt;lchild=CreateTree();printf("ntt請輸入%c結點的右子結點：",t->data);t->rchild=CreateTree();return t;void Preorder(BT *T)if(T)printf("%3c",T->data);Preorder(T->lchild);Preorder(T->rchild);void Inorder(BT *T)if(T)Inorder(T->lchild);printf("%3c",T->data);Inorder

14、(T->rchild);void Postorder(BT *T)if(T)Postorder(T->lchild);Postorder(T->rchild);printf("%3c",T->data);void Levelorder(BT *T)int i,j;BT *q100,*p;p=T;if(p!=NULL)i=1;qi=p;j=2;while(i!=j)p=qi;printf("%3c",p->data);if(p->lchild!=NULL)qj=p->lchild;j+;if(p->rchil

15、d!=NULL)qj=p->rchild;j+;i+;void Leafnum(BT *T)if(T)if(T->lchild=NULL&&T->rchild=NULL)count+;Leafnum(T->lchild);Leafnum(T->rchild);void Nodenum(BT *T)if(T)count+;Nodenum(T->lchild);Nodenum(T->rchild);int TreeDepth(BT *T)int ldep,rdep;if(T=NULL)return 0;elseldep=TreeDepth(

16、T->lchild);rdep=TreeDepth(T->rchild);if(ldep>rdep)return ldep+1;elsereturn rdep+1;void ShowTree(BT *T)BT *stackTREEMAX,*p;int levelTREEMAX2,top,n,i,width=4;if(T!=NULL)printf("ntt凹入表示法：ntt");top=1;stacktop=T;leveltop0=width;while(top>0)p=stacktop;n=leveltop0;for(i=1;i<=n;i+)p

17、rintf(" ");printf("%c",p->data);for(i=n+1;i<30;i+=2)printf("");printf("ntt");top-;if(p->rchild!=NULL)top+;stacktop=p->rchild;leveltop0=n+width;leveltop1=2;if(p->lchild!=NULL)top+;stacktop=p->lchild;leveltop0=n+width;leveltop1=1;5程序運行 6實驗小結本章要求我們掌握的是二叉樹