首页 > 操作系统 >

二叉搜索树（1）图形分析和C语言实现(2)

电脑杂谈　发布时间：2020-06-10 16:03:43　来源：网络整理

复制代码

查找后继节点的代码

复制代码

Node* bstree_successor(Node *x)
{
    // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
    if (x->right != NULL)
        return bstree_minimum(x->right);
    // 如果x没有右孩子。则x有以下两种可能：
    // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
    // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
    Node* y = x->parent;
    while ((y!=NULL) && (x==y->right))
    {
        x = y;
        y = y->parent;
    }
    return y;
}

复制代码

6. 插入

插入节点的代码

复制代码

static Node* bstree_insert(BSTree tree, Node *z)
{
    Node *y = NULL;
    Node *x = tree;
    // 查找z的插入位置
    while (x != NULL)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
    if (y==NULL)
        tree = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;
    return tree;
}
Node* insert_bstree(BSTree tree, Type key)
{
    Node *z;    // 新建结点
    // 如果新建结点失败，则返回。
    if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)
        return tree;
    return bstree_insert(tree, z);
}

复制代码

bstree_insert（tree，z）是一个内部函数. 其功能是将节点（z）插入二叉树（tree）中，并在插入节点后返回根节点.

insert_bstree（tree，key）是一个外部接口. 它的功能是在树上添加一个节点，键是该节点的值. 并在插入节点后返回根节点.

注意: 本文实现的二进制搜索树允许插入具有相同键值的节点！如果用户不想插入具有相同键值的节点，则将bstree_insert（）修改为以下代码.

复制代码

static Node* bstree_insert(BSTree tree, Node *z)
{
    Node *y = NULL;
    Node *x = tree;
    // 查找z的插入位置
    while (x != NULL)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else  if (z->key > x->key)
            x = x->right;
        else
        {
            free(z); // 释放之前分配的系统。
            return tree;
        }
    }
    z->parent = y;
    if (y==NULL)
        tree = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;
    return tree;
}

复制代码

7. 删除

删除节点代码

复制代码

static Node* bstree_delete(BSTree tree, Node *z)
{
    Node *x=NULL;
    Node *y=NULL;
    if ((z->left == NULL) || (z->right == NULL) )
        y = z;
    else
        y = bstree_successor(z);
    if (y->left != NULL)
        x = y->left;
    else
        x = y->right;
    if (x != NULL)
        x->parent = y->parent;
    if (y->parent == NULL)
        tree = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;
    if (y != z) 
        z->key = y->key;
    if (y!=NULL)
        free(y);
    return tree;
}
Node* delete_bstree(BSTree tree, Type key)
{
    Node *z, *node; 
    if ((z = bstree_search(tree, key)) != NULL)
        tree = bstree_delete(tree, z);
    return tree;
}

复制代码

bstree_delete（tree，z）是一个内部函数. 其功能是删除二叉树（树）中的节点（z），并在删除节点后返回根节点.

排序二叉树的删除_二叉树的遍历 c_二叉排序树 c

delete_bstree（tree，key）是外部接口. 它的功能是在树中找到具有键值的节点，并在找到后删除该节点. 并在删除节点后返回到根节点.

8. 打印

打印二叉树代码

复制代码

void print_bstree(BSTree tree, Type key, int direction)
{
    if(tree != NULL)
    {
        if(direction==0)    // tree是根节点
            printf("%2d is root\n", tree->key);
        else                // tree是分支节点
            printf("%2d is %2d's %6s child\n", tree->key, key, direction==1?"right" : "left");
        print_bstree(tree->left, tree->key, -1);
        print_bstree(tree->right,tree->key,  1);
    }
}

复制代码

print_bstree（树，键，方向）的功能是打印整个二叉树（树）. 其中，树是二叉树节点，键是二叉树的键值，方向是节点的类型:

direction为0，表示该节点是根节点；

direction为-1，表示该节点是其父节点的左子节点；

direction为1，表示该节点是其父节点的右子节点.

9. 销毁二叉树

破坏二叉树的代码

复制代码

void destroy_bstree(BSTree tree)
{
    if (tree==NULL)
        return ;
    if (tree->left != NULL)
        destroy_bstree(tree->left);
    if (tree->right != NULL)
        destroy_bstree(tree->right);
    free(tree);
}

复制代码

完整的实现代码

二进制搜索树头文件（bstree.h）

查看代码

二叉搜索树实现文件（bstree.c）

查看代码

用于二进制搜索树的测试程序（btree_test.c）

查看代码

上面的btree_test.c是二进制搜索树的测试程序，其运行结果如下:

复制代码

== 依次添加: 1 5 4 3 2 6 
== 前序遍历: 1 5 4 3 2 6 
== 中序遍历: 1 2 3 4 5 6 
== 后序遍历: 2 3 4 6 5 1 
== 最小值: 1
== 最大值: 6
== 树的详细信息: 
 1 is root
 5 is  1's  right child
 4 is  5's   left child
 3 is  4's   left child
 2 is  3's   left child
 6 is  5's  right child
== 删除根节点: 3
== 中序遍历: 1 2 4 5 6

复制代码

下面将分析测试过程的流程！

（01）创建一个“二进制搜索树”根.

（02）依次将1,5,4,3,2,6插入二进制搜索树. 如下图所示: