算法导论第十二章

二叉查找树： 定义为任何父亲节点数据的大小都大于左子女， 小于右子女。 这样， 中序遍历树即可拿到树的一个排序。插入节点的过程就是建树的过程。 为了使树的结构能更趋于平衡， 在插入前， 将序列随机化是一个非常不错的办法。 主要实现了insert, delete, maxmum, minimum, next, previous方法, 以下是我的实现. 用节点作树的存储结构：其中TreeNode是节点结构。template<class Ty>class BinarySearchTree{public:  typedef Ty                value_type;  typedef Ty*       pointer;  typedef const value_type* const_pointer;  typedef value_type&       reference;  typedef const value_type& const_reference;  typedef size_t            size_type;  typedef ptrdiff_t         difference_type;

 template<class Ty> class TreeNode  { public:  typedef Ty value_type;  TreeNode() : m_parent(0), m_left(0), m_right(0) {}  TreeNode(const Ty& __x) : m_parent(0), m_left(0), m_right(0), m_value(__x) {}

  Ty m_value;  TreeNode<Ty>* m_parent;  TreeNode<Ty>* m_left;  TreeNode<Ty>* m_right;

  TreeNode<Ty>* left() {   return m_left;    }  TreeNode<Ty>* right() {   return m_right;  }  TreeNode<Ty>* parent() {   return m_parent;  }    Ty& value() {   return m_value;  }

  static TreeNode<Ty>* makeNode(const Ty& __x)  {   return new TreeNode<Ty>(__x);  } };

 typedef TreeNode<Ty> node_type;

public:  BinarySearchTree() : m_root(0) {}

 ~BinarySearchTree() {  destroy(); }

 void insert(const value_type& __x) {  node_type* curNode = m_root;  node_type* node = TreeNode<Ty>::makeNode(__x);  if (!m_root)  {   m_root = node;   return;  }  while(curNode)  {   if (m_function(node->value(), curNode->value()))   {    if (curNode->left())    {     curNode = curNode->left();    }    else    {     curNode->m_left = node;     node->m_parent = curNode;     return;    }   }   else   {    if (curNode->right())    {     curNode = curNode->right();    }    else    {     curNode->m_right = node;     node->m_parent = curNode;     return;    }   }  } }

 template<class Function> void traverse(Function f) {  traverse(m_root, f); }

 template<class Function> void traverse(node_type* root, Function f) {  if (!root)   return;  traverse(root->left(), f);  traverse(root->right(), f);  f(root->value()); }

 value_type minimum() {  node_type* node = m_root;  if (!node)  {   throw std::out_of_range("no minimum");  }  while(node->left())  {   node = node->left();  }  return node->value(); }

 value_type maxmum() {  node_type* node = m_root;  if (!node)  {   throw std::out_of_range("no minimum");  }  while(node->right())  {   node = node->right();  }  return node->value(); }

 node_type* next(node_type* node) {  assert(node);  if (!node) return 0;  if (node->right())  {   return minimum(node->right());  }  while(node->parent() && node->parent()->right() == node)  {   node = node->parent();  }  return node->parent(); }

 node_type* privious(node_type* node) {  assert(node);  if (!node) return 0;  if (node->left())  {   return maxmum(node->left());  }  while(node->parent() && node->parent()->left() == node)  {   node = node->parent();  }  return node->parent(); }

 node_type* find(const value_type& __x) {  node_type* node = m_root;  while(node)  {   if (node->value() == __x)   {    return node;   }   if (m_function(node->value(), __x))   {    node = node->right();   }   else   {    node = node->left();   }  }  return 0; }  void erase(const value_type& __x) {  node_type* node = find(__x);  if (!node)  {   return;  }  if (!node->left() || !node->right())  {     }  else  {   node_type* nextNode = next(node);   std::swap(node->m_value, nextNode->m_value);   node = nextNode;  }  node_type** parent;  if (!node->parent())  {   parent = &m_root;  }  else  {   if (node->parent()->left() == node)   {    parent = &(node->m_parent->m_left);   }   else   {    parent = &(node->m_parent->m_right);   }  }

  if (node->left())  {   *parent = node->left();   node->m_left->m_parent = node->parent() ? node->parent() : 0;  }  else  {   *parent = node->right();   if (node->right())    node->m_right->m_parent = node->parent() ? node->parent() : 0;  }  delete node; }

private: node_type* minimum(node_type* node) {  assert(node);  while(node->left())  {   node = node->left();  }  return node; }

 node_type* maxmum(node_type* node) {  assert(node);  while(node->right())  {   node = node->right();  }  return node; }

private: BinarySearchTree(const BinarySearchTree&); BinarySearchTree& operator= (const BinarySearchTree&); void destroy() {  removeTree(m_root);  m_root = 0; }

 void removeTree(node_type* root) {  if (root)  {   removeTree(root->left());   removeTree(root->right());   delete root;  } }

 std::less<Ty> m_function; node_type* m_root;};