一波C语言二元查找树算法题目解答实例汇总

什么是二元查找树？

二元查找树，又称为二叉搜索树，是一种非常常见的数据结构，它的主要特点是左子树所有节点的值小于其根节点的值，右子树所有节点的值大于其根节点的值。该策略保证整个树的左子树所有节点小于根节点，右子树所有节点大于根节点。

二元查找树可以用来做很多问题，例如查找、插入、删除等。

二元查找树算法题目解答实例汇总

下面我们将对几个常见的二元查找树算法题目进行讲解。

题目一： 向二元查找树中插入节点

实现一个函数，将一个整数插入到二元查找树中。

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* insertIntoBST(struct TreeNode* root, int val){
    if (root == NULL) {
        root = malloc(sizeof(struct TreeNode));
        root->val = val;
        root->left = NULL;
        root->right = NULL;
    } else {
        if (root->val < val) {
            root->right = insertIntoBST(root->right, val);
        } else if (root->val > val) {
            root->left = insertIntoBST(root->left, val);
        } else {
            // do nothing
        }
    }
    return root;
}

以上代码通过递归将值插入二元查找树中。如果根节点为空，则新建一个根节点并返回；如果插入的值小于根节点，则继续递归左子树；如果插入的值大于根节点，则递归右子树。如果插入的值已经存在，则不进行任何操作。

题目二： 在二元查找树中删除节点

实现一个函数，将一个给定的值从二元查找树中删除。如果树中节点数小于等于1，则删除整个树。

struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    if (root == NULL) {
        return NULL;
    }

    if (root->val == key) {
        // 如果是叶子节点，则直接删除
        if (root->left == NULL && root->right == NULL) {
            free(root);
            root = NULL;
        } else if (root->left == NULL) {
            // 如果只有右孩子，则将右孩子上升为新的根节点
            struct TreeNode *tmp = root;
            root = root->right;
            free(tmp);
        } else if (root->right == NULL) {
            // 如果只有左孩子，则将左孩子上升为新的根节点
            struct TreeNode *tmp = root;
            root = root->left;
            free(tmp);
        } else {
            // 如果有两个孩子，则将右子树的最小值作为新的根节点
            struct TreeNode *tmp = root->right;
            while (tmp->left != NULL) {
                tmp = tmp->left;
            }
            root->val = tmp->val;
            root->right = deleteNode(root->right, tmp->val);
        }
    } else if (root->val < key) {
        root->right = deleteNode(root->right, key);
    } else {
        root->left = deleteNode(root->left, key);
    }

    return root;
}

以上代码通过递归将给定值从二元查找树中删除。如果根节点为空，则返回 NULL；如果要删除的值小于根节点，则继续递归左子树；如果要删除的值大于根节点，则递归右子树。如果要删除的值等于根节点，需要考虑以下三种情况：

• 如果要删除的节点是叶子节点，则直接删除。
• 如果要删除的节点只有一个孩子，则将该孩子上升为新的根节点。
• 如果要删除的节点有两个孩子，则将右子树的最小值作为新的根节点。

示例一：向二元查找树中插入节点

例如，将数组 [4,2,7,1,3] 转换成二元查找树，代码如下：

struct TreeNode* root = NULL;
for (int i = 0; i < 5; i++) {
    root = insertIntoBST(root, nums[i]);
}

其中 nums 数组为 [4,2,7,1,3]，表示要插入的数。插入后的二元查找树如下所示：

      4
     / \
    2   7
   / \
  1   3

示例二：在二元查找树中删除节点

例如，删除数值为 2 的节点进行重建，代码如下：

root = deleteNode(root, 2);

重建后的二元查找树如下所示：

      4
     / \
    3   7
   /
  1

总结

二元查找树是一种非常有用的数据结构，可以用来解决很多问题。通过上述两个题目的讲解，希望大家能够更加深入的了解二元查找树的相关知识。