二叉查找樹（BST），顧名思義，其有利于數據的查找、搜索。
所謂二叉查找樹：
1、其有可能是一顆空樹。
2、若不是空樹
=每個節點有一個關鍵值（在這里假設每兩個元素沒有相同的關鍵值，對于相同的可以根據具體問題需要來設計自己的BST）
=根節點的關鍵值（如果有）比左子樹關鍵值大，但是比右子樹關鍵值小。
=根節點的左右子樹也是二叉查找樹（BST）。
現在就具體問題具體分析。
構建一個BST,在BST中查找一個關鍵值，如果查找成功則顯示查找成功和比較次數
如果查找不成功則顯示查找成功和比較次數
首先定義二叉查找樹的節點
ADT BSTNode
操作對象：其關鍵值data
基本操作：
BSTNode();//構建一個節點
~BSTNode();//撤銷節點
ADT BSTree
操作對象：BSTNode
基本操作：
BSTree();//構建空BST
void insert(int k); //向該樹中插入K
bool Search(BTreeNode* node1,int k,int&); //搜索根節點node的數且值為k節點
void DeleteBST(BTreeNode *); //刪除樹釋放空間
BTreeNode* Getroot(){return Root;}//返回根節點，以便外部函數調用
int Getcount(){return count;} //返回搜索的次數
int GetSize(){return size;} //返回該樹節點數
void Clear(){count=0;} //用于每次搜索完后將搜索次數清0，以便記錄下次搜索的次數
~BSTree(); //撤銷BST
其代碼如下
1
#include<iostream.h>
2const int MaxSize=100;
3class BSTree;
4
/**//*
5
**節點定義及構造函數的實現
6
*/
7class BTreeNode
{
8 friend class BSTree; //申明友元以便訪問其私有變量
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); //向該樹中插入K
26 bool Search(BTreeNode* node1,int k,int&); //搜索根節點node的數且值為k節點
27 void DeleteBST(BTreeNode *); //刪除樹釋放空間
28 BTreeNode* Getroot(){return Root;}//返回根節點，以便外部函數調用
29 int Getcount(){return count;} //返回搜索的次數
30 int GetSize(){return size;} //返回該樹節點數
31 void Clear(){count=0;} //用于每次搜索完后將搜索次數清0，以便記錄下次搜索的次數
32 ~BSTree(); //釋放內存
33private:
34 BTreeNode* Root;
35 int size; //記錄該二叉查找樹的大小
36 int count; //記錄比較次數
37};
38/**//*
39**BST的實現
40*/
41BSTree::BSTree(){
42 count=0; //記錄數據清0
43 int n;
44 cout<<"請輸入BST節點個數:";
45 cin>>n;
46 size=n; //輸入二叉查找樹的大小
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){//查找關鍵值為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){//按照后序遍歷的方式刪除該樹
91 DeleteBST(r->left);
92 DeleteBST(r->right);
93 delete r;
94 r=NULL;
95 }
96}
97BSTree::~BSTree(){
98 DeleteBST(Root);
99}
100/**//*
101測試
102*/
103void main()
104{
105 BSTree bst;
106 int Array[MaxSize];
107 cout<<"請輸入二叉查找樹的數據:";
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<<"請輸入要查找的數:";
118 cin>>k;
119 while(bst.Search(bst.Getroot(),k,x))
120 {
121 cout<<"查找成功! 比了"<<bst.Getcount()<<"次"<<endl;
122 bst.Clear();
123 cout<<"請輸入要查找的數:";
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セ 閱讀(1947)
評論(0) 編輯 收藏 引用 所屬分類:
C++