1.二叉搜索树的概念

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

1. 若左子树不空，则左子树上所有节点的值均小于它的根节点的值。
2. 若右子树不空，则右子树上所有节点的值均大于它的根节点的值。
3. 左、右子树也分别为二叉排序树。

二叉搜索树的中序序列必定有序。这一性质十分重要。如图是一个二叉搜索树：（百度百科）

注意观察，每个节点的左孩子小于自己，右孩子大于自己。
二叉搜索树与平衡二叉树概念上无直接联系，但是平衡二叉搜索树性能最好。

2.二叉搜索树的基本操作

• 查值
  二叉搜索树的查值操作与二分类似，先查根节点，若根节点值大于要查值，则对左子树指向上述操作，否则对右子树执行，直到查到。时间复杂度O(logn)级别。见伪代码：

  查找（查找值，树）
  {
  如果查找值等于根节点的值
      返回查到的节点；
  如果查找值小于根节点的值
      查找（查找值，左子树）；
  如果查找值大于根节点的值
      查找（查找值，右子树）；
  返回空；
  }

• 插入值
  首先将要插入的值与根节点比较，若比根节点小，则插入左子树，重复这个操作，若比根节点大，则插入右子树，重复这个操作，这样讲比较抽象，具体见伪代码：

  插入（插入值，树）
  {
  如果插入值小于树的根节点的值
      插入（插入值，左子树）；
  如果插入值大于等于树的根节点的值
      插入（插入值，右子树）；
  如果树不存在
      申请新节点；
  }

• 删除值
  这个相对复杂，但是只要把握好“二叉搜索树的中序序列必定有序”这个性质，其实也简单的批爆。
  首先，如果要删的节点是叶子节点，那么久直接删。
  如果要删的节点有左子树，将左子树下最靠右的节点值赋予想要删除的节点。
  如果要删的节点有右子树，将右子树下最靠左的节点值赋予想要删除的节点。
  具体见伪代码：

  删除（删除值，树）
  {
  删除节点 = 查找（删除值，树）；
  如果删除节点是叶子节点
      删除删除节点；
  如果删除节点有左子树{
      删除节点值 = 左子树最右值；
      删除（左子树最右值，左子树）；
  }
  如果删除节点有右子树{
      删除节点值 = 右子树最左值；
      删除（右子树最左值，右子树）；
  }
  }

  也就是说，删除一个值时，其在中序序列中的相邻值会替代它，这样能保证其中序序列严格有序。

3.二叉搜索树的实现

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define M 1000000007
using namespace std;
typedef long long LL;

struct node //节点结构体
{
    int data; //数据
    node* l_child; //左孩子 
    node* r_child;//右孩子
};

class BSTree
{
public:
    BSTree(); //构造
    ~BSTree(); //析构
    void create(int n); //创建，n为数据量
    void insert(int x); //插入值
    void del(int x); //删值
    void print(); //打印序列
    node* srh(int x); //查找
private:
    node* tree;
};

BSTree::BSTree()
{
    tree = NULL;
}

void tree_del(node* tree)
{
    if(tree == NULL)
        return;
    tree_del(tree->l_child);
    tree_del(tree->r_child);
    delete tree;
}

BSTree::~BSTree()
{
    tree_del(tree);
}

node* new_node(int x) //创建新的节点
{
    // cout << "new_node" << endl;
    node* new_n = new node;
    new_n->data = x;
    new_n->l_child = NULL;
    new_n->r_child = NULL;
    return new_n;
}

node* tree_ins(node* tree,int x)
{
    if(tree == NULL)
        tree = new_node(x);
    else if(x >= tree->data)
        tree->r_child = tree_ins(tree->r_child,x);
    else
        tree->l_child = tree_ins(tree->l_child,x);
}

void BSTree::insert(int x)
{
    tree = tree_ins(tree,x);
}

void BSTree::create(int n)
{
    for(int i = 0;i < n;++i)
    {
        int tmp;
        cout << "Input the " << i + 1 << "th number: ";
        cin >> tmp;
        insert(tmp);
    }
}

node* tree_srh(node* tree,int x)
{
    if(tree == NULL)
    {
        // cout << "tree == NULL" << endl;
        return NULL;
    }
    if(x == tree->data)
        return tree;
    if(x > tree->data)
    {
        // cout << "x > tree->data" << endl;
        return tree_srh(tree->r_child,x);
    }
    if(x < tree->data)
    {
        // cout << "x < tree->data" << endl;
        return tree_srh(tree->l_child,x);
    }
    return NULL;
}

node* BSTree::srh(int x)
{
    return tree_srh(tree,x);
}

node* tree_del(node* tree,int x)
{
    node* p;
    //以下是定位操作
    if(tree == NULL)
    {
        cout << "tar == NULL" << endl;
        return NULL;
    }
    if(tree->data > x)
        tree->l_child = tree_del(tree->l_child,x);
    else if(tree->data < x)
        tree->r_child = tree_del(tree->r_child,x);
    //定位到之后，开始删除
    else
    {
        if(tree->l_child == NULL && tree->r_child == NULL)
        {
            // cout << tree->data << endl;
            delete tree;
            tree = NULL;
        }
        else if(tree->l_child != NULL)
        {
            // cout << "tree->l_child != NULL " << tree->data << endl;
            for(p = tree->l_child;p->r_child;p = p->r_child); //找出左子树最右值
            tree->data = p->data;
            tree->l_child = tree_del(tree->l_child,tree->data);
        }
        else if(tree->r_child != NULL)
        {
            // cout << "tree->r_child != NULL " << tree->data << endl;
            for(p = tree->r_child;p->l_child;p = p->l_child); //找出右子树最左值
            tree->data = p->data;
            tree->r_child = tree_del(tree->r_child,tree->data);
        }
    }
    return tree;
}

void BSTree::del(int x)
{
    tree = tree_del(tree,x);
}

void tree_prt(node* tree)
{
    if(tree)
    {
        tree_prt(tree->l_child);
        // cout << "tree_prt" << endl;
        cout << tree->data << " ";
        tree_prt(tree->r_child);
        // cout << "tree_prt" << endl;
    }
}

void BSTree::print()
{
    // cout << "print" << endl;
    tree_prt(tree);
    // cout << "~print" << endl;
    cout << endl;
}

//int main()
//{
//    int n;
//    cout << "Input the number of numbers: ";
//    cin >> n;
//    BSTree tree;
//    tree.create(n);
//    tree.print();
//    cout << "Input the number you want to delete: ";
//    int tmp; cin >> tmp;
//    tree.del(tmp);
//    tree.print();
//
//    return 0;
//}

（删除操作我debug了半小时，最后发现是在主函数中把它注释掉了，蔡的抠脚）

总提纲：《数据结构》期末提纲小结