大奥 蕾之乱,乡村爱情第六部,博希来近况
二叉查找树（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
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论