#include <iostream> using namespace std,

  。

//枚举类，前中后三种遍历方式 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; } 。