二叉搜索树 二叉搜索树源码分享

//枚举类，前中后三种遍历方式
enum ORDER_MODE
{
 ORDER_MODE_PREV = 0,
 ORDER_MODE_MID,
 ORDER_MODE_POST
};

//树节点的结构体
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;
};

//构造方法
template <class T>
BinarySearchTree<T>::BinarySearchTree()
{
 m_root = NULL;
}

//使用另一棵二叉搜索树的构造函数
template <class T>
BinarySearchTree<T>:: BinarySearchTree(const BinarySearchTree& rhs)
{
 m_root = rhs.m_root;
}

//析构函数，释放内存
template <class T>
BinarySearchTree<T>:: ~BinarySearchTree()
{
 makeEmpty();
}

// 判断x元素是否存在
template <class T>
bool  BinarySearchTree<T>::contains(const T& x) const
{
 return contains(x, m_root);
}

//递归调用
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;
}

// 寻找树中的最小值
template <class T>
const T& BinarySearchTree<T>::findMin() const
{
 return findMin(m_root)->element;
}

//递归搜索树中最小值
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMin( BinaryNode<T>* t) const
{
 //二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大
 if (!t)
  return NULL;
 if (t->left == NULL)
  return t;
 else
  return findMin(t->left);
}

// 寻找树中最大值
template <class T>
const T& BinarySearchTree<T>::findMax() const
{
 return findMax(m_root)->element;
}

//递归寻找树中最大值
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMax( BinaryNode<T>* t) const
{
 //二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大
 if (t != NULL)
  while (t->right != NULL)
   t = t->right;
 return t;
}

// 插入元素
template <class T>
void BinarySearchTree<T>:: insert(const T& x)
{
 insert(x, m_root);
}

//递归插入
template <class T>
void BinarySearchTree<T>::insert(const T& x, BinaryNode<T>* &t)
{
 if (t == NULL)
  t = new BinaryNode<T>(x, NULL, NULL);//注意这个指针参数是引用
 else if (x < t->element)
  insert(x, t->left);
 else if (x > t->element)
  insert(x, t->right);
 else
  ;//do nothing
}

//移除元素
template <class T>
void BinarySearchTree<T>::remove(const T& x)
{
 return remove(x, m_root);
}

//递归移除
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;
  }
 }
}

//清空二叉树
template <class T>
void  BinarySearchTree<T>::makeEmpty()
{
 makeEmpty(m_root);
}

//递归清空
template <class T>
void  BinarySearchTree<T>::makeEmpty(BinaryNode<T>* &t)
{
 if (t)
 {
  makeEmpty(t->left);
  makeEmpty(t->right);
  delete t;
 }
 t = NULL;
}

// 打印二叉搜索树
template <class T>
void BinarySearchTree<T>::printTree(ORDER_MODE eOrderMode /*= ORDER_MODE_PREV*/) 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
}

//前序打印
template <class T>
void BinarySearchTree<T>::printTreeInPrev(BinaryNode<T>* t) const
{
 if (t)
 {
  cout << t->element;
  printTreeInPrev(t->left);
  printTreeInPrev(t->right);
 }
}

//中序打印
template <class T>
void BinarySearchTree<T>::printTreeInMid(BinaryNode<T>* t) const
{
 if (t)
 {
  printTreeInPrev(t->left);
  cout << t->element;
  printTreeInPrev(t->right);
 }
}

//后序打印
template <class T>
void BinarySearchTree<T>::printTreeInPost(BinaryNode<T>* t) const
{
 if (t)
 {
  printTreeInPost(t->left);
  printTreeInPost(t->right);
  cout << t->element;
 }
}
```

测试代码
===
```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);
 //测试前中后序打印
 cout <<endl<<"前序："<<endl;
 binaryTree.printTree(ORDER_MODE_PREV);
 cout <<endl<<"中序："<<endl;
 binaryTree.printTree(ORDER_MODE_MID);
 cout <<endl<<"后序："<<endl;
 binaryTree.printTree(ORDER_MODE_POST);
 cout <<endl;

 //测试基本操作
 bool b = binaryTree.contains(1);
 cout<< "是否存在1："<<b<<endl;
 int x = binaryTree.findMin();
 cout << "最小值为："<< x <<endl;
 x = binaryTree.findMax();
 cout << "最大值为："<< x <<endl;
 binaryTree.remove(2);

 cout << "移除元素2之后"<<endl;

 //测试前中后序打印
 cout <<endl<<"前序："<<endl;
 binaryTree.printTree(ORDER_MODE_PREV);
 cout <<endl<<"中序："<<endl;
 binaryTree.printTree(ORDER_MODE_MID);
 cout <<endl<<"后序："<<endl;
 binaryTree.printTree(ORDER_MODE_POST);
 cout <<endl;

 return 0;
}