1、HUNAN UNIVERSITY課程實(shí)習(xí)報(bào)告題 目： BST 學(xué)生姓名 康小雪 學(xué)生學(xué)號 20090810310 專業(yè)班級 計(jì)科三班 指導(dǎo)老師 李曉鴻 完 成 日 期 2010-12-11 5 / 5文檔可自由編輯打印一、 需求分析1 該程序可以從通過從鍵盤輸入結(jié)點(diǎn)的個(gè)數(shù)和結(jié)點(diǎn)信息（數(shù)字）來建立一個(gè)新的二叉樹，輸入的數(shù)字可以不按大小順序，但大小不能重復(fù)；2 還可以輸入新的數(shù)據(jù)，計(jì)算機(jī)可通過在二叉樹中比較查找是否有該數(shù)據(jù)，若有，則計(jì)算機(jī)返回“查找成功”及查找時(shí)比較的次數(shù)，若沒有則返回“查找不成功”及查找時(shí)比較的次數(shù)，由此形成一個(gè)動(dòng)態(tài)查找表輸入輸出舉例輸入：8/BST的節(jié)點(diǎn)個(gè)數(shù)34, 76, 45

2、, 18, 26, 54, 92, 65 /8個(gè)數(shù)據(jù)45/查找 45輸出：查找成功 3 /返回成功和查找時(shí)比較的次數(shù) 34/查找 34輸出：查找成功 1 /返回成功和查找時(shí)比較的次數(shù)100/查找 100輸出：查找不成功 3 /返回成功和查找時(shí)比較的次數(shù)二、 概要設(shè)計(jì)抽象數(shù)據(jù)類型二叉樹ADT BiTree數(shù)據(jù)對象 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） 若D-root空集，則存在D-root的一個(gè)劃分D1,D

3、r 且D1Dr=空集；（3） 若D1空集，則D1中存在唯一元素x1，<root，x1>H,且存在D1shang de guanxi H1=H;ruo Dr空集，則Dr中存在唯一的元素，xr，<root，xr>H，且存在Dr上的關(guān)系HrH;H=<root,x1>,<root,xr>,H1,Hr;（4） (D1,H1)是一棵符合本定義的二叉樹，稱為根的左子樹，(Dr，Hr)是一棵符合本定義的二叉樹，稱為根的右子樹基本操作P:Bool BST:BSTSearch(int key,int& count)/在BST中查找元素 bool BST:BS

4、TInsert(int key)/在BST中插入一個(gè)新的元素bool BST:BSTSearchHelp(BSTNode* root,int key,int& count)/查找的輔助函數(shù)，判斷兩個(gè)關(guān)鍵記錄是否相等，若相等則返回，若大于則在右子樹中查找，若小于就在左子樹中查找bool BST:BSTInsertHelp(BSTNode* root,int key,BSTNode* rootParent)/插入的輔助函數(shù)，在當(dāng)前節(jié)點(diǎn)的左或右子樹插入一個(gè)節(jié)點(diǎn)void BST:BSTDestoryHelp(BSTNode* root)/銷毀二叉樹ADT Tree算法的基本思想先輸入元素，構(gòu)建

5、一棵二叉樹，再輸入需要查找的元素，在二叉樹中查找是否存在該元素。程序的流程程序由二個(gè)模塊組成：（1）輸入建立模塊：在主函數(shù)中輸入結(jié)點(diǎn)數(shù)和結(jié)點(diǎn)信息并建立相應(yīng)的二叉樹（2）輸入查找模塊：輸入需要查找的數(shù)據(jù)，并在二叉樹中查找最后返回查找信息三、詳細(xì)設(shè)計(jì)物理數(shù)據(jù)類型二叉樹class BST/二叉樹private:class BSTNode/二叉樹節(jié)點(diǎn) BSTNode* leftChildPtr;/左孩子 BSTNode* rightChildPtr;/右孩子 int value;/值 BSTNode* root;/根節(jié)點(diǎn);算法的具體步驟/基本操作的函數(shù)原型BST:BST() root=0;/初始化根節(jié)

6、點(diǎn)為0BST:BST() BSTDestoryHelp(root);/析構(gòu)函數(shù)銷毀二叉樹bool BST:BSTSearch(int key,int& count) return BSTSearchHelp(root,key,count);/在二叉樹中查找bool BST:BSTInsert(int key)/插入新元素 if(root=0) root=new BSTNode(key,0,0); return true; return BSTInsertHelp(root,key,0);bool BST:BSTSearchHelp(BSTNode* root,int key,int&a

7、mp; count)/查找 if(root=0) return false; if(key=root->value) count+; return true; else if(key<root->value) count+; return BSTSearchHelp(root->leftChildPtr,key,count); else count+; return BSTSearchHelp(root->rightChildPtr,key,count); bool BST:BSTInsertHelp(BSTNode* root,int key,BSTNode*

8、rootParent)/插入 if(root=0) if(key<rootParent->value) rootParent->leftChildPtr=new BSTNode(key,0,0); else rootParent->rightChildPtr=new BSTNode(key,0,0); return true; if(key=root->value) return false; else if(key<root->value) return BSTInsertHelp(root->leftChildPtr,key,root); e

9、lse return BSTInsertHelp(root->rightChildPtr,key,root);void BST:BSTDestoryHelp(BSTNode* root)/銷毀二叉樹 if(root=0) return ; BSTDestoryHelp(root->leftChildPtr); BSTDestoryHelp(root->rightChildPtr); delete root;算法的時(shí)空分析遍歷所有的結(jié)點(diǎn)上限是O(n),動(dòng)態(tài)查找的增長率上限O(log(n)<=F(n)<=O(n),故此算法的增長率上限為O(n)輸入和輸出的格式請輸入記錄的個(gè)數(shù)n: 請輸入 n個(gè)記錄(整數(shù)):請輸入你想查找的關(guān)鍵記錄: 關(guān)鍵記錄已被找到.比較次數(shù)為: .四、調(diào)試分析1看了書代碼寫出來了，編譯無錯(cuò)，就是運(yùn)行有問題，不知道怎么搞，后來向同學(xué)請教了代碼，看懂了，寫得也和人家的差不