天天看点
返回

BST二叉树在C语言上的实现二叉树的定义：左边节点全小于父节点，右边节点全大于父节点一、节点结构体的定义与树根的建立二、插入二、搜索三、插入四、删除六、遍历

题外话：

二叉树的思想还是挺简单的，就是左右左右，主要问题点是实现过程中用到了二级指针。

用二级指针的目的（虽然这里没有写出），是在搜索相同值的节点的时候，为了保存相同值节点的父节点，即相同值节点为*p，父节点为p；同时拥有p和*p，才能在建立新节点或者删除节点的时候建立联系。

比如插入时

new->left = NULL;
    new->right = NULL;
    new->key = key;
    *p = new;

最下面一步为*p=new，即把新建立的节点与母节点建立联系，本质是“p取值为new”。

不用二级指针的话，像链表里的插入和删除用到另外一个指针来保存前一个元素的方法，应该也是可行的。

不多说废话，现在开始建树！！

二叉树的定义：左边节点全小于父节点，右边节点全大于父节点

定义现在用不到，等到看插入和删除的时候，如果不明白大小的判断和左右寻找的关系，可以来看一下定义，我就在这里等着你。

一、节点结构体的定义与树根的建立

二叉树的每一个节点，首先包含自己的值，然后拥有一个向左的指针，和一个向右的指针。

typedef struct node{
    int key;
    struct node *left;
    struct node *right;
}NODE;
           
NODE *root = NULL;     /* 定义树根；一开始为NULL */

题外话：

有趣的是这些指针，就像在链表里一样，读者可以思考一下 **p 这个二级指针的 p，与其他各节点是什么关系，很有趣。

hint：*p 是下一个元素的值，则p存的是下一个元素的地址；

类比一下，*（*p）是下一个元素（指针）的值，则 *p 存的是下一个元素（指针）的地址，对 *p 做 * 运算，其实是取到了 *p 指向的元素的值。

这是个什么意思呢？ 即 p 节点， 就是 *p 节点的父节点。因为所有节点都是指针，指针里存地址，那指向指针的指针，自然要用二级指针。

二、插入

插入之前，要注意一个很关键的问题，即往哪插。

所以自然而然，搜索这个工作势在必行，所以先看搜索。

二、搜索

    1、比较

搜索就涉及到值的大小关系，比如相等代表已经有数据，搜索到；要搜索的值比当前值大，就往右拐等等，所以需要一个比较函数，来返回各种结果。

不明白大小与左右的关系的朋友请翻到最开头看定义。

首先定义了各种结果

#define EQUAL 1
#define BIGGER 2
#define SMALLER 3

然后是函数；    key为传入的要搜索的值，cur_key为当前节点的key

int keyComp (int key, int cur_key)
{
    if (key == cur_key)
        return EQUAL;
    else if (key > cur_key)
        return BIGGER;
    else return SMALLER;
}

    2、搜索

搜索这个工作非常简单，就是一个终止条件，即当前节点一旦为NULL，则表明已经到了头，停止搜索；flag为比较函数的返回值

这个函数的返回值可以根据需要自己定义。此处是，如果找到，则返回该节点的地址；方便操作，如果要修改数据什么的。

NODE * treeSearch (int key)
{
    NODE * p = root;
    int flag;
    
    while (p != NULL){
        flag = keyComp(key, p->key);
        
        if (flag == EQUAL)
            return p;
        else if (flag == BIGGER)
            p = p->right;
        else        /* flag == SMALLER */
            p = p->left;
    }
    return NULL;        /* 没有该元素 */
}

三、插入

要想插入，还是得先搜索，搜索到一个可以插入的位置。

请注意，什么叫可以插入的位置。

首先要保证没有改值，否则就重复了。

其次如果要插入的值大于当前节点的值，就看节点的指向右边的指针，如果为NULL，则可以插入，就插他；如果已经有了元素，则重复以上操作，继续往下找，直到找到一个空位。

最后如果要插入的值小于当前节点的值，就对称一下上面的过程。。

所以搜索的过程一共有三个分支

1、相等

2、大于

3、小于

