實驗報告

院(系)：信息科學與技術學院課程名稱：數據結構日期

班學號實驗室

級

專姓名計算機號

業

實實驗6樹的操作成績評定

驗

名

稱

所或教師簽名

用VCTC

軟

件

實(1)掌握二叉樹的二叉鏈表存儲結構；

驗(2)掌握二叉樹的先序，中序，后序的遍歷方法；

目(3)利用二叉樹的遞歸遍歷方法實現二叉樹的創建，查找等操作。

的

實復習書上有關內容。

驗閱讀實驗內容1，進行程序填空，并寫出可能的結果。

準編出實驗的源程序。

備本次實驗為4學時

一、建立二叉樹，并且用廣義表和凹入表表示出來，再前序輸出各個結點的值。

請進行程序填空，再上機調試。

提示：若要建立書上P63圖6.10(a)的二叉樹，輸入應為(小圓點表示空子樹)

ABD.G...CE..F..

#include<malloc.h>

#include<stdio.h>

typedefcharDataType;/*應由用戶定義DataType的實際類型*/

/*二叉樹的鏈式存儲表示*/

typedefstructNode

實(

驗DataTypedata;

內structNode*Lchild;

容structNode*Rchild;/*左右孩子指針*/

}BiTNode,*BiTree;/*結點類型*/

/*構造二叉樹*/

voidCreateBiTree(BiTree*bt)

