二叉查找树(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>
2
const int MaxSize=100;
3
class BSTree;
4![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
5
**节点定义及构造函数的实现
6
*/
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class BTreeNode
{
8
friend class BSTree; //申明友元以便访问其私有变量
9
public:
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
BTreeNode()
{
11
left=NULL;
12
right=NULL;
13
}
14
private:
15
int data;
16
BTreeNode* left;
17
BTreeNode* right;
18
};
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
20
**BST的定义
21
*/
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class BSTree
{
23
public:
24
BSTree();
25
void insert(int k); //向该树中插入K
26
bool Search(BTreeNode* node1,int k,int&); //搜索根节点node的数且值为k节点
27
void DeleteBST(BTreeNode *); //删除树释放空间
28![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
BTreeNode* Getroot()
{return Root;}//返回根节点,以便外部函数调用
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int Getcount()
{return count;} //返回搜索的次数
30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int GetSize()
{return size;} //返回该树节点数
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void Clear()
{count=0;} //用于每次搜索完后将搜索次数清0,以便记录下次搜索的次数
32
~BSTree(); //释放内存
33
private:
34
BTreeNode* Root;
35
int size; //记录该二叉查找树的大小
36
int count; //记录比较次数
37
};
38![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
39
**BST的实现
40
*/
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
BSTree::BSTree()
{
42
count=0; //记录数据清0
43
int n;
44
cout<<"请输入BST节点个数:";
45
cin>>n;
46
size=n; //输入二叉查找树的大小
47
Root=NULL;
48
}
49![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void BSTree::insert(int k)
{
50
BTreeNode* p=Root;
51
BTreeNode* pp=NULL;
52![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(Root)
{
62
if(pp->data>k)
63
pp->left=R;
64
else
65
pp->right=R;
66
}
67
else
68
Root=R;
69
}
70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool BSTree::Search(BTreeNode* r,int k,int &e)
{
71![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(r)
{//查找关键值为k,并用e保存
72![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(r->data==k)
{
73
e=r->data;
74
count++;
75
return true;
76
}
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else if(r->data>k )
{
78
count++;
79
Search(r->left,k,e);
80
}
81![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else if(r->data<k)
{
82
count++;
83
Search(r->right,k,e);
84
}
85
}
86
else
87
return false;
88
}
89![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void BSTree::DeleteBST(BTreeNode *r)
{
90![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(r)
{//按照后序遍历的方式删除该树
91
DeleteBST(r->left);
92
DeleteBST(r->right);
93
delete r;
94
r=NULL;
95
}
96
}
97![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
BSTree::~BSTree()
{
98
DeleteBST(Root);
99
}
100![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
101
测试
102
*/
103
void main()
104![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
105
BSTree bst;
106
int Array[MaxSize];
107
cout<<"请输入二叉查找树的数据:";
108
for(int i=0;i<bst.GetSize();i++)
109![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
110
cin>>Array[i];
111
}
112
for(i=0;i<bst.GetSize();i++)
113![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
114
bst.insert(Array[i]);
115
}
116
int k,x;
117
cout<<"请输入要查找的数:";
118
cin>>k;
119
while(bst.Search(bst.Getroot(),k,x))
120![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
121
cout<<"查找成功! 比了"<<bst.Getcount()<<"次"<<endl;
122
bst.Clear();
123
cout<<"请输入要查找的数:";
124
cin>>k;
125
}
126
cout<<"查找不成功! 比了"<<bst.Getcount()<<"次"<<endl;
127
cin.get();
128![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
129
}
130
131![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
132![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2011-01-08 21:01
あ维wêiセ 阅读(1898)
评论(0) 编辑 收藏 引用 所属分类:
C++