数据结构学习-BST二叉查找树

二叉查找树（binary search tree）

是一种树形的存储数据的结构

如图所示，它具有的特点是：

1、具有一个根节点

2、每个节点可能有0、1、2个分支

3、对于某个节点，他的左分支小于自身，自身小于右分支

接下来我们用c++来实现bst的封装

首先我们编写每个节点的类结构，分析可以知道我们每一个节点需要存储一个数据（data），左分支（left指向一个节点），右分支（right指向另一个节点）

因此我们建立

bstnode.h

#ifndef test1_bstnode_h
#define test1_bstnode_h
template <typename t> //这里使用模板类，以放入多种类型的数据，值得一提的是模板类不能讲声明和实现放在两个文件中
class bstnode{
public:
    t data;
    bstnode* left;
    bstnode* right;
    bstnode(){  //默认构造函数
        data = 0;
        left = nullptr;
        right = nullptr;
    }
    bstnode(t val){   //赋值构造函数
        data = val;
        left = nullptr;
        right = nullptr;
    }
};
#endif //test1_bstnode_h

 

接下来我们创建封装了各种方法的树形结构类：

mybst.h

 

这个头文件的设计思路如下：

 

1、先包含bstnode* root作为根节点，在通过根节点的左右指针延伸出整棵树；

 

2、封装了一些会用到的方法：搜索指定值（search）、找出一颗子树中的最小值（treemin）、插入指定值（insert）、删除指定值（delete）、判断是否是叶子结点（isleaf）、判断是否有两个孩子（isnodewithtwochild）、

 

三种遍历方式（前序preordertraversal、中序inordertraversal、后序postodertraversal）、删除所有节点（deleteallnodes）、广度搜索进行周游（bftraversal）、横着画图（graph）、返回根节点（getroot）、判断树空（isempty）

 

默认构造函数、vector为参数的构造函数、数组和长度为参数的构造函数、析构函数。

 

注意在这里为了防止公有方法直接调用私有数据，采用了创建以"__"开头的私有方法，让公有方法先来调用该私有方法，再让私有方法来调用私有数据，以确保其安全性。

 

#ifndef test1_mybst_h
#define test1_mybst_h

#include <iomanip>
#include "bstnode.h"
#include <vector>
#include <deque>
#include <iostream>
using namespace std;