写成代码就是这个样子（注意终止条件）用了二级指针，为了保存当前节点的父节点，用来建立新节点与父节点的联系，看不懂的可以上去看看题外话。

NODE * treeInsert (int key)
{
    NODE **p = &root, *new;
    int flag;
    
    /* 搜索插入位置 */
    while ((*p) != NULL){    /* 为什么要判断*p而不是p？因为p是父节点，*p才是子节点 */

        flag = keyComp(key, (*p)->key);
        
        if(flag == EQUAL)       /* 已经有相同的key存在 */
            return NULL;
        else if (flag == BIGGER)
            p = &(*p)->right;    /* p是二级指针 */
        else
            p = &(*p)->left;
    }
    
    if((new = (NODE *)malloc(sizeof(NODE))) == NULL){
        printf("no memory\n");
        exit(0);
    }
    
    new->left = NULL;
    new->right = NULL;
    new->key = key;
    *p = new;    /* p为父节点；该语句的目的在于让p和new通过*p建立联系 */
    
    return new;
}

返回值依然是新添加的元素的地址，依然可以根据需要定义。

四、删除

终于插完了！！现在来看看最复杂的部分，删除。

其实也不难，如果插入部分的二级指针理解了的话。

删除也分三个分支，简单想一下就可以知道。

但是可不能随意删除哦，随意删除很有可能破坏二叉树的定义，即左边全小于父节点，右边全大于父节点。

所以要遵循一定的规则，但也只有一种情况需要啦，不要担心。

第一种就是要删除的节点没有孩子，很开心，直接删。

第二种是有一个孩子，轻松愉快，孩子提到该节点的位置进行替换即可。

第三种是有两个孩子，规则就是寻找该节点右边的最小值节点，用它来替换该节点。

什么意思呢，就是被删除节点的right一个节点，然后一直往左往左走到黑，就找到了最小值（根据定义，左边全小于）

所以需要一个额外的搜索最小值节点函数，找到后将其保存，删除，传回备用。

此处传入的参数应当是被删除节点的右指针指向的节点的地址，传回该最小值节点的地址。

NODE *treeDeleteMin(NODE **p)
{
    NODE *x;
    while ((*p)->left != NULL)
        p = &(*p)->left;
    x = *p;
    *p = x->right; /* 将该节点右边的节点提到该位置，若没有则是NULL */
    
    return x;
}

再次提醒此处的二级指针，到底为什么要用二级指针？？？？（抓耳挠腮中）

不知道，可能我脑子抽了，这里一级指针也可以。

传回参数直接赋值给原函数中的*p，即要被删除的节点。但要注意，为了建立联系，要用一个指针x保存原*p，操作完指针，建立起联系之后之后再释放。

int treeDelete (int key)
{
    NODE **p = &root, *x;
    int flag;
    while((*p) != NULL){
        flag = keyComp(key, (*p)->key);
        x = *p;
        if (flag == EQUAL){
            /* 没有孩子 */
            if ((x->right == NULL) && (x->right == NULL))
                *p = NULL;
            /* 有一个孩子 */
            else if (x->right == NULL)
                *p = x->left;
            else if (x->left == NULL)
                *p = x->right;
            /* 有两个孩子 */
            else{
                *p = treeDeleteMin(&x->right);
                (*p)->left = x->left;
                (*p)->right = x->right;
            }
            free(x);
            return 1;
        }
        else if (flag == BIGGER)
            p = &(*p)->right;
        else
            p = &(*p)->left;
        }
    return 0;
    }

六、遍历

终于建完树了，下面看看自己的成果吧！

二叉树的话当然是用中序，即···有机会专门写篇帖子讲一下三种序吧，这里直接上程序，不懂的小伙伴们麻烦查一下喽。

主要思想是递归。

void treeView (NODE *p)
{
    if (p == NULL)
        return;
    else{
        treeView(p->left);
        printf("%d\n", p->key);
        treeView(p->right);
    }
}

仔细看，じっと見ると分かる。。。といってもわからん！！！

大丈夫、オ イ ジィン ジュン ビ ホ ロ トー

（没事，我已经准备好了图）

