C++二叉搜刮树 - ToB企服应用市场:ToB评测及商务社交产业平台

template<class k>
// 先来定义二叉搜索树的基本结构，这个就是他们的节点设置！！！
struct bstNode
{
K _key;
bstNode<k>* _left;
bstNode<k>* _right;
bstNode(const k& key)
:_left(nullptr), _right(nullptr), _key(key)
{}
};

复制代码

template<class k>
class bstree
{
typedef bstNode<k> node;
public:
private:
node<k>* _root;
};

复制代码

bool insert(const k key)
{
// zdl:: 此时_root == nullptr
if (!_root)
{
auto x = node(key);
_root->_left = new node(key);
return true;
}
else
{
}
}

复制代码

bool insert(const k& key)
{
if (!_root)
{
_root = new node(key);
return true;
}
else
{
node* cur = _root, *parent = nullptr;
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 (key > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
}
return true;
}

复制代码

void _InOrder(node* root)
{
if (root)
{
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
}

复制代码

#include"BST.h"
using namespace zdl;
int main()
{
int a[] = {2,43,4,5,7,2,4,5,2,9,0};
zdl::bstree<int> bst;
for (auto& x : a) bst.insert(x);
bst.InOrder();
return 0;
}

复制代码

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 *parent = nullptr;
Node *cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
// 0-1个孩⼦的情况
// 删除情况1 2 3均可以直接删除，改变⽗亲对应孩⼦指针指向即可
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
return true;
}
else
{
// 2个孩⼦的情况
// 删除情况4，替换法删除
// 假设这⾥我们取右⼦树的最⼩结点作为替代结点去删除
// 这⾥尤其要注意右⼦树的根就是最⼩情况的情况的处理，对应课件图中删
除8的情况
// ⼀定要把cur给rightMinP，否会报错。
Node *rightMinP = cur;
Node *rightMin = cur->_right;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}

复制代码

template<class K, class V>
struct BSTNode
{
// pair<K, V> _kv;
K _key;
V _value;
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
BSTNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node;
public:
BSTree() = default;
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key, value);
if (parent->_key < 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->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
return true;
}
else
{
Node* rightMinP = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->_key, root->_value);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
private:
Node* _root = nullptr;
};
int main()
{
BSTree<string, string> dict;
//BSTree<string, string> copy = dict;
dict.Insert("left", "左边");
dict.Insert("right", "右边");
dict.Insert("insert", "插⼊");
dict.Insert("string", "字符串");
string str;
while (cin>>str)
{
auto ret = dict.Find(str);
if (ret)
{
cout << "->" << ret->_value << endl;
}
else
{
cout << "⽆此单词，请重新输⼊" << endl;
}
}
return 0;
}
// 测试二
int main()
{
string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠", "苹
果", "⾹蕉", "苹果", "⾹蕉" };
BSTree<string, int> countTree;
for (const auto& str : arr)
{
// 先查找⽔果在不在搜索树中
// 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1>
// 2、在，则查找到的结点中⽔果对应的次数++
//BSTreeNode<string, int>* ret = countTree.Find(str);
auto ret = countTree.Find(str);
if (ret == NULL)
{
countTree.Insert(str, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
return 0;
}

复制代码