《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-二叉排序樹.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-二叉排序樹.doc（12頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告題目：二叉排序樹 學(xué) 院 計(jì)算機(jī)學(xué)院 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 年級班別 級 班 學(xué) 號 編 號 學(xué)生姓名 指導(dǎo)教師 成 績 _2015 年 月報(bào)告：報(bào)告內(nèi)容：詳細(xì)完整基本完整 不完整設(shè)計(jì)方案：非常合理合理基本合理 較差算法實(shí)現(xiàn)：全部實(shí)現(xiàn)基本實(shí)現(xiàn)部分實(shí)現(xiàn) 實(shí)現(xiàn)較差測試樣例：完備比較完備基本完備 不完備文檔格式：規(guī)范比較規(guī)范基本規(guī)范 不規(guī)范答辯：理解題目透徹，問題回答流利理解題目較透徹，回答問題基本正確部分理解題目，部分問題回答正確未能完全理解題目，答辯情況較差總評成績：優(yōu)良中及格不及格1. 題目選擇合適的存儲(chǔ)結(jié)構(gòu)，建立二叉排序樹，完成插入、刪除等基本操作。 ADT Binary

2、 Sort Tree 數(shù)據(jù)對象：int RcdType data; 數(shù)據(jù)關(guān)系：BSTNode *lchild, *rchild; 基本操作： InitBST(&T) 操作結(jié)果：構(gòu)造一個(gè)空的二叉排序樹T。 DestroyBST(&T) 初始條件：二叉排序樹T已存在。 操作結(jié)果：銷毀二叉排序樹T。 SearchBST(&T, key) 初始條件：二叉排序樹T已存在。 操作結(jié)果：若二叉排序樹T中存在值為key的結(jié)點(diǎn)，則返回該結(jié)點(diǎn)指針，否則NULL。 InsertBST(&T, e) 初始條件：二叉排序樹T已存在且T中不存在值為e.key的結(jié)點(diǎn)。 操作結(jié)果：將e插入到T。 DeleteBST(&T,

3、key) 初始條件：二叉排序樹T已存在在且T中存在值為key的結(jié)點(diǎn)。 操作結(jié)果：刪除值為key的結(jié)點(diǎn)。 TraverseBST(&T, e) 初始條件：二叉排序樹T已存在 操作結(jié)果：遍歷二叉排序樹T中的元素。 PrintRcdType(e) 初始條件：二叉排序樹T已存在。 操作結(jié)果：依次輸出T的每個(gè)元素。ADT Binary Sort Tree 2存儲(chǔ)結(jié)構(gòu)定義#include#include#include#define OVERFLOW -1#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;t

4、ypedef int KeyType;typedef struct KeyType key; RcdType; typedef struct BSTNode RcdType data;struct BSTNode *lchild, *rchild; BSTNode, * BSTree;3. 算法設(shè)計(jì)使用二叉鏈表存儲(chǔ)結(jié)構(gòu)Status InitBST(BSTree &T) /構(gòu)造一個(gè)空的二叉排序樹T T=NULL; return OK;Status DestroyBST(BSTree &T) /銷毀二叉排序樹 T if (T) if( T-lchild ) DestroyBST( T-lchild

5、 ); if( T-rchild ) DestroyBST( T-rchild ); free(T); T = NULL; return OK;BSTree SearchBST(BSTree &T,KeyType key) /二叉排序樹查找的遞歸實(shí)現(xiàn) if(NULL=T)return NULL; /查找失敗 if(T-data.key=key)return T; /查找成功 if(T-data.keykey) return SearchBST(T-lchild,key); /在左子樹上繼續(xù)查找 return SearchBST(T-rchild,key); /在右子樹上繼續(xù)查找void Del

6、eteNode(BSTree &T) /二叉排序樹中刪除結(jié)點(diǎn)T，并重接它的左或右子樹 BSTree q,s; if(NULL=T-rchild) /右子樹空則只需重接它的左子樹 q=T; T=T-lchild; free(q); else if(NULL=T-lchild) /只需重接它的右子樹 q=T; T=T-rchild; free(q); else /左右子樹均不空 q=T; s=T-lchild; while(NULL=s-rchild) q=s; s=s-rchild; /轉(zhuǎn)左，然后向右到盡頭 T-data=s-data; /s指向被刪結(jié)點(diǎn)的前驅(qū) if(q!=T) q-rchild

7、=s-lchild; /重接q的右子樹 else q-lchild=s-lchild; / 重接q的左子樹 free(s); Status DeleteBST(BSTree &T,KeyType key) /二叉排序樹的刪除操作 /若二叉排序樹T中存在值為key的結(jié)點(diǎn)，則刪除該節(jié)點(diǎn)，并返回TRUE；否則FALSE if(NULL=T) return FALSE; /不存在值為key的結(jié)點(diǎn) if(key=T-data.key) /找到值為key的結(jié)點(diǎn) DeleteNode(T); return TRUE; if(keydata.key) return DeleteBST(T-lchild,key

8、); /返回在左子樹刪除的結(jié)果 return DeleteBST(T-rchild,key); /返回在右子樹刪除的結(jié)果 Status InsertBST(BSTree &T,RcdType e) /二叉排序樹插入 /若二叉排序樹T中不存在值為e.key的結(jié)點(diǎn)，則插入到T BSTree s; /若二叉排序樹是空樹，則創(chuàng)建新插入的結(jié)點(diǎn)并作為根節(jié)點(diǎn) if(NULL=T) s=(BSTNode*)malloc(sizeof(BSTNode); if(NULL=s)return OVERFLOW; s-data=e; s-lchild=NULL; s-rchild=NULL; T=s; return

9、TRUE; if(e.keydata.key) return InsertBST(T-lchild,e); /插入結(jié)點(diǎn)的值小于根結(jié)點(diǎn)，在左子樹遞歸插入if(e.keyT-data.key) return InsertBST(T-rchild,e); /插入結(jié)點(diǎn)的值大于根結(jié)點(diǎn)，在右子樹遞歸插入 return FALSE; Status TraverseBST(BSTree &T,Status (*visit) (RcdType e) / 中序遞歸遍歷輸出T，visit是對數(shù)據(jù)元素的應(yīng)用函數(shù) if(T) TraverseBST(T-lchild,visit); /遞歸遍歷T的左子樹 visit(T

10、-data); /訪問結(jié)點(diǎn)的數(shù)據(jù)域 TraverseBST(T-rchild,visit); /遞歸遍歷T的右子樹 return OK;Status PrintRcdType(RcdType e) /依次輸出二叉排序樹結(jié)點(diǎn)的值 printf(%d,e.key); return OK;void main() /主函數(shù) int i,j=0,k; int a; int menue=0; int status; KeyType temp; int (*visit)(RcdType e); int t20=0; RcdType e; BSTNode *p; BSTree Tree; visit=PrintRcdType; for(;) for(;menue=0;) /menue=0則循環(huán)開始菜單 printf(n* 開始菜單 *n); printf(* 1.創(chuàng)建二叉排序樹 t*n); printf(* 2.退出 t*n); pri