二叉搜索树

从前面讨论折半搜索的性能中可知，如果每次从搜索序列的中间进行搜索，把区间缩小一半，通过有限次迭代，很快就能通近到所要寻找的元素。进一步，如果我们直接输入搜索序列，构造出类似于折半搜索的判定树那样的树形结构，就能实现快速搜索。这种树形结构就是二又搜索树。
二又搜索树（binary search tree）或者是一棵空树，或者是具有下列性质的二又树：
　　（1）每个结点都有一个作为搜索依据的关键码（key），所有结点的关键码互不相同。
　　（2）左子树（如果存在）上所有结点的关键码都小于根结点的关键码。
　　（3）右子树（如果存在）上所有结点的关键码都大于根结点的关键码。
　　（4）左子树和右子树也是二又搜索树。
　　关键码事实上是结点所保存元素中的某个域的值，它能够唯一地表示这个结点。因此，如果对一棵二又搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二又排序树（binary sorting tree）。

基本操作

• 搜索
• 销毁
• 遍历
• 插入
• 移动
• 建立
• 删除
  　在二又搜索树中删除一个结点时，必须将因删除结点而断开的二又链表重新链接起来，同时确保二叉搜索树的性质不会失去。此外，为了保证在执行删除后，树的搜索性能不至于降低，还需要防止重新链接后树的高度不能增加。
  如果想要删除叶结点，只需将其父结点指向它的指针清零，再释放它即可。
  　　如果被删结点右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。
  　　如果被删结点左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。
  　　如果被删结点左、右子树都不空，可以在它的右子树中寻找中序下的第一个结点（关键码最小），用它的值填补到被删结点中，再来处理这个结点的删除问题，这是一个递归处理。例如，在上图中想要删除关键码为78的结点，它的左、右子树都不空。在它的右子树中找中序下的第一个结点，其关键码为81。把它的值填补到被删结点中去，下面的问题就是删除关键码为81的结点了。这个结点左子树为空，用它的右子女（关键码为88）代替它的位置就可以了。

图1

c++代码（测试例子为图1最右边的图）：

/*head file*/
//
// Created by ZC on 2019-08-04.
//

#ifndef ALGORITHM_BINARY_SEARCH_TREE_H
#define ALGORITHM_BINARY_SEARCH_TREE_H
#include<iostream>

template <typename elemType>
struct Node{
   //构造函数
   Node(const elemType val, Node<elemType> *L=nullptr, Node<elemType> *R=nullptr, Node<elemType> *PRE=nullptr):
   value(val),left(L),right(R),pre(PRE){std::cout << "Node1 init" << std::endl;}
   // 另两个构造函数
   Node(): left(nullptr), right(nullptr),pre(nullptr){std::cout << "Node2 init" << std::endl;}
   Node(const Node &);

   elemType value;
   Node<elemType> *left, *right, *pre;
};


template <typename elemType>
Node<elemType>::Node(Node const &rhs)
{
   value = rhs.value;
   left = rhs.left;
   right = rhs.right;
   pre = rhs.pre;
}




template <typename elemType>
class Binary_Search_Tree {
public:
   //构造函数
   Binary_Search_Tree(): root(nullptr), size(0){std::cout << "BST Initialization." << std::endl;}
   //析构
   ~Binary_Search_Tree(){ Destroy(root);}
   // 插入
   bool Insert(elemType value){
       // using nullptr for PRE init.
       bool ans = Insert(value, root, nullptr);
       if (ans)
       {
           SizePlus();
           return true;
       }
       else
           return false;
   }
   // 删除
   bool Remove(elemType value){return Remove(value, root);}
   //搜索
   Node<elemType> * Search(elemType value){return Search(value, root);}
   //遍历
   void PreOrder(){ PreOrder(root);}
   void InOrder(){ InOrder(root);}
   void PostOrder(){ PostOrder(root);}
   void LevelOrder(){ LevelOrder(root);}
   //size值配置
   std::size_t ShowSize(){return size;}
   void SizePlus(){++size;}
   void SizeMinus(){--size;}

protected:
   void Destroy(Node<elemType> *&);
   bool Insert(const elemType &, Node<elemType> *&,Node<elemType> *);
   bool Remove(elemType, Node<elemType> *&);
   Node<elemType> * Search(elemType, Node<elemType> *);
   void PreOrder(Node<elemType> *);
   void InOrder(Node<elemType> *);
   void PostOrder(Node<elemType> *);
   void LevelOrder(Node<elemType> *);

private:
   //根指针
   Node<elemType> *root;
   // 树的大小
   std::size_t size;
};



