加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

树表的查找技术

(2013-08-24 16:45:01)
标签:

树表

查找技术

it

分类: 数据结构

基本概念

        二叉排序树(Binary Sort Tree)又称二叉查找树。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树;

具体的图解

树表的查找技术

树表的查找技术

树表的查找技术

 

部分代码的实现:

//声明类BiSortTree及定义结构BiNode,文件名为bisorttree.h  

#ifndef BISORTTREE_H  

#define BISORTTREE_H  

  

struct BiNode  

 

  int data;  

  BiNode *lchild, *rchild;  

};  

  

class BiSortTree    //假定记录中只有一个整型数据项  

 

public:  

    BiSortTree(int a[ ], int n);    //建立查找集合a[n]的二叉排序树  

    ~BiSortTree(void);        //析构函数,释放二叉排序树中所有结点,同二叉链表的析构函数  

    BiNode* Getroot( );       //获取指向根结点的指针  

    BiNode* InsertBST(BiNode *root, BiNode *s);          //在二叉排序树中插入一个结点s  

    void DeleteBST(BiNode *p, BiNode *f );               //删除结点f的左孩子结点p  

    BiNode* SearchBST(BiNode *root, int k, int count);   //查找值为k的结点  

private:  

    BiNode *root;    //二叉排序树(即二叉链表)的根指针  

    void Release(BiNode *root);   //析构函数调用  

};  

#endif  

 

 

[cpp] view plaincopy

//定义类BiSortTree中的成员函数,文件名为bisorttree.cpp  

#include  

#include"bisorttree.h"  

using namespace std;  

  

  

BiSortTree::BiSortTree(int a[ ], int n)//构造函数  

    

    root NULL;  

    for (int 0; n; i++)  

     

        BiNode* new BiNode;  

        s->data a[i];  

        s->lchild NULL;  

        s->rchild NULL;  

        root InsertBST(root, s);  

        

 

  

BiSortTree::~BiSortTree(void)  

  

    Release(root);    

 

  

  

BiNode* BiSortTree::Getroot(  

 

    return root;  

 

  

  

BiNode* BiSortTree::InsertBST(BiNode *root, BiNode *s)  

 

   if(root==NULL) return s;  

   else{      

        if(s->datadata) root->lchild InsertBST(root->lchild, s);//插入到左子树中  

        else  root->rchild InsertBST(root->rchild, s);                 //插入到右子树中  

        return root;  

        

 

  

  

void BiSortTree::DeleteBST(BiNode *p, BiNode *f   

 

    f->lchild;  

    BiNode *par;  

    BiNode *s;  

    if(!p->lchild && !p->rchild){ //p为叶子      

        f->lchild NULL;    

        delete p;  

     

    else{   

        if (!p->rchild){         //p只有左子树              

            f->lchild p->lchild;  

            delete p;  

         

        else{   

            if (!p->lchild){     //p只有右子树                

                f->lchild p->rchild;  

                delete p;  

             

            else{                //左右子树均不空               

                 par p;    

                 p->rchild;    

                 while (s->lchild!=NULL)   //查找最左下结点  

                  

                     par s;  

                     s->lchild;  

                  

                 p->data s->data;  

                 if (par==p)  par->rchild s->rchild;  //处理特殊情况  

                 else par->lchild s->rchild;          //一般情况  

                 delete s;  

                  //左右子树均不空的情况处理完毕  

         

     

 

  

BiNode* BiSortTree::SearchBST(BiNode *root, int k, int count)  

 

    if(root==NULL){       

        cout<<"此结点不存在!"<<endl;   

        cout<<"比较次数为"<<count<<endl;  

        return NULL;  

     

    else{   

        if (root->data==k){ //查找成功,返回          

            count++;  

            cout<<"查找"<<root->data<<"成功!"<<endl;  

            cout<<"比较次数为"<<count<<endl;  

            return root;  

         

        else{   

            if (k root->data){            

                count++;  

                return SearchBST(root->lchild, k,count);  //查找左子树  

             

            else{  

                count++;  

                return SearchBST(root->rchild, k,count);  //查找右子树  

             

         

     

 

  

void BiSortTree::Release(BiNode* root)  

 

  if (root != NULL){                    

      Release(root->lchild);   //释放左子树  

      Release(root->rchild);   //释放右子树  

      delete root;  

     

 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:平衡二叉树
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇平衡二叉树
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有