有必要说明一下，圈1234对应程序里的4条语句，红色的p1p2···p6代表递归跳出之后紧接的打印，小伙伴们要真的想明白，就照着这个图，自己画一下想一下，马上就懂了，相信我。by the way 图中圈2圈4里面的order其实是函数本身，p-left和pright是传进函数的参数，意为向左一个节点或向右一个节点。

BST二叉树在C语言上的实现二叉树的定义：左边节点全小于父节点，右边节点全大于父节点一、节点结构体的定义与树根的建立二、插入二、搜索三、插入四、删除六、遍历

终于码完了，下面是全部的码，主程序就请自己搞定啦。

/* BST */

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


#define EMPTY 0
#define EQUAL 1
#define BIGGER 2
#define SMALLER 3


/* 数据结构定义 */
typedef struct node{
    int key;
    struct node *left;
    struct node *right;
}NODE;

/* 树的建立与初始化 */
NODE *root = NULL;

/* fuction */
int keyComp (int key, int cur_key);        /* 比较；目标值，节点值 */
NODE * treeSearch (int key);       /* 搜索；root作为搜索开始 */
NODE * treeInsert (int key);        /* 插入 */
int treeDelete (int key);       /* 删除 */
NODE * treeDeleteMin (NODE **p);        /* 找到右部分树最小值 */
void treeView (NODE *p);        /* 中序 */

/* 主函数 */
int main()
{
    treeInsert (3);
    treeInsert (5);
    treeInsert (2);
    treeInsert (6);
    treeInsert (10);
    
    treeDelete(2);
    
    treeView (root);
    
    return 0;
}


int keyComp (int key, int cur_key)
{
    if (key == cur_key)
        return EQUAL;
    else if (key > cur_key)
        return BIGGER;
    else return SMALLER;
}


NODE * treeSearch (int key)
{
    NODE * p = root;
    int flag;
    
    while (p != NULL){
        flag = keyComp(key, p->key);
        
        if (flag == EQUAL)
            return p;
        else if (flag == BIGGER)
            p = p->right;
        else        /* flag == SMALLER */
            p = p->left;
    }
    return NULL;        /* 没有该元素 */
}


NODE * treeInsert (int key)
{
    NODE **p = &root, *new;
    int flag;
    
    /* 搜索插入位置 */
    while ((*p) != NULL){

        flag = keyComp(key, (*p)->key);
        
        if(flag == EQUAL)       /* 已经有相同的key存在 */
            return NULL;
        else if (flag == BIGGER)
            p = &(*p)->right;
        else
            p = &(*p)->left;
    }
    
    if((new = (NODE *)malloc(sizeof(NODE))) == NULL){
        printf("no memory\n");
        exit(0);
    }
    
    new->left = NULL;
    new->right = NULL;
    new->key = key;
    *p = new;
    
    return new;
}


int treeDelete (int key)
{
    NODE **p = &root, *x;
    int flag;
    while((*p) != NULL){
        flag = keyComp(key, (*p)->key);
        x = *p;
        if (flag == EQUAL){
            /* 没有孩子 */
            if ((x->right == NULL) && (x->right == NULL))
                *p = NULL;
            /* 有一个孩子 */
            else if (x->right == NULL)
                *p = x->left;
            else if (x->left == NULL)
                *p = x->right;
            /* 有两个孩子 */
            else{
                *p = treeDeleteMin(&x->right);
                (*p)->left = x->left;
                (*p)->right = x->right;
            }
            free(x);
            return 1;
        }
        else if (flag == BIGGER)
            p = &(*p)->right;
        else
            p = &(*p)->left;
        }
    return 0;
    }


NODE *treeDeleteMin(NODE **p)
{
    NODE *x;
    while ((*p)->left != NULL)
        p = &(*p)->left;
    x = *p;
    *p = x->right;
    
    return x;
}

void treeView (NODE *p)
{
    if (p == NULL)
        return;
    else{
        treeView(p->left);
        printf("%d\n", p->key);
        treeView(p->right);
    }
}

热烈欢迎指正与讨论！！！

c语言 BST 二叉树
上一篇: 【转载.SQL注入原理】SQL Server应用程序中的高级SQL注入
下一篇: ssm 实现日志 用aspectj_javaWEB SSM AOP+注解保存操作日志

继续阅读