二叉搜索树BST

目录

一:二叉搜索树定义

二:二叉搜索树数据结构 

二叉搜索树的类定义

 三:二叉搜索树的两种非递归遍历

前序遍历

层次遍历

 四:两种方法实现添加元素

递归实现

循环实现

五:构造函数和析构函数 

构造函数

析构函数

 六:两种方法实现查询

 递归实现

循环实现

七:两种方法找结点的父结点 

第一种递归

第二种循环 

八:递归中序遍历

 九:结点的删除---两种方法

 第一种---指针的引用*&

 第二种:结点指针的传递


一:二叉搜索树定义

 特殊性质:

中序遍历一颗二叉搜索树会按照递增排序

二:二叉搜索树数据结构 

数据元素采用k-v对----k是键值,v是存储内容

//k-v对集合
template<class KEY,class VALUE>
struct SET{
    KEY key;
    VALUE value;
    //构造函数
    SET(KEY k,VALUE v):key(k),value(v){}
};

二叉搜索树的类定义

//二叉搜索树
template<class KEY,class VALUE>
class bsTree{
private:
    //BST结点
    struct bsNode{
    SET<KEY,VALUE> data;//普遍结点,不是指针
    bsNode *left,*right;
    //构造函数
    bsNode(const SET<KEY,VALUE>& x,bsNode* lc=NULL,bsNode* rc=NULL):
       data(x),left(lc),right(rc){}
    };
    //根节点指针
    bsNode* root;
}

根节点指针,每个节点存储k-v对,和指向左右孩子的指针

 三:二叉搜索树的两种非递归遍历

前序遍历

//前序遍历
template<class KEY,class VALUE>
void bsTree<KEY,VALUE>::preTraverse() const{
    if(root==NULL) return;
    stack<bsNode*> sta;
    sta.push(root);
    bsNode* tmp;
    cout<<"前序遍历:";
    while(!sta.empty()){
       tmp=sta.top();
       sta.pop();
       cout<<"("<<tmp->data.key<<","<<tmp->data.value<<")"<<"   ";
       //后进先出
       if(tmp->right) sta.push(tmp->right);
       if(tmp->left)  sta.push(tmp->left);
    }
    cout<<endl;
}

注意用标准库中的栈:#include<stack>

注意:先右孩子再左孩子

层次遍历

//层次遍历
template<class KEY,class VALUE>
void bsTree<KEY,VALUE>::levelTraverse() const{
    if(root==NULL) return;
    queue<bsNode*> que;
    que.push(root);
    bsNode* tmp;
    cout<<"层次遍历:";
    while(!que.empty()){
       tmp=que.front();
       que.pop();
       cout<<"("<<tmp->data.key<<","<<tmp->data.value<<")"<<"   ";
       if(tmp->left)  que.push(tmp->left);
       if(tmp->right) que.push(tmp->right);
    }
    cout<<endl;
}

引入:#include<stack>

 四:两种方法实现添加元素

递归实现

void insert_rec(const SET<KEY,VALUE>& x){insert_rec(x,root);}//递归

这是公有函数接口,需要私有函数重载来传入根指针

/*插入*/
template<class KEY,class VALUE>//递归
void bsTree<KEY,VALUE>::insert_rec(const SET<KEY,VALUE>& x,bsNode* &t){
      if(t==NULL) t=new bsNode(x);
      //比较---x.key和t->data.key
      if(x.key<t->data.key) insert_rec(x,t->left);
      else if(x.key>t->data.key) insert_rec(x,t->right);
      else{
        t->data.value=x.value;
        return;
      }
}

注意要传指针的引用:*&,因为我们改变了指针指向

循环实现

template<class KEY,class VALUE>//循环
void bsTree<KEY,VALUE>::insert_loop(const SET<KEY,VALUE>& x){
     if(root==NULL){
        root=new bsNode(x);
        return;
     }
     bsNode* t=root;
     while(1){
        if(x.key<t->data.key){
            if(t->left) t=t->left;
            else{
                t->left=new bsNode(x);
                return;
            }
        }
        else if(x.key>t->data.key){
            if(t->right) t=t->right;
            else{
                t->right=new bsNode(x);
                return;
            }
        }
        else{//x.key==t->data.key
            t->data.value=x.value;
            return;
        }
     }
}

注意体会递归和循环的差异

五:构造函数和析构函数 

构造函数

 bsTree(){root=NULL;}//构造函数

析构函数

 ~bsTree(){ clear(root);}//析构函数

私有函数--clear()

 //清空结点
    void clear(bsNode* &t){
        if(t==NULL) return;
        clear(t->left);
        clear(t->right);
        delete t;
        t=NULL;//根节点置空---写t不写root
    }

注意:不要出现root

 六:两种方法实现查询

由于我们不想讨论结点存在的情况,所以选择用指针,因为没找到会返回NULL

 递归实现

/*find*/
    SET<KEY,VALUE>* find_rec(KEY k){ return find_rec(k,root);}

私有函数传参

