c语言实现二叉查找树

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define true 1
#define false 0

typedef int ElemType;
typedef int KeyType;

/*二叉查找树的节点结构定义*/
typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

/*二叉查找树查找算法*/
int SearchBST(BiTree T, KeyType key, BiTree f, BiTree *p)
{
    /*如果T指针为空, 说明查找失败*/
    if(!T)
    {
        *p = f;
        return false;
    }
    /*如果相等, 令p指针指向该关键字*/
    else if(key == T->data)
    {
        *p = T;
        return true;
    }
    /*如果key值比T根节点的值小, 则查找其左子树; 反之, 查找其右子树*/
    else if(key < T->data)
    {
        return SearchBST(T->lchild, key, T, p);
    }
    else
    {
        return SearchBST(T->rchild, key, T, p);
    }
}

int InsertBST(BiTree *T, ElemType e)
{
    BiTree p = NULL;

    /*如果查找不成功, 需做插入操作*/
    if(!SearchBST((*T), e, NULL, &p))
    {
        /*初始化插入节点*/
        BiTree s = (BiTree)malloc(sizeof(BiTNode));

        s->data = e;
        s->lchild = s->rchild = NULL;

        /*如果p为null, 说明该二叉树为空树, 此时插入的结点为整棵树的根节点*/
        if(!p)
        {
            *T = s;
        }
        /*如果p不为NULL, 则p指向的为查找失败的最后一个子节点*/
        else if(e < p->data)
        {
            p->lchild = s;
        }
        else
        {
            p->rchild = s;
        }

        return true;
    }

    return false;
}

int Delete(BiTree *p)
{
    BiTree q, s;

    /*情况1, 结点p本身为叶子结点, 直接删除即可*/
    if(!(*p)->lchild && !(*p)->rchild)
    {
        q = *p;
        free(q);
        *p = NULL;
    }
    /*情况2, 左子树为空, 只需用结点p的右子树根节点代替结点p即可*/
    else if(!(*p)->lchild)
    {
        q = *p;
        *p = (*p)->rchild;
        free(q);
    }
    /*情况3, 右子树为空, 只需用结点p的左子树根节点代替结点p即可*/
    else if(!(*p)->rchild)
    {
        q = *p;
        *p = (*p)->lchild;
        free(q);
    }
    /*情况4, 左右子树均不为空*/
    else
    {
        q = *p;
        s = (*p)->lchild;

        /*遍历, 找到结点p的前驱*/
        while(s->rchild)
        {
            q = s;
            s = s->rchild;
        }

        /*直接改变结点p的值*/
        (*p)->data = s->data;

        /*判断结点p的左子树s是否有右子树*/
        if(q != *p)
        {
            /*若有, 则在删除直接前驱结点的同时, 令前驱的左孩子结点改为q指向结点孩子的结点*/
            q->rchild = s->lchild;
        }
        else
        {
            /*若无, 则直接将左子树上移即可*/
            q->lchild = s->lchild;
        }

        free(s);
    }

    return true;
}

int DeleteBST(BiTree *T, int key)
{
    /*不存在关键字等于key的数据元素*/
    if(!(*T))
    {
        return false;
    }
    else
    {
        if(key == (*T)->data)
        {
            Delete(T);
            return true;
        }
        else if(key < (*T)->data)
        {
            /*使用递归的方式*/
            return DeleteBST(&(*T)->lchild, key);
        }
        else
        {
            return DeleteBST(&(*T)->rchild, key);
        }
    }
}

/*中序输出*/
void order(BiTree t)
{
    if(t == NULL)
    {
        return;
    }

    order(t->lchild);
    printf("%d ", t->data);
    order(t->rchild);
}

int main()
{
    int i;
    int a[5] = {3, 4, 2, 5, 9};
    BiTree T = NULL;

    for(i=0; i<5; i++)
    {
        InsertBST(&T, a[i]);
    }

    printf("中序遍历二叉树\n");
    order(T);
    printf("\n");
    printf("删除3之后, 中序遍历二叉树\n");
    DeleteBST(&T, 9);
    order(T);
    printf("\n");

    return 0;
}

2.编译源码

$ gcc -o test test.c -std=c99

3.运行及其结果

$ ./test
中序遍历二叉树
2 3 4 5 9 
删除3之后, 中序遍历二叉树
2 3 4 5