GroupBlog

1.二叉排序树的概念:

二叉排序树是一种动态树表.

二叉排序树的定义:二叉排序树或者是一颗空树,或者是一颗具有如下性质的二叉树:

若它的左子树非空,则左子树上的所有的节点的值均小于根节点的值.
若它的右子树非空, 则右子树上的所有节点的值均大于根节点的值.
左右子树本身又各是一颗二叉排序树,二叉排序树的性质：按中序遍历二叉排序树，得到的中序遍历是一个递增有序序列.

2.二叉树的插入:

在二叉排序树中插入新的节点，要保证插入后的二叉树仍然符合二叉树的定义.

插入过程:若二叉排序树为空, 则待插入的节点*s作为根节点插入到空树中;

当非空时，将待插入点关键字k 和根节点bst->key;若k<bst->key.bst=bst-<Lchild;k>bst->key，bst=bst->Rchild，一直这样递归下去,知道bst为空,插入到叶子节点.若k=bst->key，则不做任何操作, 直接返回.

3.二叉树排序树的生成:

从空的二叉排序树开始, 经过一系列的查找插入操作之后，生成了一颗二叉排序树.

说明:

每次插入的都是二叉树的叶子节点.
由不同顺序的关键字序列,会得到不同的二叉排序树.
对于一个任意的关键字序列构造一颗二叉树，其实是对关键字进行排序.

3.二叉排序树的删除:

假设被删节点*p的双亲节点是*f:

1.若*p是叶子节点,则只需要修改双亲节点的指针.

2.若节点*p是*f的左孩子.且*p只有左孩子或者只有右孩子,则只要使*p的左孩子或右孩子成为f的左孩子. 若节点*p是*f的右孩子孩子.且*p只有左孩子或者只有右孩子,则只要使*p的左孩子或右孩子成为f的右孩子.

3.若节点的左右子树均非空,先找到*p的前驱节点*s(注意*s是*p的左子树中最右下的节点,它的右链为空),以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上.

下面是我实现的代码：

#include<stdio.h>
#include<stdlib.h>
#define INFINE 32678
typedef int KeyType;  //数据类型
typedef struct Node
{
    KeyType key;
    struct Node *Lchild,*Rchild;
}BSTNode,*BSTree;
void InsertBST(BSTree *bst,KeyType k)    //插入建树法;
{
    BSTNode *s;
    if(*bst == NULL){
        s=(BSTree)malloc(sizeof(BSTNode));
        s->key=k;
        s->Lchild=NULL;
        s->Rchild=NULL;
        *bst=s;
    }else{            //寻找k的位置.
        if(k>(*bst)->key){      
            InsertBST(&((*bst)->Rchild),k);
        }else if(k<(*bst)->key){
            InsertBST(&((*bst)->Lchild),k);
        }
    }
}
void Created(BSTree *bst)
{
    KeyType key;
    *bst=NULL;
    scanf("%d",&key);
    while(key!=INFINE){
        InsertBST(bst,key);
        scanf("%d",&key);
    }
}
void Inorder(BSTree bst)
{
    if(bst!=NULL){
        Inorder(bst->Lchild);
        printf("%d ",bst->key);
        Inorder(bst->Rchild);
    }
}
BSTree SerchBST(BSTree bst,KeyType k)
{
    BSTNode *q;
    q=bst;
    while(q){
        if(q->key ==k){
            return q;
        }
        if(k>q->key){
            q=q->Rchild;
        }else{
            q=q->Lchild;
        }
    }
    return NULL;
}
BSTree DeleteBST(BSTree bst,KeyType k)
{
    BSTNode *p,*f,*q,*s;
    p=bst;
    f=NULL;
    while(p){      //寻找要删除的节点是否在二叉排序树中.
        if(p->key == k){
            break;
        }
        f=p;     //f记录p的双亲节点.
        if(p->key > k){  
            p=p->Lchild;
        }else{
            p=p->Rchild;
        }
        
    }
    if(p==NULL){
        return 0;  //待删除的节点不存在
    }
   if(p->Lchild==NULL && p->Rchild==NULL){   //待删节点的左右子树都为空.
        if(p==bst){
            bst=NULL;   //删除的是根节点;
        }else{
            if(f->Lchild == p){   
                f->Lchild=NULL;
            }else{
                f->Rchild=NULL;
            }
        }
        free(p);
    }else if(p->Lchild == NULL && p->Rchild != NULL){   //待删节点的左子树为空，右子树不为空!
        if(f->Lchild == p){
            f->Lchild=p->Rchild; //将p的右子树链接到其父节点的左链上.
        }else{
            f->Rchild=p->Rchild;   //将p的右子树链接到其父节点的右链上
        }
        free(p);
    }else if(p->Rchild == NULL && p->Lchild != NULL){
        if(f->Lchild == p){
            f->Lchild=p->Lchild;   //将p的左子树链接到父节点的左链上.
        }else{
            f->Rchild == p->Lchild;   //将p的左子树链接到父节点的右链上.
        }
        free(p);
    }else if(p->Lchild!=NULL && p->Rchild!=NULL){    //待删节点的左右子树都不为空,
        q=p;
        s=p->Lchild;    //转向左子树
        while(s->Rchild){      
            q=s;
            s=s->Rchild;       //s指向被删节点的前驱节点(中序前驱)
        }
        if(q!=p){
            q->Rchild=s->Lchild;  //重接q的右子树
        }else{
            q->Lchild=s->Lchild;  //重接q的左子树
        }
        p->key=s->key;              //以p的（中序）前驱节点s的key替换p中值.
        free(s);
    }
}
int main(int argc,char *argv[])
{
    BSTree bst;
    BSTNode *q;
    Created(&bst);
    Inorder(bst);
    printf("\n");
    q=SerchBST(bst,3);
    printf("%d\n",q->key);
    DeleteBST(bst,3);
    Inorder(bst);
    return 0;
}