二叉查找樹(shù)（BST），顧名思義，其有利于數(shù)據(jù)的查找、搜索。
所謂二叉查找樹(shù)：
1、其有可能是一顆空樹(shù)。
2、若不是空樹(shù)
=每個(gè)節(jié)點(diǎn)有一個(gè)關(guān)鍵值（在這里假設(shè)每?jī)蓚€(gè)元素沒(méi)有相同的關(guān)鍵值，對(duì)于相同的可以根據(jù)具體問(wèn)題需要來(lái)設(shè)計(jì)自己的BST）
=根節(jié)點(diǎn)的關(guān)鍵值（如果有）比左子樹(shù)關(guān)鍵值大，但是比右子樹(shù)關(guān)鍵值小。
=根節(jié)點(diǎn)的左右子樹(shù)也是二叉查找樹(shù)（BST）。
現(xiàn)在就具體問(wèn)題具體分析。
構(gòu)建一個(gè)BST,在BST中查找一個(gè)關(guān)鍵值，如果查找成功則顯示查找成功和比較次數(shù)
如果查找不成功則顯示查找成功和比較次數(shù)
首先定義二叉查找樹(shù)的節(jié)點(diǎn)
ADT BSTNode
操作對(duì)象：其關(guān)鍵值data
基本操作：
BSTNode();//構(gòu)建一個(gè)節(jié)點(diǎn)
~BSTNode();//撤銷(xiāo)節(jié)點(diǎn)
ADT BSTree
操作對(duì)象：BSTNode
基本操作：
BSTree();//構(gòu)建空BST
void insert(int k); //向該樹(shù)中插入K
bool Search(BTreeNode* node1,int k,int&); //搜索根節(jié)點(diǎn)node的數(shù)且值為k節(jié)點(diǎn)
void DeleteBST(BTreeNode *); //刪除樹(shù)釋放空間
BTreeNode* Getroot(){return Root;}//返回根節(jié)點(diǎn)，以便外部函數(shù)調(diào)用
int Getcount(){return count;} //返回搜索的次數(shù)
int GetSize(){return size;} //返回該樹(shù)節(jié)點(diǎn)數(shù)
void Clear(){count=0;} //用于每次搜索完后將搜索次數(shù)清0，以便記錄下次搜索的次數(shù)
~BSTree(); //撤銷(xiāo)BST
其代碼如下
1
#include<iostream.h>
2const int MaxSize=100;
3class BSTree;
4
/**//*
5
**節(jié)點(diǎn)定義及構(gòu)造函數(shù)的實(shí)現(xiàn)
6
*/
7class BTreeNode
{
8 friend class BSTree; //申明友元以便訪(fǎng)問(wèn)其私有變量
9public:
10
BTreeNode(){
11 left=NULL;
12 right=NULL;
13
}
14private:
15 int data;
16 BTreeNode* left;
17 BTreeNode* right;
18};
19/**//*
20**BST的定義
21*/
22class BSTree{
23public:
24 BSTree();
25 void insert(int k); //向該樹(shù)中插入K
26 bool Search(BTreeNode* node1,int k,int&); //搜索根節(jié)點(diǎn)node的數(shù)且值為k節(jié)點(diǎn)
27 void DeleteBST(BTreeNode *); //刪除樹(shù)釋放空間
28 BTreeNode* Getroot(){return Root;}//返回根節(jié)點(diǎn)，以便外部函數(shù)調(diào)用
29 int Getcount(){return count;} //返回搜索的次數(shù)
30 int GetSize(){return size;} //返回該樹(shù)節(jié)點(diǎn)數(shù)
31 void Clear(){count=0;} //用于每次搜索完后將搜索次數(shù)清0，以便記錄下次搜索的次數(shù)
32 ~BSTree(); //釋放內(nèi)存
33private:
34 BTreeNode* Root;
35 int size; //記錄該二叉查找樹(shù)的大小
36 int count; //記錄比較次數(shù)
37};
38/**//*
39**BST的實(shí)現(xiàn)
40*/
41BSTree::BSTree(){
42 count=0; //記錄數(shù)據(jù)清0
43 int n;
44 cout<<"請(qǐng)輸入BST節(jié)點(diǎn)個(gè)數(shù):";
45 cin>>n;
46 size=n; //輸入二叉查找樹(shù)的大小
47 Root=NULL;
48}
49void BSTree::insert(int k){
50 BTreeNode* p=Root;
51 BTreeNode* pp=NULL;
52 while(p){
53 pp=p;
54 if(p->data>k)
55 p=p->left;
56 else
57 p=p->right;
58 }
59 BTreeNode* R=new BTreeNode;
60 R->data=k;
61 if(Root){
62 if(pp->data>k)
63 pp->left=R;
64 else
65 pp->right=R;
66 }
67 else
68 Root=R;
69}
70bool BSTree::Search(BTreeNode* r,int k,int &e){
71 if(r){//查找關(guān)鍵值為k,并用e保存
72 if(r->data==k){
73 e=r->data;
74 count++;
75 return true;
76 }
77 else if(r->data>k ) {
78 count++;
79 Search(r->left,k,e);
80 }
81 else if(r->data<k){
82 count++;
83 Search(r->right,k,e);
84 }
85 }
86 else
87 return false;
88}
89void BSTree::DeleteBST(BTreeNode *r){
90 if(r){//按照后序遍歷的方式刪除該樹(shù)
91 DeleteBST(r->left);
92 DeleteBST(r->right);
93 delete r;
94 r=NULL;
95 }
96}
97BSTree::~BSTree(){
98 DeleteBST(Root);
99}
100/**//*
101測(cè)試
102*/
103void main()
104{
105 BSTree bst;
106 int Array[MaxSize];
107 cout<<"請(qǐng)輸入二叉查找樹(shù)的數(shù)據(jù):";
108 for(int i=0;i<bst.GetSize();i++)
109 {
110 cin>>Array[i];
111 }
112 for(i=0;i<bst.GetSize();i++)
113 {
114 bst.insert(Array[i]);
115 }
116 int k,x;
117 cout<<"請(qǐng)輸入要查找的數(shù):";
118 cin>>k;
119 while(bst.Search(bst.Getroot(),k,x))
120 {
121 cout<<"查找成功! 比了"<<bst.Getcount()<<"次"<<endl;
122 bst.Clear();
123 cout<<"請(qǐng)輸入要查找的數(shù):";
124 cin>>k;
125 }
126 cout<<"查找不成功! 比了"<<bst.Getcount()<<"次"<<endl;
127 cin.get();
128
129}
130
131
132
posted on 2011-01-08 21:01
あ維wêiセ 閱讀(1924)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
C++