posts - 6,  comments - 30,  trackbacks - 0

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