實驗三二叉樹的操作及應(yīng)用

1、實驗三 二叉樹的操作及應(yīng)用實驗課程名： 數(shù)據(jù)結(jié)構(gòu)與算法成績:專業(yè)班級： 15計科1班 學號： 201540410109 姓名： 劉江 實驗時間： 2016.10.24-10.31 實驗地點： K4-102 指導教師： 馮珊 一、實驗?zāi)康募耙?、進一步掌握指針變量、動態(tài)變量的含義。2、掌握二叉樹的結(jié)構(gòu)特性，以及各種存儲結(jié)構(gòu)的特點和適用范圍。3、掌握用指針類型描述、訪問和處理二叉樹的運算。二、實驗內(nèi)容任務(wù)一：完成下列程序，該程序以二叉鏈表作存儲結(jié)構(gòu)，構(gòu)建如圖1所示的二叉樹，并依次進行二叉樹的前序、中序、后序及層次遍歷。圖1解答：（1）源代碼：#include<stdio.h>#inc

2、lude<stdlib.h>#define OK 1#define ERROR 0typedef char DataType;/* 二叉樹節(jié)點的存儲類型 */typedef struct Node/define stricture BiTree DataType data; struct Node *lchild,*rchild;Node, *BiTree;/*按先序序列建立一棵二叉樹*/BiTree CreatBiTree(BiTree &T)DataType ch;scanf("%c",&ch);if(ch=' ') T=NU

