二叉排序树的查找的递归算法，c语言实现代码

二叉排序树（Binary Search Tree, BST）的查找递归算法是一种常用的数据结构操作，其基本思想是从根节点开始，如果目标值小于当前节点的值，则在左子树中继续搜索；如果大于当前节点，则在右子树中搜索；如果找到相等的值则返回，否则如果没有找到则返回空。

以下是C语言实现的简单递归查找算法：

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 递归查找函数
TreeNode* searchBST(TreeNode* root, int target) {
    // 如果根节点为空或者等于目标值，直接返回
    if (root == NULL || root->val == target)
        return root;

    // 否则，如果目标值小于当前节点值，就在左子树里递归查找
    if (target < root->val)
        return searchBST(root->left, target);

    // 如果目标值大于当前节点值，就在右子树里递归查找
    return searchBST(root->right, target);
}

在这个递归过程中，当遍历到叶子节点仍找不到目标值，或遍历完所有节点都没有找到时，函数会返回NULL，表示目标值不存在于该二叉搜索树中。

相关问题

二叉排序树的递归查找算法c语言

二叉排序树（Binary Search Tree, BST）是一种特殊的二叉树，其中每个节点的左子树包含的所有节点值都小于该节点，右子树包含的所有节点值都大于该节点。递归查找算法在BST中非常直观，它的基本思想是：如果目标值等于当前节点的值，就找到了；如果目标值小于当前节点，就在左子树中递归查找；如果目标值大于当前节点，就在右子树中递归查找。

以下是一个简单的C语言递归查找算法的示例：

// 假设我们有一个名为Node的结构体，其中包含val（值）、left和right指针
typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

// 二叉搜索树查找函数
Node* search(Node* root, int target) {
    // 基本情况：如果根节点为空或找到了目标值
    if (root == NULL || root->val == target)
        return root;

    // 如果目标值小于根节点，递归查找左子树
    if (target < root->val)
        return search(root->left, target);

    // 否则在右子树查找
    return search(root->right, target);
}

实现（平衡）二叉排序树的各种算法代码

以下是实现平衡二叉排序树（AVL树）的各种算法的C语言代码示例。

注：平衡二叉排序树的左子树和右子树的高度差不能超过1，以保证树的平衡。

1. AVL树节点结构体定义

struct AVLNode {
    int data;
    struct AVLNode* left;
    struct AVLNode* right;
    int height;
};

我们定义了一个结构体 `AVLNode` 表示AVL树节点。其中 `data` 表示节点的数据，`left` 表示左子节点，`right` 表示右子节点，`height` 表示节点的高度。

2. 计算节点高度

