C語言編程二叉樹

1、陜西科技大學(xué)實驗報告班級： 數(shù)學(xué)101軟件 學(xué)號：201012010225姓名： 田貴文 實驗組別: _ 實驗日期：報告日期： 成績：報告內(nèi)容:（目的和要求、原理、步驟、數(shù)據(jù)、計算、小結(jié)等）實驗名稱：C語言編程二叉樹一、實驗?zāi)康募耙笳莆斩鏄涞拇鎯崿F(xiàn)掌握二叉樹的遍歷思想掌握二叉樹的常見算法的程序?qū)崿F(xiàn)二、實驗內(nèi)容編寫函數(shù),輸入字符序列,建立二叉樹的二叉鏈表。編寫函數(shù),實現(xiàn)二叉樹的中序遞歸遍歷算法。（最好也能實現(xiàn)前綴和后 綴遍歷算法）編寫函數(shù),實現(xiàn)二叉樹的中序非遞歸遍歷算法。編寫函數(shù),借助隊列實現(xiàn)二叉樹的層次遍歷算法。編寫函數(shù),求二叉樹的高度。編寫函數(shù),求二叉樹的結(jié)點個數(shù)。編寫函數(shù),求二叉樹的

2、葉子個數(shù)。編寫函數(shù),交換二叉樹每個結(jié)點的左子樹和右子樹。編寫一個主函數(shù),在主函數(shù)中設(shè)計一個簡單的菜單,分別調(diào)試上述算 法。三、實驗結(jié)果二叉樹的葉子結(jié)處平數(shù)交按二賈樹的所有左右子樹 0 道出親統(tǒng)詰選擇：2遞歸-中序遍歷二爻樹:CBEDAFG遞歸-創(chuàng)逮二爻鏈表遞歸-中存遍圧二賈樋遞歸-前序遍歷二叉樹遞歸-后游遍歷二夏樋詐遞歸沖序遍歷二叉樹層次-遍歷二夏樹f乂惻tu同區(qū)二夏槌的貉點個數(shù)二夏樹的葉子結(jié)點于數(shù)交拴二賈樹的所有左右子樹0道出隸統(tǒng)詰選擇：3遞歸-前序遍歷二變樹:ABCDEFG.遞歸-創(chuàng)建二夏鏈表遞歸沖存遍圧二賈樋3 遞歸-前序遍歷二叉樹遞歸-后游遍歷二夏樋辱遞歸-中序遍歷二變樹 層次-遍歷二

3、夏稅 二叉樹的高度二夏樹的結(jié)點亍數(shù)9.二夏樹的葉子結(jié)點于數(shù)10 交勲二叉樹的所有左右子樹0 追出東或諳選擇：4遞歸-后序遍歷二夏樹:CEDBGFA1.遞歸-創(chuàng)遂二賈鏈表2 遞歸-中序遍歷二叉密遞歸-前序遍歷二賈樹遞歸-后游遍歷二變養(yǎng)非遞歸-中序遍歷二夏樹E 層次-遍歷二叉也 F.二夏樹的高度E二叉樹的結(jié)點亍數(shù)二夏樹的葉子結(jié)點于數(shù)10 交按二叉樹的所有左右子樹0追出親端詰選揮：5非遞歸-中序遍歷二叉樹CBEDAFG遞歸-創(chuàng)連.二夏捱表遞歸-中序遍歷二叉轆遞歸-前序遍歷二叉樹遞歸-后薦遍歷二叉翌務(wù)謹(jǐn)歸-中序遍歷二夏樹E趕次-遍歷二曼稅二叉樹的高度E二叉樹的結(jié)點亍數(shù)U j l-l U3-D J-.

4、I SV%y.二夏樹的葉子潔點個數(shù)交拱二夏槪的所有左右子樹 0 .追.出親.纟充諳選擇：6按層次遍圧二賈樹:ABFCDGE遞歸-創(chuàng)逮二叉鏈表遞歸沖存遍歷二叉?zhèn)溥f歸-俞序遍歷二夏樹4遞歸-后序遍歷二曼樹5 玉謹(jǐn)歸-中序遍歷二變樹E億次-遍歷二叉樋了.二賈樹的高度_1-J二賈樹的結(jié)點亍數(shù)_1-J二叟樹的葉子結(jié)點于數(shù)交拱二夏梃的所誨左右子樹 0 .追出親統(tǒng)詰選擇擰二愛樹的高度為:4.謹(jǐn)歸-創(chuàng)建二賈鏈爻遞歸-中序遍歷二愛樹遞歸-前芋遍歷二賈農(nóng)4.說掃-后序筒5二叉樹5.非遞歸沖序遍歷二賈樹E 層次-遍圧二叉樹7 二叟樹的高度二賈樹的結(jié)點于數(shù)二叉餌的葉子結(jié)點于數(shù)交玄g二賈樹的所有左右子樹諳選擇辿二叉樹的

