二叉查找树(BST树)

二叉查找树的特点：

在二叉查找树中左子树上所有结点的数据都小于等于根结点的数据,而右子树上所有结点的数据都大于根结点的数据

//存储结构：
struct node
{
    Int data;
    node *lchild;
    node *rchild;
};

//在建树前根节点不存在:
Node *root = NULL;

//新建结点:
node *newNode(int v)
{
    node *Node = new node;
    Node->data = v;
    Node->lchild = NULL;
    Node->rchild = NULL;
    return Node;
}

//二叉查找树结点的查找、修改:
//时间复杂度:O(h) h是二叉查找树的高度
void search(node *root,int x,int newdata) // 在这里修改的是root指针指向的内容,所以不需要加引用&
{
    if(root == NULL)
        return;
    if(root->data == x)
        root->data = newdata;
    if(root->data <= x) search(root->lchild,x,newdata);
    else if(root->data > x)
        search(root->rchild,x,newdata);
}
//二叉查找树的插入:
//时间复杂度:O(h) h是二叉查找树的高度
void insert(node *&root,int x) // 这里要加引用,是因为修改的是root指针本身 
{
    if(root == NULL)
    {
        root = newNode(x);
        return root;
    }
    if(x<=root->data)   // 生成二叉查找树 
        insert(root->lchild,x);
    else
        insert(root->rchild,x);
}

//二叉查找树的创建:
node *create(int data[],int n)   
{
    node *root = NULL;
    for(int i=0;i<n;++i)
        insert(root,data[i]);
    return root;    
}

二叉查找树的删除
一般有两种常见做法,时间复杂度都是$O(h)$,h是二叉查找树的高度。为了保证删除之后仍然是二叉查找树。
一种方法是以树中比删去数小而又最大的结点(称为该结点的前驱)覆盖删去数，再删去该结点。
另一种则是以树中比删去数大而又最小的结点(称为该结点的后继)覆盖删去数，再删去该结点。

node *findMax(node *root)
{
    while(root->rchild != NULL)
        root = root->rchild;
    return root;
}

node *findMin(node *root)
{
    while(root->lchild != NULL)
        root = root->lchild;
    return root;
}

void deleteNode(node *&root,int x) // 加引用是因为要修改指针本身(删除) 
{
    if(root == NULL) // 树中没有x这个数据 
        return;
    if(root->data == x)
    {
        if(root->lchild==NULL && root->rchild==NULL)  //没有左右子树,直接删除 
        {
            root = NULL;
        }
        else if(root->lchild!=NULL) // 有左子树,则找前驱来覆盖root 
        {
            node *pre = findMax(root->lchild);
            root->data = pre->data;
            deleteNode(root,pre->data);
        }
        else if(root->rchild!=NULL) // 有右子树,则找后继来覆盖root 
        {
            node *next = findMin(root->rchild);
            root->data = next->data;
            deleteNode(root,next->data);
        }
    }
    else if(root->data > x)  // 根据二叉查找树特性继续找x 
    {
        deleteNode(root->lchild,x);
    }
    else
    {
        deleteNode(root->rchild,x);
    }
}

这段代码还可以进行优化，例如在找到欲删除结点root的后继结点next后，不进行递归删除，而通过这样的手段直接删除该后继：假设结点next的父亲结点是结点S，显然next是结点S的左孩子，那么由于结点next一定没有左子树，便可以直接把结点next的右子树代替结点next成为S的左子树，这样就删去了结点next。前驱同理。但这个优化需要在结点定义中额外记录每个结点的父亲结点地址。
而且我们可以发现上面的二叉查找树删除操作总是优先删除前驱(或者后继)，这样容易使树的左右子树高度不平衡，最终使二叉查找树退化成一条链。
有两种方法解决这个问题：1.每次交替删除前驱或者后继 2.记录每个节点子树的高度，并且总是优先在高度较高的子树里删除结点。（也是平衡二叉树(AVL树)的原理）

二叉查找树的一个性质：因为二叉查找树本身的特点(左<=根<右)，因此对二叉查找树进行中序遍历，遍历的结果是有序的。