c/c++语言开发共享数据结构学习-BST二叉查找树

#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

#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

#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; }