【数据结构】二叉搜索树

● 二叉搜索树满足以下条件的二叉树：
1、每个节点都有一个作为搜索依据的关键码（key），所有节点的关键码互不相同。
2、左子树上所有节点的关键码（key）都小于根节点的关键码（key）。
3、右子树上所有节点的关键码（key）都大于根节点的关键码（key）。
4、左右子树都是二叉搜索树。

● 二叉搜索树的插入过程如下：

1、若当前的二叉搜索树为空，则插入的元素为根节点。

2、若插入的元素值小于根节点值，则将元素插入到左子树中。

3、若插入的元素值大于根节点值，则将元素插入到右子树中。

4、找到插入的位置和插入的位置的父结点，进行链接。

template<class T>
void BSTree<T>::Insert(const T& key, const T& value)//非递归算法进行插入
{
 if (_root == NULL)
 {
  _root = new Node(key, value);
  return;
 }
 Node* prev = NULL;
 Node* cur = _root;
 while (cur)//在树中找到插入的位置
 {
  if (key < cur->_key)
  {
   prev = cur;
   cur = cur->_left;
  }
  else if (key > cur->_key)
  {
   prev = cur;
   cur = cur->_right;
  }
 }
 cur = new Node(key, value);//建立新结点，并判断具体位置进行链接
 if (prev->_key > cur->_key)
 {
  prev->_left = cur;
 }
 if (prev->_key < cur->_key)
 {
  prev->_right = cur;
 }
}

template<class T>
void BSTree<T>::Insert_R(const T& key, const T& value)//递归算法进行插入
{
 _insert_r(_root, key, value);
}
template<class T>
void BSTree<T>::_insert_r(Node*& root, const T& key, const T& value)//递归
{
 if (root == NULL)//root为空时，开辟新结点
 {
  root = new Node(key, value);
  return;
 }
 Node* cur = root;
 if (key < cur->_key)
  _insert_r(cur->_left, key, value);
 if (key > cur->_key)
  _insert_r(cur->_right, key, value);
}

● 二叉搜索树的查找过程如下：

1、若当前的二叉搜索树为空，则结束函数。

2、若查找的元素值小于根节点值，则在当前结点的左子树中查找。

3、若查找的元素值大于根节点值，则在当前结点的右子树中查找。

template<class T>
BSTNode<T>* BSTree<T>::Find(const T& key)//非递归算法进行查找
{
 Node* cur = _root;
 while (cur)
 {
  if (key < cur->_key)
  {
   cur = cur->_left;
  }
  else if (key > cur->_key)
  {
   cur = cur->_right;
  }
  else
  {
   return cur;
  }
 }
 return NULL;
}

template<class T>
BSTNode<T>* BSTree<T>::Find_R(const T& key)//递归
{
 return _find_r(_root, key);
}
template<class T>
BSTNode<T>* BSTree<T>::_find_r(Node*& root, const T& key)//递归算法进行查找
{
 if (root == NULL)//root为空时为没找到
 {
  return NULL;
 }
 if (key < root->_key)
  return _find_r(root->_left, key);
 else if (key > root->_key)
  return _find_r(root->_right, key);
 else
  return root;
}

● 二叉搜索树的删除，分两种情况进行处理：

1、找到要删除的结点cur和cur的父亲结点prev。

2、情况一：cur只有一个子树或没有子树。首先考虑删除的结点为根结点时，直接_root指向它的子树；

再考虑cur的左为空、右为空还是左右都为空，进行删除，链接。

3、情况二：cur左右子树都不为空。首先找到cur右子树的最左下结点del，然后进行交换，通过替换法删除del，并使prev的指向置空。

template<class T>
void BSTree<T>::Remove(const T& key)//非递归算法进行删除
{
 if (_root == NULL)
 {
  return;
 }
 Node* prev = NULL;
 Node* cur = _root;
 while (cur)//找到要删除的结点cur
 {
  if (key < cur->_key)
  {
   prev = cur;
   cur = cur->_left;
  }
  else if (key > cur->_key)
  {
   prev = cur;
   cur = cur->_right;
  }
  else
   break;
 }
 //情况一：cur只有一个孩子或没有孩子，注意考虑cur为根结点时,prev=NULL
 if (cur->_left == NULL || cur->_right == NULL)
 {
  if (cur->_left == NULL)//cur只有右孩子
  {
   if (prev == NULL)//cur为根结点时
    _root = cur->_right;
   else if (prev->_left == cur)
    prev->_left = cur->_right;
   else
    prev->_right = cur->_right;
  }
  else if (cur->_right == NULL)//cur只有左孩子
  {
   if (prev == NULL)//cur为根结点时
    _root = cur->_left;
   else if (prev->_left == cur)
    prev->_left = cur->_left;
   else
    prev->_right = cur->_left;
  }
  //删除cur并置空，包含了cur的左右为空的情况
  delete cur;
  cur = NULL;
 }
 //情况二：cur有左右子树,替换法删除
 else
 {
  //先找到cur结点右子树的最左下结点del
  Node* del = cur;
  prev = del;
  del = del->_right;
  while (del->_left)
  {
   prev = del;
   del = del->_left;
  }
  //替换法，删除结点del,注意使prev的指向置空
  swap(cur->_key, del->_key);
  swap(cur->_value, del->_value);
  if (prev->_left == del)
   prev->_left = NULL;
  else if (prev->_right == del)
   prev->_right = NULL;
  delete del;
  del = NULL;
 }
}

template<class T>
void BSTree<T>::Remove_R(const T& key)//递归算法进行删除
{
 _remove_r(_root, key);
}
template<class T>
void BSTree<T>::_remove_r(Node*& root, const T& key)//递归
{
 if (_root == NULL)
 {
  return;
 }
 if (key < root->_key)
  _remove_r(root->_left, key);
 else if (key > root->_key)
  _remove_r(root->_right, key);
 else
 {
  //情况一：只有一个子树或没有,直接使root重新赋值
  if (root->_left == NULL || root->_right == NULL)
  {
   Node* del = root;
   if (root->_left == NULL)
    root = root->_right;
   else if (root->_right == NULL)
    root = root->_left;
   else
    root = NULL;
   delete del;
   del = NULL;
  }
  else//情况二：左右子树都不为空
  {
   Node* cur = root->_right;//root右子树最左下结点，交换两个结点的值
   while (cur->_left)
   {
    cur = cur->_left;
   }
   swap(root->_key, cur->_key);
   swap(root->_value, cur->_value);
   _remove_r(root->_right, key);//在root的右子树上删除key，转换成情况一中左子树一定为空
  }
 }
}