int height(struct AVLNode* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

我们定义了一个 `height` 函数，用于计算节点的高度。若节点为空，返回0，否则返回节点的 `height` 成员变量。

3. 计算节点平衡因子

int balanceFactor(struct AVLNode* node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

我们定义了一个 `balanceFactor` 函数，用于计算节点的平衡因子。平衡因子等于节点的左子树高度减去右子树高度。

4. 更新节点高度

void updateHeight(struct AVLNode* node) {
    node->height = 1 + max(height(node->left), height(node->right));
}

我们定义了一个 `updateHeight` 函数，用于更新节点的高度。节点的高度等于其左右子树高度的较大值加1。

5. 左旋转

struct AVLNode* leftRotate(struct AVLNode* node) {
    struct AVLNode* rightChild = node->right;
    struct AVLNode* leftGrandChild = rightChild->left;
    rightChild->left = node;
    node->right = leftGrandChild;
    updateHeight(node);
    updateHeight(rightChild);
    return rightChild;
}

我们定义了一个 `leftRotate` 函数，用于实现左旋转。左旋转操作将当前节点的右子节点变为新的根节点，当前节点变为新根节点的左子节点，而新根节点的左子节点变为当前节点的右子节点。然后更新当前节点和新根节点的高度，并返回新根节点。

6. 右旋转

struct AVLNode* rightRotate(struct AVLNode* node) {
    struct AVLNode* leftChild = node->left;
    struct AVLNode* rightGrandChild = leftChild->right;
    leftChild->right = node;
    node->left = rightGrandChild;
    updateHeight(node);
    updateHeight(leftChild);
    return leftChild;
}

我们定义了一个 `rightRotate` 函数，用于实现右旋转。右旋转操作将当前节点的左子节点变为新的根节点，当前节点变为新根节点的右子节点，而新根节点的右子节点变为当前节点的左子节点。然后更新当前节点和新根节点的高度，并返回新根节点。

7. 插入节点

struct AVLNode* insert(struct AVLNode* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    updateHeight(root);
    int balance = balanceFactor(root);
    if (balance > 1 && data < root->left->data) {
        return rightRotate(root);
    }
    if (balance < -1 && data > root->right->data) {
        return leftRotate(root);
    }
    if (balance > 1 && data > root->left->data) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balance < -1 && data < root->right->data) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

我们定义了一个 `insert` 函数，用于向AVL树插入一个节点。若树为空，则直接返回一个新节点。若待插入节点的值小于当前节点的值，则递归插入当前节点的左子树，否则递归插入当前节点的右子树。然后更新当前节点的高度，并计算平衡因子。若平衡因子大于1且待插入节点的值小于当前节点的左子节点的值，则进行右旋转；若平衡因子小于-1且待插入节点的值大于当前节点的右子节点的值，则进行左旋转；若平衡因子大于1且待插入节点的值大于当前节点的左子节点的值，则先进行左旋转再进行右旋转；若平衡因子小于-1且待插入节点的值小于当前节点的右子节点的值，则先进行右旋转再进行左旋转。最后返回根节点。

8. 删除节点

struct AVLNode* delete(struct AVLNode* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = delete(root->left, data);
    } else if (data > root->data) {
        root->right = delete(root->right, data);
    } else {
        if (root->left == NULL || root->right == NULL) {
            struct AVLNode* temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else {
                *root = *temp;
            }
            free(temp);
        } else {
            struct AVLNode* temp = minValueNode(root->right);
            root->data = temp->data;
            root->right = delete(root->right, temp->data);
        }
    }
    if (root == NULL) {
        return root;
    }
    updateHeight(root);
    int balance = balanceFactor(root);
    if (balance > 1 && balanceFactor(root->left) >= 0) {
        return rightRotate(root);
    }
    if (balance > 1 && balanceFactor(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balance < -1 && balanceFactor(root->right) <= 0) {
        return leftRotate(root);
    }
    if (balance < -1 && balanceFactor(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

我们定义了一个 `delete` 函数，用于删除AVL树中的一个节点。若树为空，则直接返回。若待删除节点的值小于当前节点的值，则递归删除当前节点的左子树中的对应节点，否则递归删除当前节点的右子树中的对应节点。若待删除节点的左右子树都不为空，则在右子树中找到最小值节点，将其值赋给当前节点，然后递归删除右子树中的最小值节点。最后，必须更新当前节点的高度，并计算平衡因子。若平衡因子大于1且当前节点的左子树的平衡因子大于等于0，则进行右旋转；若平衡因子大于1且当前节点的左子树的平衡因子小于0，则先进行左旋转再进行右旋转；若平衡因子小于-1且当前节点的右子树的平衡因子小于等于0，则进行左旋转；若平衡因子小于-1且当前节点的右子树的平衡因子大于0，则先进行右旋转再进行左旋转。最后返回根节点。

9. 查找最小值节点

struct AVLNode* minValueNode(struct AVLNode* node) {
    struct AVLNode* current = node;
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}

我们定义了一个 `minValueNode` 函数，用于查找AVL树中的最小值节点。从当前节点开始，一直往左走，直到找到左子树为空的节点。最后返回该节点。

完整代码示例：