實(shí)驗(yàn)4二叉樹 -數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告

學(xué)生姓名學(xué)號(hào)

班級(jí)指導(dǎo)老師

實(shí)驗(yàn)名稱實(shí)驗(yàn)4二叉樹實(shí)驗(yàn)成績(jī)

實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)?zāi)康模?、了解二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

2、了解二叉樹的遍歷.

實(shí)

驗(yàn)實(shí)驗(yàn)要求：(1)在主函數(shù)中，通過鍵盤輸入建立設(shè)定的完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)。

概(2)設(shè)計(jì)子函數(shù)，其功能為將順序結(jié)構(gòu)的二叉樹轉(zhuǎn)化為鏈?zhǔn)浇Y(jié)構(gòu)。

述(3)設(shè)計(jì)子函數(shù)，其功能為對(duì)給定二叉樹進(jìn)行中序遍歷，顯示遍歷結(jié)果。

(4)通過實(shí)例判斷算法和相應(yīng)程序的正確性。

(5)掌握前序遍歷二叉樹的步驟，針對(duì)任意一棵二叉樹能人工完成對(duì)二叉樹的前序

遍歷。

(6)能掌握棧的工作特點(diǎn)，并能正確應(yīng)用這一特點(diǎn)實(shí)現(xiàn)對(duì)二叉樹的遍歷。

實(shí)驗(yàn)基本原理：一、設(shè)一棵完全二叉樹用順序存儲(chǔ)方法存儲(chǔ)于數(shù)組tree中，編寫程

序：

(1)根據(jù)數(shù)組tree,建立與該二叉樹對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

(2)對(duì)該二叉樹采用中序遍歷法顯示遍歷結(jié)果。

二、設(shè)一棵二叉樹采用鏈?zhǔn)椒绞酱鎯?chǔ)，編寫一個(gè)前序遍歷該二叉樹的非遞歸算法。

實(shí)驗(yàn)設(shè)計(jì)思路、步驟和方法等：一、(1)順序存儲(chǔ)的二叉樹轉(zhuǎn)化為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，

采用遞歸算法，遞歸函數(shù)的形式為Creab(tree,n,i,b),其中形參：tree為順序存儲(chǔ)二叉

實(shí)樹的數(shù)組，n為二叉樹的結(jié)點(diǎn)數(shù)，i是二叉樹某結(jié)點(diǎn)在數(shù)組tree中的下標(biāo)(初始值為

驗(yàn)1),b為要建立的鏈?zhǔn)酱鎯?chǔ)二叉樹結(jié)點(diǎn)指針、轉(zhuǎn)化時(shí)，首先建立*b結(jié)點(diǎn)，將tree[ij

內(nèi)的值賦給*b的數(shù)據(jù)域，再調(diào)用遞歸函數(shù)分別構(gòu)造左子樹和右子樹。

容(2)中序遍歷采用遞歸算法，即中序遍歷左子樹、訪問根結(jié)點(diǎn)、中序遍歷右子樹。

二、(1)使用一個(gè)棧(指針數(shù)組)。首先將根結(jié)點(diǎn)(指針)入棧，然后逐次循環(huán)，

從棧中退出棧頂元素，作為當(dāng)前要操作結(jié)點(diǎn)的指針(設(shè)為p),訪問p的數(shù)據(jù)，然后

令其右結(jié)點(diǎn)(指針)入棧，再將其左結(jié)點(diǎn)(指針)入棧，直至棧空為止。

(2)前序遍歷的次序?yàn)椋焊Y(jié)點(diǎn)、左子樹、右子樹。

實(shí)驗(yàn)過程(實(shí)驗(yàn)中涉及的記錄、數(shù)據(jù)、分析)：

一、程序代碼如下：

/*實(shí)驗(yàn)3.1二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)*/

#include<stdio.h>

#include<stdlib.h>

#defineMaxSize20

/*二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)定義*/

typedefstructBTreeNode

(

chardata;

structBTreeNode*left;

structBTreeNode*right;

}BTreeNode;

BTreeNode*Creab(char*tree,intnjnti,BTreeNode*b);/*建立二叉樹鏈?zhǔn)浇Y(jié)構(gòu)*/

voidInorder(BTreeNode*BT);/*中序遍歷二叉樹*/

voidmain()

(

BTreeNode*BT;/*根結(jié)點(diǎn)指針*/

chartree[MaxSize],c;

intn=0;/*二叉樹的結(jié)點(diǎn)數(shù)*/

inti=l;/*結(jié)點(diǎn)在數(shù)組tree中的下標(biāo)*/

printf(”請(qǐng)輸入完全二叉樹的結(jié)點(diǎn)值(連續(xù)輸入字符，以回車結(jié)束輸入)：”)；

while((c=getchar())!-\n*)tree[++n]=c;

BT=(BTreeNode*)malloc(sizeof(BTreeNode));

BT=Creab(tree,n,i,BT);

printf(n\n中序遍歷二叉樹的輸出序列為：”)；

Inorder(BT);

printf(n\nn);

)

/*將順序結(jié)構(gòu)的二叉樹轉(zhuǎn)化為鏈?zhǔn)浇Y(jié)構(gòu)*/

