数据结构: 二进制搜索树（用C语言实现）

有关二叉树的基本知识，请参阅我的博客之一: 二叉树的链式存储

说明:

二进制排序树是具有以下属性的空树或二进制树:

1. 如果左子树不为空，则左子树上所有节点的值均小于其根节点的值;

2. 如果右子树不为空，则右子树上所有节点的值都大于其根节点的值；

3. 左右子树也是二叉排序树

说明:

通过重复将节点插入二叉树来构造二叉树！

如果二叉树为空树二叉排序树的建立c，则将元素插入为根节点.

如果根节点的键值等于key，则插入失败；

如果键小于根节点的键值二叉排序树的建立c，它将被插入到根的左子树中；否则，它将被插入到根的右子树中

新插入的节点必须是叶节点！

代码分析:

void InsertBST(BiStree &Tree,ElemType e)
{
    BiStree T =Tree;    //定义执行副本，！
    BiStree father =NULL; //定义
    while (T&&T->data.key!=e.key)
    {
        father=T;
        if(e.key>T->data.key)
            T=T->Rchild;
        else
            T=T->Lchild;
    }
    if(T) //跳出循环的只有两种情况，要么就是T不存在，要么就是找到了对应元素！T 存在说明，只能是对应元素也存在，那我我们就不用插入了
        return;
    BiSnode *s = (BiSnode*)malloc(sizeof(BiSnode));//能到这里，说明节点不存在，新建一个节点，并初始化！
    s->data=e;
    s->Rchild=s->Lchild=NULL;
    if(father==NULL)        //如果farther不存在，那说明就是没有执行While语句，也即是树是空的，因为一旦执行，就不会为NULL！
        Tree=s;
    else if(e.key>father->data.key) //到这里说明Farther存在,那么剩下的就是往farther左右节点插入元素了
        father->Rchild=s;
    else
        father->Lchild=s;
}

说明:

删除操作的基础是查找元素. 首先，您需要找到要删除的元素. 如果找到它，将其删除. 如果找不到，则无需删除它.

找到一些代码:

void DelBST(BiStree &Tree,char key)
{
    if(!Tree) //如果节点为空节点，说明要删除的元素不可能存在，所以返回就好！
        return;
    else //下面是节点存在的分情况判断：
    {
        if(Tree->data.key==key) //如果找到了要删除的节点！
        {
            deleteNode(Tree);   //删除该节点
        }
        else if(Tree->data.key<key)  //如果要删除的节点大于该节点，则往该节点的右子树方向进行查找
            DelBST(Tree->Rchild,key);
        else
            DelBST(Tree->Lchild,key);//如果要删除的节点小于该节点，则往该节点的左子树方向进行查找
    }
}

现在我们已经找到了元素，要删除它，我们必须实现deleteNode（Tree）;方法！

但是，删除元素的操作有很多情况，我们必须分别处理它们:

★要删除的节点* p是叶节点

★要删除的节点* p只是一个非空子树

★要删除的节点* p具有两个非空子树

如何找到直接的前任: 找到要删除的节点的第一个左子树，然后继续向右走！

删除代码如下:

void deleteNode(BiStree &p)
{
    if(!p->Rchild)  //对第一种及第二种情况的处理
    {
        BiSnode * q =p;
        p=p->Lchild;
        free(q);
    }
    else if(!p->Lchild) //对第一种及第二种情况的处理
    {
        BiSnode * q =p;
        p=p->Rchild;
        free(q);
    } else
    {
        BiSnode * q =p;
        BiSnode * s =p->Lchild;
        while (s->Rchild)
        {
            q=s;
            s=s->Rchild;
        }
        //s指向被删节点p的前驱
        p->data=s->data;
        if(q!=p) //详见下两图
            q->Rchild=s->Lchild;    //左图
         else
            q->Lchild=s->Lchild;    //右图
        free(s);
    }
}

该代码不会被降级，非常简单！

查找键值为K的记录:

如果二进制排序树是空树，则搜索失败并返回；

如果根节点的键值等于key，则搜索成功并返回；

如果根节点的键值大于key，则继续在根的左子树上搜索；否则，继续在根的右子树上搜索

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-177261-1.html