5、箱點數(shù)肯口1 遞歸-創(chuàng)送二叉捱表遞歸沖序遍歷二夏機(jī)遞歸-前序遍歷二夏樹遞歸-后序遍歷二愛極玉謹(jǐn)歸-中序遍歷二.叉樹 .層次-遍歷二叉樹二愛樹的高度二叉祐的結(jié)點于數(shù)二曼樹的罰子潔慮個數(shù)10.交撿二賈梃的所有左右子樹0 .追出親統(tǒng)諳選擇：9二叉樹中葉子結(jié)點數(shù)為:31 .遞歸-創(chuàng)遼二夏鏈表遞歸-中存遍歷二叉擁遞歸-前序遍歷二叉樹遞歸-后游遍歷二叉樹5.玉謹(jǐn)歸-中序遍歷二叉樹 層次-遍歷二夏樋 7.ry樹的高度8 二叉樹的結(jié)點亍數(shù)v - - I j n -u j i!i.二叉樹的葉子結(jié)找亍數(shù)10 .交拱二夏樹的所有左右子樹 0 .追出親統(tǒng)詰選擇：10交換二叉樹的所有左右子樹交換后二變樹按中序遍歷輸出:

6、GFADEBC 交換帝二叉樹嗾前障遍歷輸出:AFGBDL-C 交換后二叉樹按后序遍歷輸出:GFEDCBA遞歸-創(chuàng)建二叉鏈表謹(jǐn)歸-中序遍歷二夏樹3 遞歸-前序遍歷二愛樹4遞歸-后序遍歷二夏樹5.班遞歸-中序遍圧二賈樹 層次-遍歷二叉極 了.二叉樹的高度二叉軻的結(jié)點于數(shù)二叉樹的葉子誥點平數(shù)10 交瑕二夏樹的所有左右子樹0 .追出縈蛻諳選擇:0Press any key to continue四、實驗總結(jié)通過此實驗，我掌握了二叉樹的存儲實現(xiàn)，掌握了二叉樹的遍歷思想 掌握了二叉樹的常見算法的程序?qū)崿F(xiàn)。附錄#include #include #define MAXSIZE 100typedef char

7、 DataType;typedef struct BiTNode /* 二叉鏈表存儲結(jié)構(gòu) */ DataType data;struct BiTNode *lchild,*rchild;BiTree;typedef BiTree* ElemType ; /* 棧中數(shù)據(jù)元素類型，棧中保存結(jié)點指針 */typedef struct ElemType dataMAXSIZE;int top;SeqStack; /* 棧的類型定義，順序棧 */typedef structElemType queueMAXSIZE;int front,rear;SP;SeqStack *initSeqStack() /

