一、key模型搜索二叉树的模拟实现
1.非递归实现
#pragma once
#include<iostream>
using namespace std;
template<class K>
struct BSTNode //binary search tree
{
BSTNode* _left;
BSTNode* _right;
K _key;
BSTNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
bool Insert(const K& key)
{
if (_root == NULL)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key); //找到位置后进行链接
if (cur->_key > parent->_key) //判定插在左或者右
parent->_right = cur;
else
parent->_left = cur;
return true;
}
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
else
return true;
}
return false;
}
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
//由于要用双指针,所以不能直接用Find来执行这一部分
while (cur!=nullptr)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else //找到了
{
//1.无左无右
//2.都有
if(cur->_left == nullptr) //无左,和无左无右
{
if (cur == _root) //如果要删除的就是根
{
_root = cur -> _right;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_right;
else
parent->_left = cur->_right;
}
delete cur;
return true;
}
else if (cur->_right == nullptr) //无右
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
}
delete cur;
return true;
}
else//找到左树最右叶,或者右树最左叶,替换cur
{
Node* rightmin = cur->_right;
Node* rightminparent = cur;
while (rightmin->_left != nullptr)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
cur->_key = rightmin->_key;
//转换为删除rightmin(rightmin左为空,删除他的右)
if(rightmin == rightminparent->_left) //如果进入了循环
rightminparent->_left = rightmin->_right;
else
rightminparent->_right = rightmin->_right;
delete rightmin;
return true;
}
}
}
return false;
}
void _InOrder(Node* root) //中序打印数据
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
void InOrder() //使中序打印函数使用更方便
{
_InOrder(_root);
cout << endl;
}
private:
Node* _root = nullptr;
};
2.递归实现
#pragma once
#include<iostream>
#include<string>
using namespace std;
template<class K>
struct BSTreeNode
{
BSTreeNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newroot = new Node(root->_key);
newroot->_left = Copy(root->_left);
newroot->_right = Copy(root->_right);
return newroot;
}
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
void Destory(Node* root)
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
~BSTree()
{
Destory(_root);
_root = nullptr;
}
void _Print(Node* root)
{
if (root == nullptr)
return;
_Print(root->_left);
cout << root->_key << " ";
_Print(root->_right);
}
void Print()
{
_Print(_root);
cout << endl;
}
bool _InsertR(Node* root, const K& k, Node*& parent)
{
Node* cur = root;
if (cur != nullptr)
{
if (cur->_key > k)
{
parent = cur;
_InsertR(cur->_left, k, parent);
}
else if (cur->_key < k)
{
parent = cur;
_InsertR(cur->_right, k, parent);
}
}
else
{
cur = new Node(k);
if (parent->_key > k)
parent->_left = cur;
else
parent->_right = cur;
return true;
}
if (root->_key == k)
return false;
}
bool Insert(const K& k)
{
if (_root == nullptr)
{
_root = new Node(k);
return true;
}
Node* parent = nullptr;
return _InsertR(_root, k, parent);
}
//进阶思路----引用的使用
bool _InsertR(Node*& root, const K& k)
{
if (root == nullptr)
{
root = new Node(k); //这里要修改指针指向的内容,所以要传指针的指针类型的参数(*& || **)
return true;
}
if (root->_key < k)
return _InsertR(root->_right, k);
else if (root->_key > k)
return _InsertR(root->_left, k);
else
return false;
}
bool Insert(const K& k)
{
return _InsertR(_root, k);
}
bool _Find(Node* root, const K& k)
{
if (root == nullptr)
return false;
if (root->_key > k)
_Find(root->_left, k);
else if (root->_key < k)
_Find(root->_left, k);
else
return true;
}
bool Find(const K& k)
{
return _Find(_root, k);
}
bool _Erase(Node*& root, const K& k)
{
if (root == nullptr)
return false;
if (root->_key > k)
_Erase(root->_left, k);
else if (root->_key < k)
_Erase(root->_right, k);
else
{
Node* del = root; //root的key对应k
if (root->_left == nullptr)
root = root->_right;
else if (root->_right == nullptr)
root = root->_left;
else
{
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
swap(root->_key, minRight->_key);
return _Erase(root->_right, k);
}
delete del;
return true;
}
}
bool Erase(const K& k)
{
return _Erase(_root, k);
}
private:
Node* _root = nullptr;
};
二、Key/Value 模型搜索二叉树的模拟实现
#pragma once
#include<iostream>
#include<string>
using namespace std;
template<class K,class V>
struct BSTNode //binary search tree
{
BSTNode* _left;
BSTNode* _right;
K _key;
V _value;
BSTNode(const K& key,const V& value)
: _left(nullptr)
, _right(nullptr)
, _key(key)
, _value(value)
{}
};
template<class K,class V>
class BSTree
{
typedef BSTNode<K,V> Node;
public:
bool Insert(const K& key,const V& value) //插入数据
{
if (_root == NULL)
{
_root = new Node(key,value); //new 自动调用构造函数
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) //cur为空时结束
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key,value); //找到位置后进行链接
if (cur->_key > parent->_key) //判定插在左或者右
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
else
return cur;
}
return nullptr;
}
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
//由于要用双指针,所以不能直接用Find来执行这一部分
while (cur != nullptr)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else //找到了
{
//1.无左无右
//2.都有
if (cur->_left == nullptr) //无左,和无左无右
{
if (cur == _root) //如果要删除的就是根
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_right;
else
parent->_left = cur->_right;
}
delete cur;
return true;
}
else if (cur->_right == nullptr) //无右
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
}
delete cur;
return true;
}
else//找到左树最右叶,或者右树最左叶,替换cur
{
Node* rightmin = cur->_right;
Node* rightminparent = cur;
while (rightmin->_left != nullptr)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
cur->_key = rightmin->_key;
//转换为删除rightmin(rightmin左为空,删除他的右)
if (rightmin == rightminparent->_left) //如果进入while循环
rightminparent->_left = rightmin->_right;
else
rightminparent->_right = rightmin->_right;
delete rightmin;
return true;
}
}
}
return false;
}
void _InOrder(Node* root) //中序打印数据
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
void InOrder() //使中序打印函数使用更方便
{
_InOrder(_root);
cout << endl;
}
private:
Node* _root = nullptr;
};
void test_BST3() //key/value模型可以做简单的英译汉
{
BSTree<string, string> dict;
dict.Insert("sort", "排序");
dict.Insert("int", "整形");
dict.Insert("computer", "计算机");
dict.Insert("mouse", "老鼠");
string eng;
while (cin >> eng)
{
BSTNode<string, string>* ret = dict.Find(eng);
if (ret)
cout << ret->_value << endl;
else
cout << "Not Found" << endl;
}
}
void test_BST4()//也可以做到统计数据出现次数
{
string Arr[] = { "hehe","haha", "haha", "hehe", "hehe"};
BSTree<string, int> CountV;
for (auto str : Arr)
{
BSTNode<string, int>* ret = CountV.Find(str);
if (ret)
ret->_value++;
else
CountV.Insert(str, 1);
}
CountV.InOrder();
}