template <typename t>
class mybst{
private:
    bstnode<t> * root = nullptr;
    bstnode<t> * __search(bstnode<t> * root , const t &key){
        if (nullptr == root)
            return nullptr;
        if (key == root->data)
            return root;
        else if (key < root->data)
            return __search(root->left, key);
        else
            return __search(root->right, key);
    } //查找关键字是否存在
    bstnode<t> * __treemin(bstnode<t> * root , bstnode<t> * &parent){
        bstnode<t> * curr = root;
        while(curr->left!= nullptr){
            parent = curr;
            curr = curr->left;
        }
        return  curr;
    } //返回最小节点（一路向左）
    bool __insert(const t &key){
        bstnode<t> * temp = new bstnode<t>(key);
        bstnode<t> * parent = nullptr;
        if(isempty()){
            root=temp;
            return true;
        }
        else{
            bstnode<t> * curr;
            curr = root;
            while(curr){
                parent = curr;
                if(temp->data>curr->data) curr=curr->right;
                else curr = curr->left;
            }
            if(temp->data<parent->data){
                parent->left=temp;
                return true;
            }
            else {
                parent->right = temp;
                return true;
            }
        }
        return false;
    } //插入指定值
    bool __delete(const t &key){
        bool found = false;//存储有没有找到key的变量
        if(isempty()){
            cerr<<"bst为空"<<endl;
            return false;
        }
        bstnode<t> * curr = root;
        bstnode<t> * parrent = nullptr;
        while(curr!= nullptr) {
            if (key == curr->data) {
                found = true;
                break;
            } else {
                parrent = curr;
                if (key < curr->data) curr = curr->left;
                else curr = curr->right;
            }
        }
        if(!found){
            cerr<<"未找到key！"<<endl;
            return false;
        }
        if (parrent == nullptr){//删除根节点
            root = nullptr;
            delete(curr);
            return true;
        }
        /*
         删除的节点有三种可能：
         1、叶子结点
         2、一个孩子的节点
         3、两个孩子的节点
         */
        if (__isleaf(curr)){ //删除的点是叶子结点
            if(parrent->left==curr) parrent->left= nullptr;
            else parrent->right= nullptr;
            delete(curr);
            return true;
        }
        else if(__isnodewithtwochild(curr)){ //是两个孩子的节点
            //以当前右子树中的最小值取代他
            bstnode<t> * parrent = curr;
            bstnode<t> * tmp = __treemin(curr->right,parrent);
            curr->data = tmp->data;
            if(parrent->right==tmp)
                parrent->right== nullptr;
            else parrent->left== nullptr;
            delete(tmp);
            return true;
        }
        else{ //只有一个孩子的节点
            if(curr->left!= nullptr){
                if(curr->left == curr){
                    parrent->left=curr->left;
                    delete(curr);
                    return true;
                }
                else{
                    parrent->right=curr->right;
                    delete(curr);
                    return true;
                }
            }
            if(curr->right!= nullptr){
                if(curr->left == curr){
                    parrent->left=curr->left;
                    delete(curr);
                    return true;
                }
                else{
                    parrent->right=curr->right;
                    delete(curr);
                    return true;
                }
            }
        }
        return false;
    } //删除指定值
    bool __isleaf(bstnode<t> * const & root){
        if(root->left== nullptr && root->right== nullptr) return true;
        else return false;
    }//判断是否是叶子节点
    bool __isnodewithtwochild(bstnode<t> * const & root){
        if(root->left!= nullptr && root->right!= nullptr) return true;
        else return false;
    }//判断是否有两个孩子
    void __inordertraversal(bstnode<t> *root,std::vector<int>&result){
        if(nullptr == root) return;
        __inordertraversal(root->left,result);
        cout<<root->data<<" ";
        result.push_back(root->data);
        __inordertraversal(root->right,result);
    }//中序遍历
    void __preordertraversal(bstnode<t> *root,std::vector<int>&result){
        if(nullptr == root) return;
        cout<<root->data<<" ";
        result.push_back(root->data);
        __inordertraversal(root->left,result);
        __inordertraversal(root->right,result);
    }//前序遍历
    void __postordertraversal(bstnode<t> *root,std::vector<int>&result){
        if(nullptr == root) return;
        __inordertraversal(root->left,result);
        __inordertraversal(root->right,result);
        cout<<root->data<<" ";
        result.push_back(root->data);
    }//后序遍历
    void __deleteallnodes(bstnode<t> *root){
        if (root == nullptr) return;
        __deleteallnodes(root->left);
        __deleteallnodes(root->right);
        __delete(root->data);
    }//删除所有节点
    void __bftraversal(vector<t>&result) {
        deque<bstnode<t> *> tqueue;
        bstnode<t> *pointer = root;
        if (pointer != nullptr) {
            tqueue.push_back(pointer);
        }
        while (!tqueue.empty()) {
            pointer = tqueue.front();
            tqueue.pop_front();
            cout << pointer->data << " ";
            result.push_back(pointer->data);
            if (pointer->left != nullptr) tqueue.push_back(pointer->left);
            if (pointer->right != nullptr) tqueue.push_back(pointer->right);
        }
    } //广度搜索来进行周游
    void __graph(int indent,bstnode<t>* root){
        if(root != 0){
            __graph(indent + 8, root->right);
            cout<<setw(indent)<<" "<<root->data<<endl;
            __graph(indent + 8, root->left);
        }
    } //横着画图的内部接口
    bstnode<t> * __getroot(){
        return root;
    } //返回根节点的内部接口
public:
    mybst(){
        root = nullptr;
    } //默认构造
    mybst(vector<t> arr){
        root = nullptr;
        for(int i =0;i<(int)arr.size();i++){
            __insert(arr[i]);
        }
    }
    mybst(t * arr,int len){
        root = nullptr;
        for(int i =0;i<len;i++){
            __insert(*(arr+i));
        }
    }
    ~mybst(){
        bstnode<t> * curr = root;
        __deleteallnodes(curr);
    }//析构
    bool isempty() const{
        return root == nullptr;
    }//判断树空
    bool search(const t &key){
        bstnode<t> * temp = __search(root, key);
        return (temp == nullptr) ? false : true;
    }//查找关键字是否存在的对外接口
    bool insert(const t &key){
        return __insert(key);
    }//插入节点的外部接口
    bool delete(const t &key){
        return __delete(key);
    }//删除节点的外部接口
    void inordertraversal(vector<t>&result){
        __inordertraversal(root, result);
    }//中序遍历的外部接口
    void preordertraversal(vector<t>&result){
        __preordertraversal(root, result);
    }//前序遍历的外部接口
    void postordertraversal(vector<t>&result){
        __postordertraversal(root, result);
    }//后序遍历的外部接口
    void bftraversal(vector<t>&result){
        return __bftraversal(result);
    } //广度搜索外部接口
    void graph(int indent,bstnode<t>* root){
        return __graph(indent,root);
    } //横着画图的外部接口
    bstnode<t> * getroot(){
        return __getroot();
    } //返回根节点的外部接口
};

#endif //test1_mybst_h

 

最后来进行测试：

main.cpp

#include <iostream>
#include <vector>
#include "mybst.h"
#include "bstnode.h"
using namespace std;
int main() {
    vector<int> in = {23,11,56,5,20,30,89,77,45,50};
    mybst<int> bst(in);
    bst.delete(5);
    bst.insert(4);
    bool found = bst.search(4);
    if(!found)
        cout<<"not found!"<<endl;
    else
        cout<<"found!"<<endl;
    vector<int> result;
    cout<<"inordertravelsal:  ";
    bst.inordertraversal(result);
    cout<<endl<<"preordertravelsal:  ";
    bst.preordertraversal(result);
    cout<<endl<<"postordertraversal:  ";
    bst.postordertraversal(result);
    cout<<endl<<"bftraversal:  ";
    bst.bftraversal(result);
    cout<<endl<<"graph:"<<endl;
    bstnode<int>* pointer = bst.getroot();
    bst.graph(0,pointer);
    return 0;
}

得到图示结果：

参考：https://blog.csdn.net/zhangxiao93/article/details/51444972