3、LL;elseif(!(T=(Node*)malloc(sizeof(Node)printf("Overflow.n");exit(0);T->data =ch;CreatBiTree(T->lchild );CreatBiTree(T->rchild );return T;void PrintData(DataType x)printf("%c",x);void PreOrder(BiTree T, void (*Visit)( DataType item)/*前序遍歷二叉樹T，訪問操作為Visit()函數(shù)*/if(T!= NULL)

4、Visit(T->data);PreOrder(T->lchild, Visit);PreOrder(T->rchild, Visit);void InOrder(BiTree T, void (*Visit)( DataType item) /*中序t */if(T!= NULL)InOrder(T->lchild, Visit);Visit(T->data);InOrder(T->rchild, Visit); void PostOrder(BiTree T, void (*Visit)( DataType item) /*后序 */if(T!= NUL

5、L)PostOrder(T->lchild, Visit);PostOrder(T->rchild, Visit);Visit(T->data);int main()int choice;BiTree root;printf("下面建立一棵二叉樹，結(jié)點數(shù)據(jù)輸入按先序次序。n");printf("輸入數(shù)據(jù)請注意，每一個非空結(jié)點的所有孩子數(shù)據(jù)都要給出n");printf("若孩子為空，請用空格符表示。n");printf("請輸入二叉樹結(jié)點的數(shù)據(jù)，這里設(shè)定為字符:n");CreatBiTree(roo

6、t);printf("=n");printf("1：先序序列：n");printf("2：中序序列：n");printf("3：后序序列：n");printf("其它值則退出：n");printf("=n");doprintf("請輸入對應(yīng)的操作碼：");scanf("%d",&choice);switch(choice)case 1:printf("n先序序列為："); PreOrder(root,Prin

7、tData);printf("n");break;case 2:printf("n中序序列為："); InOrder(root,PrintData);printf("n");break;case 3:printf("n后序序列為："); PostOrder(root,PrintData);printf("n");while(choice>0&&choice<4); return 0;（2） 運行結(jié)果： （3）運行結(jié)果分析： 運用遍歷方法實現(xiàn)二叉樹的建立任務(wù)二：完成下列

8、程序，該程序以二叉鏈表作存儲結(jié)構(gòu)，構(gòu)建如圖2所示二叉樹，計算二叉樹深度、所有結(jié)點總數(shù)、葉子結(jié)點數(shù)、雙孩子結(jié)點個數(shù)、單孩子結(jié)點個數(shù)。圖2解答：（1）源代碼：#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0typedef char TElemType;/* 二叉樹節(jié)點的存儲類型 */typedef struct BiTNode/define stricture BiTree TElemType data; struct BiTNode *lchild,*rchild;BiTNode, *BiTree

9、;/*按先序序列建立一棵二叉樹*/void CreatBiTree(BiTree &T)TElemType ch;scanf("%c",&ch);if(ch=' ') T=NULL;return;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)printf("Overflow.n");exit(0);(T)->data =ch;CreatBiTree(T->lchild );CreatBiTree(T->rchild );void PrintData(TElemTyp

10、e x)printf("%c",x);void PreOrder(BiTree T, void (*Visit)( TElemType item)/*前序遍歷二叉樹T，訪問操作為Visit()函數(shù)*/if(T!= NULL)Visit(T->data);PreOrder(T->lchild, Visit);PreOrder(T->rchild, Visit);void InOrder(BiTree T, void (*Visit)( TElemType item) /*中序t */if(T!= NULL)InOrder(T->lchild, Visi

11、t);Visit(T->data);InOrder(T->rchild, Visit); void PostOrder(BiTree T, void (*Visit)( TElemType item) /*后序 */if(T!= NULL)PostOrder(T->lchild, Visit);PostOrder(T->rchild, Visit);Visit(T->data);/以上代碼與任務(wù)一的完全相同，下面是完成任務(wù)二的代碼/注意這些函數(shù)算法的相似性int BTreeDepth(BiTree BT) int leftdep,rightdep; if (BT=

12、NULL) return(0); else leftdep=BTreeDepth(BT->lchild); rightdep=BTreeDepth(BT->rchild); if (leftdep>rightdep) return(leftdep+1); else return(rightdep+1); int NodeCount(BiTree BT) if (BT=NULL) return(0); else return(NodeCount (BT-> lchild)+ NodeCount (BT-> rchild)+1); int LeafCount(BiTr

13、ee BT) if (BT=NULL) return(0); else if (BT-> lchild =NULL && BT-> rchild =NULL) return(1); else return(LeafCount (BT-> lchild)+ LeafCount (BT-> rchild); int NotLeafCount(BiTree BT) if (BT=NULL) return(0); else if (BT-> lchild =NULL && BT-> rchild =NULL) return(0); e

14、lse return(NotLeafCount (BT-> lchild)+ NotLeafCount (BT-> rchild)+1); int OneChildCount(BiTree BT) if (BT=NULL) return(0); else if (BT-> lchild =NULL && BT-> rchild!=NULL) |(BT-> lchild!=NULL && BT-> rchild =NULL) return(OneChildCount (BT-> lchild)+ OneChildCount

15、 (BT-> rchild)+1); else return(OneChildCount (BT-> lchild)+ OneChildCount (BT-> rchild); int TwoChildCount(BiTree BT) if (BT=NULL) return(0); else if (BT-> lchild =NULL | BT-> rchild =NULL) return(TwoChildCount (BT-> lchild)+ TwoChildCount (BT-> rchild); else if (BT-> lchild!

16、=NULL && BT-> rchild!=NULL) return(TwoChildCount (BT-> lchild)+ TwoChildCount (BT-> rchild)+1);/主函數(shù)在任務(wù)一的基礎(chǔ)上進行適當?shù)脑鎏韎nt main()int choice;BiTree root;printf("下面建立一棵二叉樹，結(jié)點數(shù)據(jù)輸入按先序次序。n");printf("輸入數(shù)據(jù)請注意，每一個非空結(jié)點的所有孩子數(shù)據(jù)都要給出n");printf("若孩子為空，請用空格符表示。n");printf(&

17、quot;請輸入二叉樹結(jié)點的數(shù)據(jù)，這里設(shè)定為字符:n");CreatBiTree(root);printf("=n");printf("1：先序序列：n");printf("2：中序序列：n");printf("3：后序序列：n");printf("4：二叉樹的深（高）度：n");printf("5：二叉樹的結(jié)點數(shù)：n");printf("6：二叉樹的葉子結(jié)點數(shù)：n");printf("7：二叉樹的度為2的結(jié)點數(shù)：n");pr

18、intf("8：二叉樹的度為1的結(jié)點數(shù)：n");printf("其它值則退出：n");printf("=n");doprintf("請輸入對應(yīng)的操作碼：");scanf("%d",&choice);switch(choice)case 1:printf("n先序序列為："); PreOrder(root,PrintData);printf("n");break;case 2:printf("n中序序列為："); InOrder(root,PrintData);