1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目: 創(chuàng)建一個(gè)二叉排序樹，并以先序、中序、后序遍歷輸出。實(shí)驗(yàn)?zāi)康模菏炀氄莆斩媾判驑浣⒌乃惴▽?shí)驗(yàn)內(nèi)容：已知n個(gè)元素，創(chuàng)建一個(gè)二叉排序樹，以先序、中序、后序遍歷輸出，并計(jì)算每個(gè)節(jié)點(diǎn)的平衡因子。一、需求分析1.本程序輸入應(yīng)為一組數(shù)，將這組數(shù)作為關(guān)鍵字創(chuàng)建一個(gè)二叉排序樹。2.本程序輸出應(yīng)為該建立好的二叉排序樹的先序、中序、后序遍歷輸出，以及每個(gè)節(jié)點(diǎn)的平衡因子。3. 程序執(zhí)行的命令包括：（1）創(chuàng)建二叉排序樹（2）先序非遞歸遍歷輸出（3）中序非遞歸遍歷輸出（4）后序非遞歸遍歷輸出（5）計(jì)算并輸出每個(gè)節(jié)點(diǎn)的平衡因子4.測試數(shù)據(jù)：輸入元素的個(gè)數(shù)為8，元素為53 25 76 20 48

2、 14 60 84輸出為：先序遍歷：53 25 20 14 48 76 60 84 中序遍歷：14 20 25 48 53 60 76 84后序遍歷：14 20 48 25 60 84 76 53平衡因子：節(jié)點(diǎn)53的平衡因子為1 節(jié)點(diǎn)25的平衡因子為1 節(jié)點(diǎn)20的平衡因子為1 節(jié)點(diǎn)14的平衡因子為0 節(jié)點(diǎn)48的平衡因子為0 節(jié)點(diǎn)76的平衡因子為0 節(jié)點(diǎn)60的平衡因子為0 節(jié)點(diǎn)84的平衡因子為0二 概要設(shè)計(jì)為了實(shí)現(xiàn)以上操作，應(yīng)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)。1. 基本操作：node *create()創(chuàng)建二叉排序樹void NRPreorder(node *bt)先序非遞歸遍歷輸出void NRinord

3、er(node *bt)中序非遞歸遍歷輸出void NRpostorder(node *bt)后序非遞歸遍歷輸出int height(node *bt)計(jì)算左右子樹深度void shendu(node *bt)計(jì)算平衡因子2. 本程序包含七個(gè)模塊（1） 主程序模塊（2） 二叉排序樹創(chuàng)建模塊計(jì)算左右子樹深度模塊（3） 先序遍歷模塊（4） 中序遍歷模塊（5） 后序遍歷模塊（6） 計(jì)算左右子樹深度模塊（7） 計(jì)算平衡因子模塊計(jì)算平衡因子模塊3. 模塊調(diào)用圖二叉排序樹創(chuàng)建模塊主程序模塊后序遍歷模塊中序遍歷模塊先序遍歷模塊三 詳細(xì)設(shè)計(jì)1 元素類型，結(jié)點(diǎn)類型和指針類型：#define maxsize 10

4、0typedef struct nodechar data; struct node *lc; struct node *rc; node;node *smaxsize;node *bt;node *q,*p;2.每個(gè)模塊的分析：（1）主程序模塊：int main()node *bt;bt=create();printf(該二叉樹的先序遞歸遍歷序列為: );preorder(bt);printf(n);printf(該二叉樹的中序遞歸遍歷序列為: );inorder(bt);printf(n);printf(該二叉樹的后序遞歸遍歷序列為: );postorder(bt);printf(n);p

5、rintf(該二叉樹的先序非遞歸遍歷序列為:);NRPreorder(bt);printf(n);printf(該二叉樹的中序非遞歸遍歷序列為:);NRinorder(bt);printf(n);printf(該二叉樹的后序非遞歸遍歷序列為:);NRpostorder(bt);printf(n);printf(以先序遍歷輸出該二叉樹，每個(gè)節(jié)點(diǎn)的平衡因子如下:n);shendu(bt);getchar();getchar();return 0;（2）二叉排序樹創(chuàng)建模塊：node *create()node *bt;node *q,*p;bt=NULL; /*根節(jié)點(diǎn)指針置空*/int x; int