(

charch;

ch=getchar();

if(ch=='「)*bt=NULL;

else/*讀入非空樹*/

(

*bt=(BiTree)malloc(sizeof(BiTNode));〃生成一個新結點

(*bt)->data=ch;

CreateBiTree(&((*bt)->Lchild));//生成左子樹

CreateBiTree(&((*bt)-〉Rchild));//生成右子樹

/*用廣義表表示二叉樹*/

voidListBiTree(BiTreeT)

(

if(T!=NULL)

(

printf("%c",T->data);

if(T->Lchild!=NULL||T->Rchild!=NULL)

{

printf("(");

ListBiTree(T->Lchild);

if(T->Rchild!=NULL)

printf(",");

'D:\Debug\Cppl.exe"

請輸入先序序列■結點用.表示)：

ListBiTree(T->Rchild);ABD.G...CE..F..

printf(")");A<B<D<,G>>,C<E,F>>

用凹入表表示二叉樹：

A

B

D

G

C

E

F

/*用凹入表表示二叉樹*/前序遍歷：

voidDisplayBiTree(BiTreeT)ABDGCEF

Pressanykeytocontinue.

(

BiTreestackfl00],p;

intlevel[100],top,n,i;

if(T!=NULL)

(

printf("用凹入表表示二叉樹

top=l;

stack[top]=T;

ievel[top]=3;

while(top>0)

|

p=stack[top];

n=level[top];

for(i=l;i<=n;i++)

printf("");

printf("%c\n",p->data);

top-;

if(p->Rchild!=NULL)

top++;

stackftop]=p->Rchild;

level[top]=n+3;

)

if(p->Lchild!=NULL)

(

top++;

stack[top]=p->Lchild;

level[top]=n+3;

/*前序遍歷二叉樹*/

voidPreorder(BiTreeT)

(

if(T!=NULL)

(

printf("%c”,T->data);/*訪問結點*/

Preorder(T->Lchild);

Preorder(T->Rchild);

voidmain()

{BiTreeT;

printf("請輸入先序序列(虛結點用.表示)：\n");

CreateBiTree(&T);

ListBiTree(T);

printf("\n");

DisplayBiTree(T);

printf("前序遍歷：\n");

Preorder(T);

printf("\n");

二、寫出中序、后序遍歷二叉樹的函數，并上機驗證。

三、編寫程序，實現下列功能：

1.查找指定結點

2.統計二叉樹中葉結點的個數

3.求二叉樹的高度。

四、下列程序是在二叉樹的進行查找和統計二叉樹中的葉結點個數，程序中有錯誤，請

閱讀后再上機調試運行。

#include"stdio.h"

includenstdlib.h"

typedefstructBiTNode{

chardata;

structBiTNode*lchild,*rchild;/*左右孩子指針*/

}BinTNode,*BinTree;

intCountLeaf2(BinTreebt)

{/*開始時，bt為根結點所在鏈結點的指針，返回值為bt的葉子數*/

intn;

if(bt==NULL)n=0;

elseif(bt->lchild==NULL&&bt->rchild==NULL)

n=l;

else

n=CountLeaf2(bt->lchild)4-CountLeaf2(bt->rchild);

returnn;

)

BinTreeSearch(BinTreebt,charx)

{/*在bt為根結點指針的二叉樹中查找數據元素X*/

if(bt->data==x)returnbt;/*查找成功返回*/

if(bt->lchild!=NULL)relurn(Search(bt->lchild,x));

/*在bt->lchild為根結點指針的二叉樹中查找數據元素X*/

if(bt->rchild!=NULL)retum(Search(bt->rchild,x));

/*在bt->rchild為根結點指針的二叉樹中查找數據元素x*/

returnNULL;/*查找失敗返回*/

}

BinTreeCreatBiTree()

{BinTreeT;

charch;

scanf(u\n%c",&ch);

if(ch==7)T=NULL;

else{

T=(BinTNode*)malloc(sizeof(BinTNode));

T->data=ch;/*生成根結點*/

T->lchild=CreatBiTree();/*構造左子樹*/

T->rchild=CreatBiTree。；/*構造右子樹*/

)

return(T);

)

voidInOrderOut(BinTreeT)

{/*中序遍歷輸出二叉樹T的結點值刃

if(T!=NULL)

{InOrderOut(T->lchild);/*中序遍歷二叉樹的左子樹*/

printf('f%3cn,T->data);/*訪問結點的數據*/

InOrderOut(T->rchild);/*中序遍歷二叉樹的右子樹*/

)

)

voidmain()

{

BinTreebt;

BinTNode*p;

printf("請輸入要建立的二叉樹)

bt=CreatBiTree();

printf("\n中序遍歷所建立的二叉樹為)

InOrderOut(bt);

printf(n\n要查找的字符為屋)；

p=Search(bt,'a');

if(p)printf("\n找到了\n")；

elseprintf("\n沒找到\n")；

pr血f("\n葉結點的個數為％d\n”,CountLeaf2(bt));

卜青輸入要建立的二叉樹

abc.e...fa..n..

、

醫患

質建

仔

哥

立ean

子符

為

到了a

葉結點的個數為3

Pi*essanykeytocontinue

五、在上題的基礎上，編寫統計二叉樹的結點總數，統計度為2的結點總數的函數再上

機調試。

六、以二叉鏈表為存儲結構，寫一個拷貝二叉鏈表的程序并上機調試

#include"stdio.h"

#includenstdlib.h"

typedefstructBiTNode{

chardata;

structBiTNode*lchild,*rchild;/*左右孩子指針*/

}BinTNode/BinTree;

BinTreeCreatBiTree()

{BinTreeT;

charch;

scanf(',\n%cH,&ch);

if(ch=='0,)T=NULL;

else{

T=(BinTNode*)malloc(sizeof(BinTNode));

T->data=ch;/*生成根結點*/

T->lchild=CreatBiTree();/*構造左子樹*/

T->rchild=CreatBiTree。;/*構造右子樹*/

)

return(T);}

voidInOrderOut(BinTreeT)

{/*中序遍歷輸出二叉樹T的結點值*/

if(T)

{InOrderOut(T->lchild);/*中序遍歷二叉樹的左子樹*/

printf("％3c”,T，data);/*訪問結點的數據*/

InOrderOut(T->rchild);/*中序遍歷二叉樹的右子樹*/

BinTNode*BiTreeCopy(BinTNode*T)

BinTNode*C;

if(NULL==T)

returnNULL;

C=(BinTNode*)malloc(sizeof(BinTNode));

C->data=I^>data;

C->lchild=BiTreeCopy(T->lchild);

C->rchild=BiTreeCopy(T->rchiId);

returnC;

voidmain()

(

BinTreebt,x;

printf("請輸入要建立的二叉樹)

bt=CreatBiTree();

printf("\n中序遍歷所建立的二叉樹為)

InOrderOut(bt);

printf(”\n拷貝的二叉樹為：”)；

x=BiTreeCopy(bt);

InOrderOut(x);

請輸入要建立的二叉樹

abc0e000fg00m00

電序謾歷所建立的二叉樹為cebagfm

拷貝的二叉樹為：cebagfnPressanykeytocontinue

實驗報告

院（系）：信息科學與技術學院課程名稱：數據結構日期:

班級學號實驗室

專業姓名計算機號

實驗實驗6二叉樹的基本操作成績評定

名稱

所用教師簽名

軟件VC或TC

實（1）掌握二叉樹的二叉鏈表存儲結構；

驗（2）掌握二叉樹的先序，中序，后序的遍歷方法；

目（3）利用二叉樹的遞歸遍歷方法實現二叉樹的創建，查找等操作。

的

實復習書上有關內容。

驗閱讀實驗內容1，進行程序填空，并寫出可能的結果。

準編出實驗的源程序。

備本次實驗為4學時

1.填空：

(1)CreateBiTree(&((*bt)->Lchild))

(2)T!=NULL

(3)Preorder(T->Lchild);

(4)Preorder(T->Rchild);

實驗1運行情況為：

輸入：ABD.G...CE..F..

輸出結果：

實

驗

結

果

及

分

析

2.中序、后序遍歷二叉樹的函數以及運行情況為:

L青輸入先序序列（虛結點用-表示）

hBC_G_■■CE■■F_■

用凹入表表示二叉樹：

A

B

C

E

F

前序遍歷，

F1BCGCEF

中：

BCGCEFA

后序通歷：

BCGCEFA

P*-essar??jRe七ocont;incie

3.函數：查找指定結點、統計二叉樹中葉結點的個數、求二叉樹的高度

#include<malloc.h>

#include<stdio.h>

typedefcharDataType;/*應由用戶定義DataType的實際類型*/

/*二叉樹的鏈式存儲表示*/

typedefstructNode

(

DataTypedata;

structNode*Lchild;

structNode*Rchild;/*左右孩子指針*/

[BiTNode,*BiTree;/*結點類型*/

/*構造二叉樹*/

voidCreateBiTree(BiTree*bt)

(

charch;

ch=getchar();

if(ch==;')*bt=NULL;

else/*讀入非空樹*/

(

*bt=(BiTree)malloc(sizeof(BiTNode));〃生成一個新結點

(*bt)->data=ch;

CreateBiTree(&((*bt)->Lchild));〃生成左子樹

CreateBiTree(&((*bt)->Rchild));//生成右子樹

)

}

〃查找節點

BiTreemindata(BiTreehead,chara)

(

BiTreep=head;

while(p!=NULL&&p->data!=a)

(

mindata(p->