[C++] Search binary tree

Article directory

• 1. Simulation implementation of key model search binary tree
• • 1. Non-recursive implementation
  • 2. Recursive implementation
• 2. Simulation implementation of Key/Value model search binary tree

1. Simulation implementation of key model search binary tree

1. Non-recursive implementation

#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 & amp; 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); // link after finding the location
if (cur->_key > parent->_key) // determine whether to insert on the left or right
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 & amp; key)
{<!-- -->
Node* cur = _root;
Node* parent = nullptr;
//Since double pointers are used, you cannot directly use Find to execute this part
while (cur!=nullptr)
{<!-- -->
if (cur->_key > key)
{<!-- -->
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{<!-- -->
parent = cur;
cur = cur->_right;
}
else // found
{<!-- -->
//1. No left and no right
//2. Both
if(cur->_left == nullptr) //no left, and no left and no right
{<!-- -->
if (cur == _root) //If the root is to be deleted
{<!-- -->
_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) //no right
{<!-- -->
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//Find the rightmost leaf of the left tree, or the leftmost leaf of the right tree, replace cur
{<!-- -->
Node* rightmin = cur->_right;
Node* rightminparent = cur;
while (rightmin->_left != nullptr)
{<!-- -->
rightminparent = rightmin;
rightmin = rightmin->_left;
}
cur->_key = rightmin->_key;

//Convert to delete rightmin (rightmin left is empty, delete his right)
if(rightmin == rightminparent->_left) //If you enter the loop
rightminparent->_left = rightmin->_right;
else
rightminparent->_right = rightmin->_right;
delete rightmin;
return true;
}
}
}
return false;
}

void _InOrder(Node* root) //Inorder print data
{<!-- -->
if (root == nullptr)
return;

_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}

void InOrder() //Make the inorder printing function more convenient to use
{<!-- -->
_InOrder(_root);
cout << endl;
}
private:
Node* _root = nullptr;
};

2. Recursive implementation

#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);
}
\t


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 & amp; k, Node* & amp; 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);
}



//Advanced ideas - the use of references
bool _InsertR(Node* & amp; root, const K & amp; k)
{<!-- -->
if (root == nullptr)
{<!-- -->
root = new Node(k); //The content pointed to by the pointer is to be modified here, so the parameter of the pointer type of the pointer must be passed (* & amp; || **)
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* & amp; root, const K & amp; 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's key corresponds to 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;
};

2. Simulation implementation of Key/Value model search binary tree

#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 & amp; key, const V & amp; 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 & amp; key, const V & amp; value) //insert data
{<!-- -->
if (_root == NULL)
{<!-- -->
_root = new Node(key,value); //new automatically calls the constructor
return true;
}

Node* parent = nullptr;
Node* cur = _root;
while (cur) //end when cur is empty
{<!-- -->
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); // link after finding the location
if (cur->_key > parent->_key) // determine whether to insert on the left or right
{<!-- -->
parent->_right = cur;
}
else
{<!-- -->
parent->_left = cur;
}
return true;
}

Node* Find(const K & amp; 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 & amp; key)
{<!-- -->
Node* cur = _root;
Node* parent = nullptr;
//Since double pointers are used, you cannot directly use Find to execute this part
while (cur != nullptr)
{<!-- -->
if (cur->_key > key)
{<!-- -->
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{<!-- -->
parent = cur;
cur = cur->_right;
}
else // found
{<!-- -->
//1. No left and no right
//2. Both
if (cur->_left == nullptr) //no left, and no left and no right
{<!-- -->
if (cur == _root) //If the root is to be deleted
{<!-- -->
_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) //no right
{<!-- -->
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//Find the rightmost leaf of the left tree, or the leftmost leaf of the right tree, replace cur
{<!-- -->
Node* rightmin = cur->_right;
Node* rightminparent = cur;
while (rightmin->_left != nullptr)
{<!-- -->
rightminparent = rightmin;
rightmin = rightmin->_left;
}

cur->_key = rightmin->_key;

//Convert to delete rightmin (rightmin left is empty, delete his right)
if (rightmin == rightminparent->_left) //if entering the while loop
rightminparent->_left = rightmin->_right;
else
rightminparent->_right = rightmin->_right;
delete rightmin;
return true;
}
}
}
return false;
}

void _InOrder(Node* root) //Inorder print data
{<!-- -->
if (root == nullptr)
return;

_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}

void InOrder() //Make the inorder printing function more convenient to use
{<!-- -->
_InOrder(_root);
cout << endl;
}

private:
Node* _root = nullptr;
};


void test_BST3() //key/value model can do simple English-Chinese translation
{<!-- -->
BSTree<string, string> dict;
dict.Insert("sort", "sort");
dict.Insert("int", "integer");
dict.Insert("computer", "computer");
dict.Insert("mouse", "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()//Can also do statistics on the number of occurrences of data
{<!-- -->
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();
}