6、 i;int m;int j;printf(請輸入數(shù)據(jù)個(gè)數(shù):n);scanf(%d,&m);printf(請輸入數(shù)據(jù):n);for(j=0;jdata=x; q-lc=q-rc=NULL;if(bt=NULL) /*如果根節(jié)點(diǎn)指針為空，將其指向新申請節(jié)點(diǎn)*/bt=q;else p=bt; /*活動(dòng)指針指向根節(jié)點(diǎn)*/while(i=0)if(p-datax) /*如果新輸入的數(shù)值比當(dāng)前節(jié)點(diǎn)的數(shù)值小*/if(p-lc!=NULL) /*如果當(dāng)前節(jié)點(diǎn)的左孩子不為空，將活動(dòng)指針移到它的左孩子*/p=p-lc;else /*否則將新申請節(jié)點(diǎn)鏈到當(dāng)前節(jié)點(diǎn)的左孩子，將i標(biāo)記為1，表示已處理*/p-lc=q;

7、i=1;else /*否則沿右鏈域比較*/if(p-rc!=NULL) p=p-rc;else /*直到終端，插入輸入節(jié)點(diǎn)*/p-rc=q;i=1;return bt;（3）先序遍歷模塊：void NRPreorder(node *bt) node *p; top=-1; top+; stop=bt; while(top!=-1) p=stop-; while(p) printf(%d ,p-data); top+; stop=p-rc; p=p-lc; （4）中序遍歷模塊void NRinorder(node *bt)node *p;int top;if(bt=NULL) return;to

8、p=0;p=bt;while(!(p=NULL&top=0)while(p!=NULL)stop=p;top+;p=p-lc;if(topdata);p=p-rc;（5）后序遍歷模塊：void NRpostorder(node *bt)node *p,*q;int top=-1;int flag;p=bt;if(p!=NULL)do while(p!=NULL)top+;stop=p;p=p-lc;q=NULL;flag=1;while(top!=-1&flag)p=stop;if(p-rc=q)printf(%d ,p-data);top-;q=p;elsep=p-rc;flag=0; wh

9、ile (top!=-1);（6）計(jì)算左右子樹深度模塊int height(node *bt)int hl,hr;if(bt=NULL) /*利用遞歸算法求左右子樹的深度*/return 0;elsehl=height(bt-lc);hr=height(bt-rc);if(hlhr)return (hl+1);elsereturn (hr+1);(7)計(jì)算平衡因子模塊void shendu(node *bt)int sl,sr;int ph;node *p; top=-1; top+; stop=bt; while(top!=-1) p=stop-; while(p) sl=height(p-

10、lc); /*當(dāng)前節(jié)點(diǎn)左子樹的深度*/sr=height(p-rc); /*當(dāng)前節(jié)點(diǎn)右子樹的深度*/ph=sl-sr; /*當(dāng)前節(jié)點(diǎn)的平衡因子*/ printf(節(jié)點(diǎn)為%d的平衡因子為%dn,p-data,ph); top+; stop=p-rc; p=p-lc; int height(node *bt)3.函數(shù)調(diào)用圖：void shendu(node *bt)node *create()int main()void NRpostorder(node *bt)void NRinorder(node *bt)void NRPreorder(node *bt)4. 完整的程序：(見源文件).四 使

11、用說明、測試分析及結(jié)果1程序使用說明（1）本程序的運(yùn)行環(huán)境為VC6.0。（2）進(jìn)入演示程序后即顯示提示信息：請輸入數(shù)據(jù)個(gè)數(shù)：請輸入數(shù)據(jù)：輸入完數(shù)據(jù)以三種形式輸出二叉排序樹，并輸出每個(gè)節(jié)點(diǎn)的平衡因子.2.測試數(shù)據(jù)：輸入元素的個(gè)數(shù)為8，元素為53 25 76 20 48 14 60 84輸出為：先序遍歷：53 25 20 14 48 76 60 84 中序遍歷：14 20 25 48 53 60 76 84后序遍歷：14 20 48 25 60 84 76 53平衡因子：節(jié)點(diǎn)53的平衡因子為1 節(jié)點(diǎn)25的平衡因子為1 節(jié)點(diǎn)20的平衡因子為1 節(jié)點(diǎn)14的平衡因子為0 節(jié)點(diǎn)48的平衡因子為0 節(jié)點(diǎn)76

12、的平衡因子為0 節(jié)點(diǎn)60的平衡因子為0 節(jié)點(diǎn)84的平衡因子為03.運(yùn)行界面：五、實(shí)驗(yàn)總結(jié)本次試驗(yàn)過程比較順利，由于上次的二叉樹積累了經(jīng)驗(yàn)，所以這次編得比較快，編程過程中沒有出現(xiàn)問題，通過這次編程對于二叉樹有了更進(jìn)一步的熟悉和了解，可以熟練編寫二叉排序樹，熟悉了二叉排序樹的結(jié)構(gòu)，并且對于計(jì)算節(jié)點(diǎn)的深度以及節(jié)點(diǎn)的平衡因子有了一定的掌握。教師評語：實(shí)驗(yàn)成績：#include#include#define maxsize 100/定義結(jié)構(gòu)體typedef struct nodechar data; struct node *lc; struct node *rc; node;/定義棧node *sma

13、xsize;int top=-1;/創(chuàng)建二叉排序樹node *create()node *bt;node *q,*p;bt=NULL; /*根節(jié)點(diǎn)指針置空*/int x; int i;int m;int j;printf(請輸入數(shù)據(jù)個(gè)數(shù):n);scanf(%d,&m);printf(請輸入數(shù)據(jù):n);for(j=0;jdata=x; q-lc=q-rc=NULL;if(bt=NULL) /*如果根節(jié)點(diǎn)指針為空，將其指向新申請節(jié)點(diǎn)*/bt=q;else p=bt; /*活動(dòng)指針指向根節(jié)點(diǎn)*/while(i=0)if(p-datax) /*如果新輸入的數(shù)值比當(dāng)前節(jié)點(diǎn)的數(shù)值小*/if(p-lc!=N

14、ULL) /*如果當(dāng)前節(jié)點(diǎn)的左孩子不為空，將活動(dòng)指針移到它的左孩子*/p=p-lc;else /*否則將新申請節(jié)點(diǎn)鏈到當(dāng)前節(jié)點(diǎn)的左孩子，將i標(biāo)記為1，表示已處理*/p-lc=q;i=1;else /*否則沿右鏈域比較*/if(p-rc!=NULL) p=p-rc;else /*直到終端，插入輸入節(jié)點(diǎn)*/p-rc=q;i=1;return bt;/先序遞歸遍歷void preorder(node *bt)if(bt!=NULL)printf(%d ,bt-data);preorder(bt-lc);preorder(bt-rc);/中序遞歸遍歷void inorder(node *bt)if(b

15、t!=NULL)inorder(bt-lc);printf(%d ,bt-data);inorder(bt-rc);/后序遞歸遍歷void postorder(node *bt)if(bt!=NULL)postorder(bt-lc);postorder(bt-rc);printf(%d ,bt-data);/先序非遞歸遍歷void NRPreorder(node *bt) node *p; top=-1; top+; stop=bt; while(top!=-1) p=stop-; while(p) printf(%d ,p-data); top+; stop=p-rc; p=p-lc; /

16、中序非遞歸遍歷void NRinorder(node *bt)node *p;int top;if(bt=NULL) return;top=0;p=bt;while(!(p=NULL&top=0)while(p!=NULL)stop=p;top+;p=p-lc;if(topdata);p=p-rc;/后序非遞歸遍歷void NRpostorder(node *bt)node *p,*q;int top=-1;int flag;p=bt;if(p!=NULL)do while(p!=NULL)top+;stop=p;p=p-lc;q=NULL;flag=1;while(top!=-1&flag)

17、p=stop;if(p-rc=q)printf(%d ,p-data);top-;q=p;elsep=p-rc;flag=0; while (top!=-1);/計(jì)算平衡因子int height(node *bt)int hl,hr;if(bt=NULL) /*利用遞歸算法求左右子樹的深度*/return 0;elsehl=height(bt-lc);hr=height(bt-rc);if(hlhr)return (hl+1);elsereturn (hr+1);void shendu(node *bt)int sl,sr;int ph;node *p; top=-1; top+; stop=bt; while(top!=-1) p=stop-; while(p) sl=height(p-lc); /*當(dāng)前節(jié)點(diǎn)左子樹的深度*/sr=height(p-rc); /*當(dāng)前節(jié)點(diǎn)右子樹的深度*/ph=sl-sr; /*當(dāng)前節(jié)點(diǎn)的平衡因子*/ printf(節(jié)點(diǎn)為%d的平衡因子為%dn,p-data,ph); top+; stop=p-rc; p=p-lc; int main()node *bt;bt=create();printf(該二叉樹的先序遞歸遍歷序列為: );preorder(bt);printf(n);printf(該二叉樹的中序遞歸遍歷序列為: );inorder(bt)