8、* 初始化棧 */ SeqStack *s; /* 首先建立?？臻g，然后初始化棧頂指針 */ s=(SeqStack*)malloc(sizeof(SeqStack);s-top=-1;return s;int push(SeqStack *s,ElemType x) if(s-top=MAXSIZE-1) /* 棧滿不能入棧 */printf(” 棧滿”)；return 0;s-top+；s-datas-top=x；return 1；void pop(SeqStack *s) /* 出棧，假設(shè)棧不空 */s-top-； int empty(SeqStack *s) if(s-top=-1)

9、return 1；else return 0；ElemType top(SeqStack *s) /* 設(shè)棧不空 */ return (s-datas-top)；/* 遞歸算法創(chuàng)建二叉鏈表 */BiTree *createBiTree() DataType ch；BiTree *T；ch=getchar()；if(ch=0) return NULL；else T=(BiTree *)malloc(sizeof(BiTree)；T-data=ch；T-lchild=createBiTree()；T-rchild=createBiTree()；return T； /* 中序遍歷二叉樹的遞歸算法 *

10、/void InOrder(BiTree *T) if(T) InOrder(T-lchild)；printf(%c,T-data)；InOrder(T-rchild)；/* 前序遍歷二叉樹的遞歸算法 */void PreOrder(BiTree *T) if(T) printf(%c,T-data); PreOrder(T-lchild); PreOrder(T-rchild);/* 后序遍歷二叉樹的遞歸算法 */void PostOrder (BiTree *T) if(T) PostOrder(T-lchild); PostOrder(T-rchild); printf(%c,T-dat

11、a);/* 中序遍歷二叉樹的非遞歸算法 */void InOrderFei(BiTree *p) SeqStack *s; s=initSeqStack();while(1) while(p) push(s,p); p=p-lchild; /* 先將結(jié)點指針壓棧，待出棧時再訪問 */ if(empty(s) break;p=top(s); pop(s); printf(%c,p-data); p=p-rchild;/* 按層次遍歷 */void LevelOrder(BiTree *T) SP *p; p=(SP*)malloc(sizeof(SP); p-front=0; p-rear=0;

12、if(T!=NULL) p-queuep-front=T; p-front=p-front+1; while(p-front!=p-rear) T=p-queuep-rear; p-rear=p-rear+1; printf(%c,T-data);if(T-lchild!=NULL)p-queuep-front=T-lchild;/咗 孩子進(jìn)隊列 */ p-front=p-front+1;if(T-rchild!=NULL) p-queuep-front=T-rchild;/*右孩子進(jìn)隊列 */ p-front=p-front+1; /* 求二叉樹的高度 */int height(BiTree

13、 *T) int i,j;if(!T) return 0; i=height(T-lchild);/* 求左子樹的高度 */ j=height(T-rchild);/* 求右子樹的高度 */return ij?i+1:j+1;/* 二叉樹的高度為左右子樹中較高的高度加1 */* 求二叉樹的所有結(jié)點個數(shù) */int Nodes(BiTree *T) int n1,n2;if(T=NULL) return 0;else if(T-lchild=NULL&T-rchild=NULL) return 1; else n1=Nodes(T-lchild);n2=Nodes(T-rchild); retu

14、rn n1+n2+1; /* 求二叉樹的葉子結(jié)點個數(shù) */int leafs(BiTree *T) int num1,num2;if(T=NULL) return 0; elseif(T-lchild=NULL&T-rchild=NULL) return 1;num1=leafs(T-lchild); /* 求左子樹中葉子結(jié)點數(shù) */ num2=leafs(T-rchild); /* 求右子樹中葉子結(jié)點數(shù) */ return num1+num2; /* 交換二叉樹的所有左右子樹 */void exchange(BiTree *T) BiTree *temp=NULL; if(T-lchild=

15、NULL&T-rchild=NULL) return; elsetemp=T-lchild;T-lchild=T-rchild; T-rchild=temp; if(T-lchild) exchange(T-lchild); if(T-rchild) exchange(T-rchild);/* 交換后二叉樹的遍歷 */void Display(BiTree *T)printf(t 交換后二叉樹按中序遍歷輸出:);InOrder(T);printf(n); printf(t 交換后二叉樹按前序遍歷輸出:);PreOrder(T);printf(n); printf(t 交換后二叉樹按后序遍歷輸出

16、:);PostOrder(T);printf(n);void menu() printf(n);printf(tt1.遞歸-創(chuàng)建二叉鏈表n); printf(tt2.遞歸沖序遍歷二叉樹n);printf(tt3.遞歸-前序遍歷二叉樹n);printf(tt4.遞歸-后序遍歷二叉樹n);printf(tt5.非遞歸沖序遍歷二叉樹5); printf(tt6 .層次-遍歷二叉樹n);printf(tt7.二叉樹的高度n);printf(tt8.二叉樹的結(jié)點個數(shù)5);printf(tt9.二叉樹的葉子結(jié)點個數(shù)5); printf(ttlO.交換二叉樹的所有左右子樹n);printf(tt0 .退出系

17、統(tǒng)5);printf(nt 請選擇:”)；void main() BiTree *bt; bt=NULL;int n,m=l;while(m)menu(); scanf(%d,&n); getchar();switch(n)case 1:printf(nt請輸入結(jié)點的前序序列創(chuàng)建二叉樹:0表示空:)； bt=createBiTree(); break;/* 生成二叉樹 */case 2:printf(nt 遞歸-中序遍歷二叉樹:)；InOrder(bt);printf(n); break;case 3:printf(nt 遞歸-前序遍歷二叉樹:)；PreOrder(bt); printf(n); break;case 4:printf(nt 遞歸-后序遍歷二叉樹:)；PostOrder(bt);printf(n); break;case 5:printf(nt非遞歸-中序遍歷二叉樹”)；InOrderFei(bt);printf(n); break;case 6:printf(nt 按層次遍歷二叉樹:)；LevelOr