BTreeNode*Creab(char*tree,intnjnti,BTreeNode*b)

1

\

BTreeNode*p;

if(i<=n)

(

if(i==l)

p=b;當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn)*/

else

p=(BTreeNode*)malloc(sizeof(BTreeNode));

p->data=tree[i];

p->left=Creab(tree,n,2*i,p);/*遞歸構(gòu)造左子樹*/

p->right=Creab(tree,n,2*i+l,p)；/*遞歸構(gòu)造右子樹*/

)

else

p=NULL;/*葉子結(jié)點(diǎn)*/

returnp;

)

/*中序遍歷二叉樹*/

voidInorder(BTreeNode*BT)

I

i

if(BT!=NULL)

(

Inorder(BT->left);/*遞歸遍歷左子樹*/

printf("%c\BT->data);

Inorder(BT->right);/*遞歸遍歷右子樹*/

)

)

二、程序代碼如下：

/*實(shí)驗(yàn)3.2二叉樹的遍歷*/

#include<stdio.h>

#include<stdlib.h>

#defineMaxSize20

/*二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)定義*/

typedefstructBTreeNode

(

chardata;

structBTreeNode*left;

structBTreeNode*right;

[BTreeNode;

/*定義棧*/

typedefstruct

(

BTreeNode*data[MaxSize];

inttop;

)Stack;

BTreeNode*Creab(char*tree,intn,inti,BTreeNode*b);/*建立二叉樹鏈?zhǔn)浇Y(jié)構(gòu)*/

voidPreorderN(BTreeNode*BT);/*前序非遞歸遍歷二叉樹*/

voidmain()

(

BTreeNode*BT;/*根結(jié)點(diǎn)指針*/

chartree[MaxSize],c;

intn=0;/*二叉樹的結(jié)點(diǎn)數(shù)*/

inti=l;/*結(jié)點(diǎn)在數(shù)組tree中的下標(biāo)*/

printf(”請(qǐng)輸入完全二叉樹的結(jié)點(diǎn)值(連續(xù)輸入字符，以回車結(jié)束輸入)：”)；

while((c=getchar())!=,\n')tree[++n]=c;

BT=(BTreeNode*)malloc(sizeof(BTreeNode));

BT=Creab(tree,n,i,BT);

printfC'\n前序遍歷二叉樹的輸出序列為：”)；

PreorderN(BT);

printf(M\nH);

)

/*將順序結(jié)構(gòu)的二叉樹轉(zhuǎn)化為鏈?zhǔn)浇Y(jié)構(gòu)*/

BTreeNode*Creab(char*tree,intn,inti,BTreeNode*b)

(

BTreeNode*p;

if(i<=n)

(

if(i==l)

p=b;/*當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn)*/

else

p=(BTreeNode*)malloc(sizeof(BTreeNode));

p->data=tree[i];

p->left=Creab(lree,n,2*i,p);/*遞歸構(gòu)造左子樹*/

p->right=Creab(tree,n,2*i4-1,p);/*遞歸構(gòu)造右子樹*/

)

else

p=NULL;/*葉子結(jié)點(diǎn)*/

returnp;

}

/*前序非遞歸遍歷二叉樹*/

voidPreorderN(BTreeNode*BT)

(

if(BT!=NULL)

(

BTreeNode*p;

Stacks;

s.top=-l;

s.top++;

s.data[s.top]=BT;/*根結(jié)點(diǎn)進(jìn)棧*/

while(s.top!=-1)

(

p=s.data[s.top];/*出棧*/

s.top";

printf(n%cM,p->data);/*訪問根結(jié)點(diǎn)*/

if(p->right!=NULL)

(

s.top++;

s.data|s.top]=p?>right;/*右孩子進(jìn)棧*/

)

if(p->left!=NULL)

{

s.top++;

s.data[s.top]=p->left;/*左孩子進(jìn)棧*/

)

)

)

else

printf("此二叉樹無效!\nn);

)

實(shí)驗(yàn)結(jié)果：一、

c\*C:\Docu>entsandSettings\AllUsers'桌面\sy3_l\Debug\sy3_l?exe”

請(qǐng)輸入完整二叉箱前基點(diǎn)卷《逑續(xù)輸入學(xué)將，以回車結(jié)束輸入）：abcdefgh

中序遍歷二叉樹的輸出序列為：hdbeafcS

Pressan9keytocontinue.

c<*C:\Docu>entsandSettings\AllUsers'桌面\sy3_l\Debug\sye*e"

請(qǐng)輸不舞嘉曾"隹續(xù)輸入字符，以回車結(jié)束輸入）：abcdefghij

中序遍歷二叉樹的輸出序列為：hdibjeafcg

Pressanykeytocontinue.

二、

c\*C:\DOCU1ESTSAIDSETTIIGS\ALLUSERS\^ffi\sy3_2\Debug\sy3_2.exe*

產(chǎn)輸胭惠曾《最輸人字符，遍睪賽歐L

,序遍歷二叉樹的輸出序列為：abdhec￡g

Pressanykeytocontinue

c<*C:\