廣東工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)二叉樹課程設(shè)計(jì)

本文格式為Word版，下載可任意編輯——廣東工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)二叉樹課程設(shè)計(jì)

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

題目：二叉樹抽象數(shù)據(jù)類型

學(xué)院計(jì)算機(jī)學(xué)院專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)年級(jí)班別學(xué)號(hào)學(xué)生姓名指導(dǎo)教師

成績(jī)____________________

2023年6月

一．試驗(yàn)概要

試驗(yàn)項(xiàng)目名稱:二叉樹抽象數(shù)據(jù)類型的實(shí)現(xiàn)試驗(yàn)項(xiàng)目性質(zhì):設(shè)計(jì)性試驗(yàn)所屬課程名稱:數(shù)據(jù)結(jié)構(gòu)試驗(yàn)計(jì)劃學(xué)時(shí):6二.試驗(yàn)?zāi)康?/p>

1.了解二叉樹的定義以及各項(xiàng)基本操作。2.實(shí)現(xiàn)二叉樹存儲(chǔ)、遍歷及其他基本功能三.試驗(yàn)儀器設(shè)備和材料

硬件：PC機(jī)

軟件：VisualC++6.0

四．試驗(yàn)的內(nèi)容

1.二叉樹類型定義以及各基本操作的簡(jiǎn)要描述；

ADTBinaryTree{

數(shù)據(jù)對(duì)象D:D是具有一致特性的數(shù)據(jù)元素的集合.數(shù)據(jù)關(guān)系R:

若D=?，則R=,稱BinaryTree為空二叉樹；若D≠，則R={H}，H是如下二元關(guān)系：

(1)

在D中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

(2)(3)

若D-{root}≠?，則存在D-{root}={D1,Dr}，且D1∩Dr=?；若D1≠?，則D1中存在惟一的元素x1，∈H，且存在Dr上的關(guān)系Hr∈H；H={，，H1,Hr}；

(4)

（D1，{H1}）是一棵符合本定義的二叉樹，稱為根的左子樹，是一棵符合本定義的二叉樹，稱為根的右子樹。

基本操作P:

InitBiTree(

操作結(jié)果：構(gòu)造空二叉樹T。DestroyBiTree(

初始條件：二叉樹T存在。操作結(jié)果：銷毀二叉樹T。CreateBiTree(

初始條件：definition給出二叉樹T的定義。操作結(jié)果：按definition構(gòu)造二叉樹T。ClearBiTree(

初始條件：二叉樹T存在。操作結(jié)果：將二叉樹T清為空樹。BiTreeEmpty(T);

初始條件：二叉樹T存在。

操作結(jié)果：若T為空二叉樹，則返回TURE,否則FALSE。BiTreeDepth(T);

初始條件：二叉樹T存在。操作結(jié)果：返回T的深度。Root(T);

初始條件：二叉樹T存在。操作結(jié)果：返回T的根。Value(T,e);

初始條件：二叉樹T存在，e是T中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e的值。Assign(T,

初始條件：二叉樹T存在，e是T中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：結(jié)點(diǎn)e賦值為value。Parent(T,e);

初始條件：二叉樹T存在，e是T中的某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若e是T的非跟結(jié)點(diǎn)，則返回它的雙親，否則返回“空〞。LeftChild(T,e);

初始條件：二叉樹T存在，e是T中的某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的左孩子。若e無左孩子，則返回“空〞。RightChild(T,e);

初始條件：二叉樹T存在，e是T中的某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的右孩子。若e無右孩子，則返回“空〞。LeftSibling(T,e);

初始條件：二叉樹T存在，e是T中的某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的左兄弟。若e無左孩子或無左兄弟，則返回“空〞。RightSibling(T,e);

初始條件：二叉樹T存在，e是T中的某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回e的右兄弟。若e無右孩子或無右兄弟，則返回“空〞。

}ADTBinaryTree

2.存儲(chǔ)結(jié)構(gòu)：采用無頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)3.源代碼：頭文件及存儲(chǔ)結(jié)構(gòu):#include#include

#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW0

#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度

typedefcharTElemType;

typedefstructBiTNode//二叉樹結(jié)構(gòu)體{

TElemTypedata;

structBiTNode*lchild,*rchild;}BiTNode,*BiTree;

typedefBiTreeQElemType;

typedefstructQNode{

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;//結(jié)點(diǎn)結(jié)構(gòu)體

typedefstruct{

QueuePtrfront;QueuePtrrear;}LinkQueue;算法設(shè)計(jì)：

intInitQueue(LinkQueue

if(!Q.front)//存儲(chǔ)分派失敗

//鏈隊(duì)列結(jié)構(gòu)體

exit(OVERFLOW);