二叉搜刮樹源碼分享

二叉搜刮樹源碼分享。本站提示廣大學習愛好者：（二叉搜刮樹源碼分享）文章只能為提供參考，不一定能成為您想要的結果。以下是二叉搜刮樹源碼分享正文

#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;
}