C语言实现BST二叉排序树的基本操作

C语言实现BST二叉排序树的基本操作，可以分为创建、插入、删除、查找、遍历等几个步骤。

创建二叉排序树

创建一个二叉排序树的过程，就是创建BSTNode结构体实例的过程。BSTNode结构体定义如下：

typedef struct BSTNode
{
    int data;        // 数据域
    struct BSTNode *left;   // 左孩子指针
    struct BSTNode *right;  // 右孩子指针
}BSTNode, *BSTree;

这里定义了一个BSTree类型，表示指向BSTNode结构体的指针。

创建二叉排序树的步骤如下：

1. 初始化BSTree为NULL，表示空树。
2. 循环读入数据，每读入一个数据，就将其插入二叉排序树中。

示例代码如下：

BSTree create_bst()
{
    BSTree root = NULL; // 根节点初始化为空

    printf("请输入节点数据，结束标志为-1：\n");
    int val;
    scanf("%d", &val);

    while(val != -1)
    {
        root = insert_bst(root, val);
        scanf("%d", &val);
    }

    return root;
}

插入节点

插入节点操作是指将一个新的节点插入到二叉排序树中，使得插入后仍然保持有序性质的操作。

插入节点的步骤如下：

1. 如果树为空，则创建一个新结点作为根节点。
2. 如果树不为空，则从根节点开始，递归查找插入位置。
3. 如果需要插入的值小于当前结点，则在左子树中递归查找插入位置。
4. 如果需要插入的值大于当前结点，则在右子树中递归查找插入位置。
5. 如果需要插入的值与当前结点的值相等，则不进行插入操作。

示例代码如下：

BSTree insert_bst(BSTree root, int val)
{
    if(root == NULL)
    {
        root = (BSTree)malloc(sizeof(BSTNode));
        root->data = val;
        root->left = NULL;
        root->right = NULL;
    }
    else if(val < root->data)
    {
        root->left = insert_bst(root->left, val);
    }
    else if(val > root->data)
    {
        root->right = insert_bst(root->right, val);
    }

    return root;
}

删除节点

删除节点操作是指从二叉排序树中删除一个指定的节点的操作。

删除节点的步骤如下：

1. 查找需要删除的节点。
2. 如果需要删除的节点没有左右子树，则直接删除。
3. 如果需要删除的节点只有左子树或右子树，则用其左子树或右子树代替它本身。
4. 如果需要删除的节点既有左子树又有右子树，则用其左子树最大节点或右子树最小节点代替它本身。

示例代码如下：

BSTree delete_bst(BSTree root, int val)
{
    if(root == NULL)    // 树为空，找不到要删除的节点
    {
        return NULL;
    }
    else if(val < root->data)   // 要删除的节点在左子树中，递归删除
    {
        root->left = delete_bst(root->left, val);
    }
    else if(val > root->data)   // 要删除的节点在右子树中，递归删除
    {
        root->right = delete_bst(root->right, val);
    }
    else    // 找到要删除的节点
    {
        if(root->left == NULL && root->right == NULL)   // 情况1：没有左右子树
        {
            free(root);
            root = NULL;
        }
        else if(root->left == NULL)    // 情况2：只有右子树
        {
            BSTree temp = root;
            root = root->right;
            free(temp);
        }
        else if(root->right == NULL)   // 情况2：只有左子树
        {
            BSTree temp = root;
            root = root->left;
            free(temp);
        }
        else    // 情况3：左右子树都有
        {
            BSTree temp = find_max(root->left);   // 从左子树中找到最大值
            root->data = temp->data;   // 用最大值代替要删除的节点
            root->left = delete_bst(root->left, temp->data);  // 删除左子树中的最大值所在节点
        }
    }

    return root;
}

// 在BSTree中查找最大值节点
BSTree find_max(BSTree root)
{
    if(root == NULL)
    {
        return NULL;
    }
    else if(root->right == NULL)
    {
        return root;
    }
    else
    {
        return find_max(root->right);
    }
}

查找节点

查找节点操作是指在二叉排序树中查找一个指定的节点的操作，返回节点的位置或NULL。

查找节点的步骤如下：

1. 从根节点开始，如果当前节点为空，则返回NULL表示未找到。
2. 如果当前节点的值等于要查找的值，则返回该节点。
3. 如果当前节点的值大于要查找的值，则在左子树中递归查找。
4. 如果当前节点的值小于要查找的值，则在右子树中递归查找。

示例代码如下：

BSTree search_bst(BSTree root, int val)
{
    if(root == NULL)    // 未找到
    {
        return NULL;
    }
    else if(root->data == val)  // 找到了
    {
        return root;
    }
    else if(root->data > val)   // 在左子树中查找
    {
        return search_bst(root->left, val);
    }
    else    // 在右子树中查找
    {
        return search_bst(root->right, val);
    }
}

遍历二叉排序树

遍历二叉排序树的过程，主要有三种方式，分别是前序遍历、中序遍历、后序遍历。

前序遍历

前序遍历的步骤如下：

1. 访问当前节点。
2. 遍历左子树。
3. 遍历右子树。

示例代码如下：

void pre_order(BSTree root)
{
    if(root != NULL)
    {
        printf("%d ", root->data);
        pre_order(root->left);
        pre_order(root->right);
    }
}

中序遍历

中序遍历的步骤如下：

1. 遍历左子树。
2. 访问当前节点。
3. 遍历右子树。

示例代码如下：

void in_order(BSTree root)
{
    if(root != NULL)
    {
        in_order(root->left);
        printf("%d ", root->data);
        in_order(root->right);
    }
}

后序遍历

后序遍历的步骤如下：

1. 遍历左子树。
2. 遍历右子树。
3. 访问当前节点。

示例代码如下：

void post_order(BSTree root)
{
    if(root != NULL)
    {
        post_order(root->left);
        post_order(root->right);
        printf("%d ", root->data);
    }
}

以上就是C语言实现BST二叉排序树的基本操作的完整攻略，并提供了相应示例代码。

阅读剩余 82%