#endif //ALGORITHM_BINARY_SEARCH_TREE_H

cpp和main测试文件：

//
// Created by ZC on 2019-08-04.
//

#include "Binary_Search_Tree.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;


template <typename elemType>
void Binary_Search_Tree<elemType>::PreOrder(Node<elemType> *ptr)
{
   cout << " PreOrder " << endl;
   if(ptr)
   {
       cout << ptr->value << " ";
       PreOrder(ptr->left);
       PreOrder(ptr->right);
   }
}

template <typename elemType>
void Binary_Search_Tree<elemType>::InOrder(Node<elemType> *ptr)
{
   if(ptr)
   {
       InOrder(ptr->left);
       cout << ptr->value << " ";
       InOrder(ptr->right);
   }
}

template <typename elemType>
void Binary_Search_Tree<elemType>::PostOrder(Node<elemType> *ptr)
{
   if(ptr)
   {
       PostOrder(ptr->left);
       PostOrder(ptr->right);
       cout << ptr->value << " ";
   }
}

template <typename elemType>
void Binary_Search_Tree<elemType>::LevelOrder(Node<elemType> *ptr)
{
   queue<Node<elemType> *> q;
   q.push(ptr);
   while(!q.empty())
   {
       Node<elemType> * tmp = q.front();
       q.pop();
       cout << tmp->value << " ";
       if (tmp->left)
           q.push(tmp->left);
       if (tmp->right)
           q.push(tmp->right);
   }
}

template <typename elemType>
bool Binary_Search_Tree<elemType>::Insert(const elemType &value, Node<elemType> *&ptr,Node<elemType> *toPre)
/*
Params:
   value: insert node value;
   ptr: default BST root pointer;
   toPre: nullptr for init.
*/
{
   // 先检查是否为空
   if (ptr == nullptr)
   {
       ptr = new Node<elemType>(value);
       if(ShowSize()>=1)
       {
           ptr->pre = toPre;
       }
       if (ptr == nullptr)
       {
           std::cout << "Memory allocation failed!" << std::endl;
           exit(1);
       }
       return true;
   }else if (value < ptr->value)
   {
       return Insert(value, ptr->left, ptr);
   }else if ( value > ptr->value)
   {
       return Insert(value, ptr->right, ptr);
   }else
   {

       return false; // value已经在树中
   }
}

//销毁以root为根的二叉树搜索树函数
template <typename elemType>
void Binary_Search_Tree<elemType>::Destroy(Node<elemType> *&root)
{
   cout << "Destroy BST of value: " << root->value << endl;
   if (root == nullptr)
       return;
   if (root->left != nullptr)
   {Destroy(root->left);}
   if (root->right != nullptr)
   {Destroy(root->right);}
   delete root;
   root = nullptr;
}

