二叉排序树的递归查找算法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);
}

相关问题

用数据结构C语言在二叉链表上完成二叉排序树的插入、创建和递归查找算法的实现完整代码

// 二叉排序树的结点结构
typedef int ElemType;
typedef struct BSTNode {
    ElemType key;
    struct BSTNode *lchild, *rchild;
} *BSTree, BSTNode;

// 二叉排序树的插入
void InsertBST(BSTree &T, ElemType key) {
    if (T == NULL) {
        T = (BSTree)malloc(sizeof(BSTNode));
        T->key = key;
        T->lchild = T->rchild = NULL;
    } else if (key < T->key) {
        InsertBST(T->lchild, key);
    } else if (key > T->key) {
        InsertBST(T->rchild, key);
    }
}

// 二叉排序树的创建
void CreateBST(BSTree &T, ElemType keys[], int n) {
    T = NULL;
    for (int i = 0; i < n; i++) {
        InsertBST(T, keys[i]);
    }
}

// 二叉排序树的递归查找
BSTree SearchBST(BSTree T, ElemType key) {
    if (T == NULL || T->key == key) {
        return T;
    } else if (key < T->key) {
        return SearchBST(T->lchild, key);
    } else {
        return SearchBST(T->rchild, key);
    }
}

用C语言编写算法实现对依次输入的关键字序列建立二叉排序树，并能实现二叉排序树的查找、插入和删除运算。

好的，我可以为您解答这个问题。

首先，我们需要了解二叉排序树的概念。二叉排序树是一种特殊的二叉树，它的左子树中所有节点的关键字都小于根节点的关键字，而右子树中所有节点的关键字都大于根节点的关键字。因此，二叉排序树的中序遍历是一个递增的序列。

接下来，我们需要实现三个运算：查找、插入和删除。具体实现如下：

1. 查找

查找操作很简单，只需要从根节点开始，比较要查找的关键字和当前节点的关键字的大小关系，如果相等则返回该节点，否则递归地在左子树或右子树中查找。

struct TreeNode* search(struct TreeNode* root, int key) {
    if (root == NULL || root->key == key) {
        return root;
    }
    if (key < root->key) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

2. 插入

插入操作需要先查找要插入的位置，然后在该位置插入一个新节点。如果要插入的关键字已经存在，则不需要插入。

struct TreeNode* insert(struct TreeNode* root, int key) {
    if (root == NULL) {
        return createNode(key);
    }
    if (key < root->key) {
        root->left = insert(root->left, key);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
    }
    return root;
}

3. 删除

删除操作比较复杂，需要考虑删除节点的子树情况。如果要删除的节点没有子树，直接删除即可。如果要删除的节点只有一个子树，将该子树连接到删除节点的父节点上即可。如果要删除的节点有两个子树，需要找到该节点的中序遍历的后继节点，将后继节点的值复制到要删除的节点上，然后删除后继节点。

struct TreeNode* delete(struct TreeNode* root, int key) {
    if (root == NULL) {
        return root;
    }
    if (key < root->key) {
        root->left = delete(root->left, key);
    } else if (key > root->key) {
        root->right = delete(root->right, key);
    } else {
        if (root->left == NULL) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        struct TreeNode* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = delete(root->right, temp->key);
    }
    return root;
}

这样，我们就完成了二叉排序树的建立、查找、插入和删除操作的实现。完整代码如下：