#include <iostream>
using namespace std;
//Enumeration class, before the last three ways of traversal
enum ORDER_MODE
{
ORDER_MODE_PREV = 0,
ORDER_MODE_MID,
ORDER_MODE_POST
};
//The structure of a tree node
template <class T>
struct BinaryNode
{
T element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const T& theElement,
BinaryNode *lt,
BinaryNode *rt):
element(theElement),
left(lt),
right(rt)
{
}
};
template <class T>
class BinarySearchTree
{
private:
BinaryNode<T> *m_root;
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree& rhs);
~BinarySearchTree();
const T& findMin() const;
const T& findMax() const;
bool contains(const T& x) const;
void printTree(ORDER_MODE eOrderMode = ORDER_MODE_PREV) const;
void makeEmpty();
void insert(const T& x);
void remove(const T& x);
private:
void insert(const T& x, BinaryNode<T>* &t) ;
void remove(const T& x, BinaryNode<T>* &t) ;
BinaryNode<T>* findMin( BinaryNode<T>* t) const;
BinaryNode<T>* findMax( BinaryNode<T>* t) const;
bool contains(const T& x, const BinaryNode<T>* t) const;
void makeEmpty(BinaryNode<T>* &t);
void printTreeInPrev(BinaryNode<T>* t) const;
void printTreeInMid(BinaryNode<T>* t)const;
void printTreeInPost(BinaryNode<T>* t)const;
};
//A constructor
template <class T>
BinarySearchTree<T>::BinarySearchTree()
{
m_root = NULL;
}
//Use the constructor of another binary search tree
template <class T>
BinarySearchTree<T>:: BinarySearchTree(const BinarySearchTree& rhs)
{
m_root = rhs.m_root;
}
//Destructor, freeing memory
template <class T>
BinarySearchTree<T>:: ~BinarySearchTree()
{
makeEmpty();
}
//To determine whether or not the x element exists
template <class T>
bool BinarySearchTree<T>::contains(const T& x) const
{
return contains(x, m_root);
}
//Recursive calls
template <class T>
bool BinarySearchTree<T>::contains(const T& x, const BinaryNode<T>* t) const
{
if (!t)
return false;
else if (x < t->element)
return contains(x, t->left);
else if (x > t->element)
return contains(x, t->right);
else
return true;
}
//Find the minimum in the tree
template <class T>
const T& BinarySearchTree<T>::findMin() const
{
return findMin(m_root)->element;
}
//Minimum in a recursive search tree
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMin( BinaryNode<T>* t) const
{
//One of the characteristics of binary trees is that the value of the left cotyledon is smaller than that of the root node, and the value of the right cotyledon is larger than that of the root node
if (!t)
return NULL;
if (t->left == NULL)
return t;
else
return findMin(t->left);
}
//Find the maximum value in the tree
template <class T>
const T& BinarySearchTree<T>::findMax() const
{
return findMax(m_root)->element;
}
//Recursively find the maximum value in the tree
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMax( BinaryNode<T>* t) const
{
//One of the characteristics of binary trees is that the value of the left cotyledon is smaller than that of the root node, and the value of the right cotyledon is larger than that of the root node
if (t != NULL)
while (t->right != NULL)
t = t->right;
return t;
}
//Insert elements
template <class T>
void BinarySearchTree<T>:: insert(const T& x)
{
insert(x, m_root);
}
//Recursive insert
template <class T>
void BinarySearchTree<T>::insert(const T& x, BinaryNode<T>* &t)
{
if (t == NULL)
t = new BinaryNode<T>(x, NULL, NULL);//Note that this pointer parameter is a reference
else if (x < t->element)
insert(x, t->left);
else if (x > t->element)
insert(x, t->right);
else
;//do nothing
}
//Remove elements
template <class T>
void BinarySearchTree<T>::remove(const T& x)
{
return remove(x, m_root);
}
//Recursive removal
template <class T>
void BinarySearchTree<T>::remove(const T& x, BinaryNode<T>* &t)
{
if (t == NULL)
return;
if (x < t->element)
remove(x, t->left);
else if (x > t->element)
remove (x, t->right);
else // now ==
{
if (t->left != NULL &&
t->right != NULL)//two child
{
t->element = findMin(t->right)->element;
remove(t->element, t->right);
}
else
{
BinaryNode<T> *oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
}
}
//Empty the binary tree
template <class T>
void BinarySearchTree<T>::makeEmpty()
{
makeEmpty(m_root);
}
//Recursion to empty
template <class T>
void BinarySearchTree<T>::makeEmpty(BinaryNode<T>* &t)
{
if (t)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
//Print binary search trees
template <class T>
void BinarySearchTree<T>::printTree(ORDER_MODE eOrderMode ) const
{
if (ORDER_MODE_PREV == eOrderMode)
printTreeInPrev(m_root);
else if (ORDER_MODE_MID == eOrderMode)
printTreeInMid(m_root);
else if (ORDER_MODE_POST == eOrderMode)
printTreeInPost(m_root);
else
;//do nothing
}
//Before the order
template <class T>
void BinarySearchTree<T>::printTreeInPrev(BinaryNode<T>* t) const
{
if (t)
{
cout << t->element;
printTreeInPrev(t->left);
printTreeInPrev(t->right);
}
}
//In order to print
template <class T>
void BinarySearchTree<T>::printTreeInMid(BinaryNode<T>* t) const
{
if (t)
{
printTreeInPrev(t->left);
cout << t->element;
printTreeInPrev(t->right);
}
}
//After the order
template <class T>
void BinarySearchTree<T>::printTreeInPost(BinaryNode<T>* t) const
{
if (t)
{
printTreeInPost(t->left);
printTreeInPost(t->right);
cout << t->element;
}
}
```
The test code
===
```C++
#include "BinarySearchTree.h"
int main()
{
BinarySearchTree<int> binaryTree;
binaryTree.insert(5);
binaryTree.insert(1);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(6);
binaryTree.insert(8);
// In the test before After the order
cout <<endl<<" Before the order: "<<endl;
binaryTree.printTree(ORDER_MODE_PREV);
cout <<endl<<" In the order: "<<endl;
binaryTree.printTree(ORDER_MODE_MID);
cout <<endl<<" After the sequence: "<<endl;
binaryTree.printTree(ORDER_MODE_POST);
cout <<endl;
//Test basic operations
bool b = binaryTree.contains(1);
cout<< " If there is a 1 : "<<b<<endl;
int x = binaryTree.findMin();
cout << " The minimum value is: "<< x <<endl;
x = binaryTree.findMax();
cout << " The maximum value is: "<< x <<endl;
binaryTree.remove(2);
cout << "Remove elements2 after "<<endl;
// In the test before After the order
cout <<endl<<" Before the order: "<<endl;
binaryTree.printTree(ORDER_MODE_PREV);
cout <<endl<<" In the order: "<<endl;
binaryTree.printTree(ORDER_MODE_MID);
cout <<endl<<" After the sequence: "<<endl;
binaryTree.printTree(ORDER_MODE_POST);
cout <<endl;
return 0;
}