//find_rec
    SET<KEY,VALUE>* find_rec(KEY k,bsNode* t){
        if(t==NULL||t->data.key==k) return (SET<KEY,VALUE>*) t;
        else if(k<t->data.key) return find_rec(k,t->left);
        else return find_rec(k,t->right);
    }

把找到了和返回空合并成一种情况

循环实现

SET<KEY,VALUE>* find_loop(KEY k){
        if(root==NULL) return NULL;
        bsNode* t=root;
        while(t&&t->data.key!=k){
            if(k<t->data.key) t=t->left;
            else t=t->right;
        }
        if(t) return (SET<KEY,VALUE>*) t;
        else return NULL;
    }

经典的循环查找方法:!=

注意指针的强制类型转换,因为传入的bsNode*,返回的SET<KEY,VALUE>*

return (SET<KEY,VALUE>*) t

七:两种方法找结点的父结点 

第一种递归

     SET<KEY,VALUE>* parent_rec(const KEY& k){
         if(root==NULL&&root->data.key==k) return NULL;
         return parent_rec(k,root,NULL);
     }

这是公有函数,需要调用私有函数来传参,注意这里用到了两个指针:

一个用来找结点,一个用来记录要找的父结点

 //parent_rec
    SET<KEY,VALUE>* parent_rec(const KEY& k,bsNode* t,bsNode* parent){
        if(t==NULL) return NULL;//没找到
        //比较值
        if(k<t->data.key){
            return parent_rec(k,t->left,t);
        }
        else if(k>t->data.key){
            return parent_rec(k,t->right,t);
        }
        else{
            return ( SET<KEY,VALUE>*)parent;//别忘了强制类型转换
        }
    }

递归寻找的代码更简便,待记录的两个指针直接通过参数传递,注意递归出口

第二种循环 

 /*parent*/
     SET<KEY,VALUE>* parent_loop(const KEY& k){
         if(root==NULL&&root->data.key==k) return NULL;
         bsNode* t=root;
         bsNode* parent=NULL;
         while(t&&t->data.key!=k){
            if(k<t->data.key){
               parent=t;
               t=t->left;
            }
            else{
                parent=t;
                t=t->right;
            }
         }
         if(t) return ( SET<KEY,VALUE>*)parent;
         else return NULL;
     }

注意体会不同

这里一定到注意:跳出循环条件!=

八:递归中序遍历

//中序遍历
     void midPreverse()const{
        cout<<"中序遍历:";
        midPreverse(root);
        cout<<endl;
     }
//中序遍历
    void midPreverse(bsNode* t)const{
       if(t==NULL) return;//递归出口
       midPreverse(t->left);
       cout<<"("<<t->data.key<<","<<t->data.value<<")"<<"   ";
       midPreverse(t->right);
    }

很简单,简单巩固一下

 九:结点的删除---两种方法

 第一种---指针的引用*&

void remove(const KEY& k){ remove(k,root);}

注意私有函数一定传:*&

 //删除--void
    void remove(const KEY& k,bsNode* &t){
            if(t==NULL) return;
            if(k<t->data.key) remove(k,t->left);
            else if(k>t->data.key) remove(k,t->right);
            else{//k==t->data.key  找到了
                if(t->left&&t->right){//有两个孩子
                   //找左孩子最大值
                   bsNode* tmp=t->left;
                   while(tmp->right) tmp=tmp->right;
                   //赋值
                   t->data=tmp->data;
                   //去左子树删去替换值
                   remove(t->data.key,t->left);
                }
                else{
                    bsNode* tmp=t;
                    t=(t->left)?t->left:t->right;
                    delete tmp;
                }
            }
    }

其实思路不难:

1:先去找待删结点

2:如果找到了要看他是叶子结点还是有单孩子还是有两个孩子

  • 如果有两个孩子----找左孩子最大值替代它,然后删了这个结点
  • 由于一个孩子只比无孩子多了一步赋值操作,所以合并

t=(t->left)?t->left:t->right;如果没有就置空了,不影响

 第二种:结点指针的传递

 //传指针
     void remove_point(const KEY& k){
        if(root){
            root=remove_point(k,root);
        }
     }
bsNode* remove_point(const KEY& k,bsNode* t){
        if(t==NULL) return NULL;
        if(k<t->data.key){
            t->left=remove_point(k,t->left);
            return t;
        }
        else if(k>t->data.key){
            t->right=remove_point(k,t->right);
            return t;
        }
        else{//k==t->data.key
            if(!t->left||!t->right){//没有左孩子或右孩子或自己是叶子结点
             bsNode* delNode=t;//赋值
             t=(t->left)?t->left:t->right;
             delete delNode;
             return t;
            }
            else{//有两个孩子
            //找右孩子最小值
             bsNode* delNode=t;
             bsNode* tmp=t->right;
             while(tmp->left) tmp=tmp->left;
            //复制一份给待返回的结点,不然断链
             bsNode* successor=new bsNode(tmp->data,tmp->left,tmp->right);
             //返回
             successor->right=remove_point(tmp->data.key,t->right);
             successor->left=t->left;
             delete delNode;
             return successor;
            }
        }
    }

注意滞后性,有点类似不断改变一个结点的左右指针


版权声明:本文为weixin_47173597原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。