廈門理工 c語言數(shù)據(jù)結構 實驗6

1、數(shù)據(jù)結構實驗報告實驗序號：6 實驗項目名稱：樹和二叉樹的操作學號姓名專業(yè)、班實驗地點指導教師實驗時間一、實驗目的及要求1、進一步掌握指針變量、動態(tài)變量的含義。2、掌握二叉樹的結構特征，以及各種存儲結構的特點及適用范圍。3、掌握用指針類型描述、訪問和處理二叉樹的運算。4、掌握用二叉樹前序、中序、后序、層次遍歷的方法。二、實驗設備（環(huán)境）及要求微型計算機；windows 操作系統(tǒng)；Microsoft Visual Studio 6.0集成開發(fā)環(huán)境。三、實驗內(nèi)容與步驟1根據(jù)P129的方法，將a*b-(c+d*e/f)+g)轉化為表達式二叉樹（繪圖），并寫出表達式二叉樹的前序、中序和后序遍歷順序。2.

2、 鏈式表表示和實現(xiàn)二叉樹如下：#include <stdio.h>#include <stdlib.h>#define max 50typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root,*p,*qmax;int sum=0;int m=sizeof(test); void insert_data(int x) /*生成二叉排序樹*/ liuyu *p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->r

3、child=NULL;if(!root)root=s; p=root; while(p) /*如何接入二叉排序樹的適當位置*/q=p;if(p->data=x)printf("data already exist! n");return;else if(x<p->data)p=p->lchild; else p=p->rchild;if(x<q->data)q->lchild=s;else q->rchild=s;void main() /*先生成二叉排序樹*/int i,x;i=1; root=NULL; /*千萬別忘

4、了賦初值給root!*/doprintf("please input data%d:",i);i+;scanf("%d",&x); /*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結束*/if(x=-9999) printf("nNow output data value:n"); else insert_data(x); /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/ while(x!=-9999); 改寫以上程序，實現(xiàn)功能如下(任選兩題)：1.編寫函數(shù)實現(xiàn)前序、中序和后序遍歷。運行結果截圖：2.編寫函數(shù)實現(xiàn)計算葉節(jié)點個數(shù)。運行結果截圖：四、分析與

5、討論對上機實踐結果進行分析，上機的心得體會。五、教師評語簽名：日期：成績附源程序清單：1. #include <stdlib.h>#include <stdio.h>typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;DLR( Bitree root ) if (root !=NULL) /非空二叉樹 printf("%d",root->data); /訪問D DLR(root->

6、lchild); /遞歸遍歷左子樹 DLR(root->rchild); /遞歸遍歷右子樹 return(0); LDR(Bitree root) if(root !=NULL) LDR(root->lchild); printf("%d",root->data); LDR(root->rchild); return(0);LRD (Bitree root) if(root !=NULL) LRD(root->lchild); LRD(root->rchild); printf("%d",root->data);

7、 return(0);Bitree root;/定義根結點 void insert_data(int x) /*生成/樹*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /創(chuàng)建結點s->data=x; /結點賦值s->lchild=NULL;s->rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序樹的適當位置*/q=p;if(p->data=x) /相同結點不能重復插入printf("data already exist! n");r

8、eturn;else if(x<p->data)p=p->lchild; else p=p->rchild;if(x<q->data)q->lchild=s;else q->rchild=s;void main() /*先生成二叉排序樹*/int i=1,x; /i記錄結點個數(shù)，x存放結點值root=NULL; /*千萬別忘了賦初值給root!*/printf("請輸入數(shù)據(jù),-9999表示輸入結束n");doprintf("please input data %d:",i);i+;scanf("%

9、d",&x); /*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結束*/if(x=-9999) printf("nNow output data value:n"); else insert_data(x); /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=-9999); printf("nDLR"); DLR(root); printf("nLDR"); LDR(root); printf("nLRD"); LRD(root);2.#include <stdlib.h>#include &l

10、t;stdio.h>typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;Bitree root;/定義根結點 int CountLeaf (Bitree root) /返回指針T所指二叉樹中所有葉子結點個數(shù)int m,n; if (!root ) return 0; if (!root->lchild && !root->rchild) return 1; else m = CountLeaf( roo

11、t->lchild); n = CountLeaf( root->rchild); return (m+n); /else / CountLeafvoid insert_data(int x) /*生成/樹*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /創(chuàng)建結點s->data=x; /結點賦值s->lchild=NULL;s->rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序樹的適當位置*/q=p;if(p->data=x) /相同結點

12、不能重復插入printf("data already exist! n");return;else if(x<p->data)p=p->lchild; else p=p->rchild;if(x<q->data)q->lchild=s;else q->rchild=s;void main() /*先生成二叉排序樹*/int i=1,x; /i記錄結點個數(shù)，x存放結點值int sum;root=NULL; /*千萬別忘了賦初值給root!*/printf("請輸入數(shù)據(jù),-9999表示輸入結束n");doprintf("please input data %d:",i);i+;scanf("%d",&x); /*從鍵盤采集數(shù)據(jù)，以-9999表示