中國礦業(yè)大學(xué)計算機學(xué)院實驗報告

中國礦業(yè)大學(xué)計算機學(xué)院實驗報告課程名稱__數(shù)據(jù)結(jié)構(gòu)(C語言版)_實驗名稱___樹結(jié)構(gòu)算法設(shè)計__班級：數(shù)學(xué)與應(yīng)用數(shù)學(xué)10-4班姓名：李國鵬學(xué)號：10104497儀器組號_______實驗日期_201實驗報告要求：1.實驗?zāi)康?.實驗內(nèi)容3.實驗步驟4.運行結(jié)果5.流程圖6.實驗體會一．實驗?zāi)康?理解樹結(jié)構(gòu)的邏輯特性；2熟練掌握二叉樹的邏輯結(jié)構(gòu)特性及各種存儲方法；3熟練掌握二插樹的各種基本操作，尤其是三種遍歷算法以及線索化算法。4進一步了解和掌握類的私有和公有成員函數(shù)的定義和使用以及類型的作用域。二．實驗內(nèi)容1試寫出中序遍歷二叉樹的遞歸和非遞歸程序并調(diào)試。2給定一棵用鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹結(jié)點數(shù)目。三.實驗步驟（1）#include<iostream.h>#include<conio.h>#include<stdlib.h>typedefstructBiTNode{ chardata; BiTNode*lchild,*rchild; //左右孩子指針}BiTNode,*BiTree;voidCreateBiTree(BiTree&T){ //按先序次序輸入二叉樹中結(jié)點的值（一個字符），*字符表示空樹 //構(gòu)造二叉鏈表表示的二叉樹T charch; cout<<"請輸入數(shù)據(jù)(*字符表示空樹)："<<"\t"; cin>>ch; if(ch=='*') T=NULL; else {T=(BiTNode*)malloc(sizeof(BiTNode)); T->data=ch; //生成根結(jié)點 CreateBiTree(T->lchild); //構(gòu)造左子樹 CreateBiTree(T->rchild); //構(gòu)造右子樹 }}//CreateBiTreevoidInOrderTraverse(BiTree&T){ //中序輸出樹中的數(shù)據(jù) if(T!=NULL){ InOrderTraverse(T->lchild); cout<<T->data<<""; InOrderTraverse(T->rchild);}}//InOrderTraversevoidmain(){ BiTreeRoot; CreateBiTree(Root); InOrderTraverse(Root); cout<<endl;getch();}（2）#include<iostream.h>#include<conio.h>#include<stdlib.h>typedefstructBiTNode{ chardata; BiTNode*lchild,*rchild; //左右孩子指針}BiTNode,*BiTree;intn=0;voidCreateBiTree(BiTree&T){ //按先序次序輸入二叉樹中結(jié)點的值（一個字符），0字符表示空樹 //構(gòu)造二叉鏈表表示的二叉樹T charch; cout<<"請輸入數(shù)據(jù)："<<"\t"; cin>>ch; if(ch=='0') T=NULL; else {T=(BiTNode*)malloc(sizeof(BiTNode)); T->data=ch; //生成根結(jié)點 CreateBiTree(T->lchild); //構(gòu)造左子樹 CreateBiTree(T->rchild); //構(gòu)造右子樹}}//CreateBiTreevoidsum(BiTree&T){ //求出二叉樹的結(jié)點的數(shù)目 if(T){n++; sum(T->lchild); sum(T->rchild);}}//sumvoidmain(){ cout<<"'0'作為空樹"<<endl; cout<<"請輸入此二叉樹。"<<endl; BiTreeroot; root=(BiTNode*)malloc(sizeof(BiTNode)); CreateBiTree(root); sum(root); cout<<endl; cout<<"此二叉樹的結(jié)點數(shù)為"<<n<<"個"<<endl;getch();}四．運行結(jié)果五.實驗體會實驗前首先要了解并理解樹結(jié)構(gòu)的邏輯特性，重點是二叉樹的結(jié)構(gòu)特征。要求熟練掌握二叉樹的各種插入、刪