二叉查找树(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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605903.html