二叉查找树（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セ 阅读(1907)
评论(0) 编辑 收藏 引用 所属分类:
C++