//删除某一个节点
template <typename elemType>
bool Binary_Search_Tree<elemType>::Remove(elemType value, Node<elemType> *&root)
{
   Node<elemType> * temp = nullptr;
   Node<elemType> * pre = nullptr;
   if(root != nullptr)
   {
       if(root->value < value)
       {
           return Remove(value, root->right);
       }
       else if (root->value > value)
       {
           return Remove(value, root->right);
       }
       else //找到该节点
       {
           if (root->left != nullptr && root->right != nullptr)
           {
               //左右子树非空
               temp = root->right;
               //寻找中序遍历时最小的元素，也就是最左节点位置
               while (temp->left != nullptr)
                   temp = temp->left;
               //用右子树中序下的第一个结点的值填充要删除的结点
               root->value = temp->value;
               //然后再递归删除右子树中节点值已经重用的节点
               Remove(root->value, root->right);
           }
           else if (root->left == nullptr && root->right == nullptr)
           {
               root = nullptr;
           }
           else if (root->left != nullptr && root->right ==nullptr)
           {
               pre = root->pre;
               root = root->left;
               root->pre = pre;
           }
           else
           {
               pre = root->pre;
               root = root->right;
               root->pre = pre;
           }
           delete temp;
           delete pre;
           pre = nullptr;
           temp = nullptr;
           return true;
       }
   }
   else
   {

       return false;
   }
}



// 找到给定的节点
template <typename elemType>
Node<elemType> * Binary_Search_Tree<elemType>::Search(elemType value, Node<elemType> *ptr)
{
   if(ptr!= nullptr)
   {
       if (ptr->value < value)
       {
           return Search(value, ptr->right);
       }
       else if (ptr->value > value)
       {
           return Search(value, ptr->left);
       }
       else
       {
           return ptr;
       }
   }
}


int main()
{
   cout << "------ test node class ------" << endl;
   Node<int> node1;
   cout << "test node1 value is :" << node1.value << endl;
   Node<int> node2(42);
   cout << "test node2 value is :" << node2.value << endl;
   Node<int> node3(node2);
   cout << "test node3 value is :" << node3.value << endl;

   cout << "------ test BST class ------" << endl;
   vector<int> A{53, 17, 78, 9, 45, 65, 94, 23, 81, 88};
   Binary_Search_Tree<int> Tree;
   cout << Tree.ShowSize() << endl;
   for (auto i=0; i<A.size(); ++i) {
       std :: cout << i << "--";
       Tree.Insert(A[i]);
   }

   cout << "In order travel:" << endl;
   Tree.InOrder();
   cout << endl;
   cout << "Level order travel:" << endl;
   Tree.LevelOrder();
   cout << endl;
   cout << "removing value : " << 78 << endl;
   Tree.Remove(78);
   cout << "In order travel:" << endl;
   Tree.InOrder();
   cout << endl;
   cout<< "Tree size is : " << Tree.ShowSize() << endl;
   Node<int> *ptr = Tree.Search(65);
   cout << "pre value of 65 : " << ptr->pre->value << endl;
}

测试结果：

/Users/xxxxxx/CLionProjects/Algorithm/cmake-build-debug/BST
------ test node class ------
Node2 init
test node1 value is :0
Node1 init
test node2 value is :42
test node3 value is :42
------ test BST class ------
BST Initialization.
0
0--Node1 init
1--Node1 init
2--Node1 init
3--Node1 init
4--Node1 init
5--Node1 init
6--Node1 init
7--Node1 init
8--Node1 init
9--Node1 init
In order travel:
9 17 23 45 53 65 78 81 88 94 
Level order travel:
53 17 78 9 45 65 94 23 81 88 
Removing value : 23
In order travel:
9 17 45 53 65 78 81 88 94 
Tree size is : 9
pre value of 65 : 78
Destroy BST of value: 53
Destroy BST of value: 17
Destroy BST of value: 9
Destroy BST of value: 45
Destroy BST of value: 78
Destroy BST of value: 65
Destroy BST of value: 94
Destroy BST of value: 81
Destroy BST of value: 88

Process finished with exit code 0
  

• Refercence :

  • 一些实现清楚的BST

  • 算法导论

  • https://www.cnblogs.com/lonelyxmas/p/4228066.html

  • 多动态图详细讲解二叉搜索树

  • 二叉查找树的基本概念去这里