實驗三二叉樹的操作及應用

1、實驗三 二叉樹的操作及應用實驗課程名： 數(shù)據結構與算法成績:專業(yè)班級： 15計科1班 學號： 201540410109 姓名： 劉江 實驗時間： 2016.10.24-10.31 實驗地點： K4-102 指導教師： 馮珊 一、實驗目的及要求1、進一步掌握指針變量、動態(tài)變量的含義。2、掌握二叉樹的結構特性，以及各種存儲結構的特點和適用范圍。3、掌握用指針類型描述、訪問和處理二叉樹的運算。二、實驗內容任務一：完成下列程序，該程序以二叉鏈表作存儲結構，構建如圖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("下面建立一棵二叉樹，結點數(shù)據輸入按先序次序。n");printf("輸入數(shù)據請注意，每一個非空結點的所有孩子數(shù)據都要給出n");printf("若孩子為空，請用空格符表示。n");printf("請輸入二叉樹結點的數(shù)據，這里設定為字符:n");CreatBiTree(roo

6、t);printf("=n");printf("1：先序序列：n");printf("2：中序序列：n");printf("3：后序序列：n");printf("其它值則退出：n");printf("=n");doprintf("請輸入對應的操作碼：");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） 運行結果： （3）運行結果分析： 運用遍歷方法實現(xiàn)二叉樹的建立任務二：完成下列

8、程序，該程序以二叉鏈表作存儲結構，構建如圖2所示二叉樹，計算二叉樹深度、所有結點總數(shù)、葉子結點數(shù)、雙孩子結點個數(shù)、單孩子結點個數(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);/以上代碼與任務一的完全相同，下面是完成任務二的代碼/注意這些函數(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ù)在任務一的基礎上進行適當?shù)脑鎏韎nt main()int choice;BiTree root;printf("下面建立一棵二叉樹，結點數(shù)據輸入按先序次序。n");printf("輸入數(shù)據請注意，每一個非空結點的所有孩子數(shù)據都要給出n");printf("若孩子為空，請用空格符表示。n");printf(&

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

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