c++二叉排序树的查找算法代码实现

在C++中，二叉搜索树（Binary Search Tree，BST）的查找算法通常涉及递归或迭代的方式。以下是基于递归的基本查找算法的代码实现：

template <typename T>
struct TreeNode {
    T val;
    TreeNode<T> *left;
    TreeNode<T> *right;
    TreeNode(T x) : val(x), left(NULL), right(NULL) {}
};

template <typename T>
TreeNode<T>* search(TreeNode<T>* root, const T& target) {
    if (root == nullptr || root->val == target) {
        return root;
    }
    if (target < root->val) {
        return search(root->left, target);
    } else {
        return search(root->right, target);
    }
}

在这个代码中，`search`函数接受一个根节点和目标值作为输入。如果根节点为空或者根节点的值正好等于目标值，那么就找到了目标，返回当前节点。如果目标小于根节点的值，就在左子树中继续查找；反之，在右子树中查找。

相关问题

按以下要求写出代码，1、定义二叉排序树的查找算法函数。2、二叉排序树的插入算法函数。3、建立二叉排序树的插入算法。4、二叉排序树删除一个结点的操作实现。5、打印二叉排序树。

以下是基于 C++ 的代码实现，包括所需的数据结构和算法函数：

#include <iostream>

using namespace std;

// 定义二叉排序树的结点
struct BSTNode {
    int data;
    BSTNode* left;
    BSTNode* right;
};

// 查找算法函数
BSTNode* BSTSearch(BSTNode* root, int key) {
    if (root == nullptr || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return BSTSearch(root->left, key);
    }
    return BSTSearch(root->right, key);
}

// 插入算法函数
BSTNode* BSTInsert(BSTNode* root, int key) {
    if (root == nullptr) {
        root = new BSTNode;
        root->data = key;
        root->left = root->right = nullptr;
    } else if (key < root->data) {
        root->left = BSTInsert(root->left, key);
    } else {
        root->right = BSTInsert(root->right, key);
    }
    return root;
}

// 建立二叉排序树的插入算法
BSTNode* BSTCreate() {
    BSTNode* root = nullptr;
    int n;
    cout << "请输入结点个数: ";
    cin >> n;
    cout << "请输入" << n << "个结点的值: ";
    for (int i = 0; i < n; i++) {
        int key;
        cin >> key;
        root = BSTInsert(root, key);
    }
    return root;
}

// 二叉排序树删除一个结点的操作实现
BSTNode* BSTDelete(BSTNode* root, int key) {
    if (root == nullptr) {
        return root;
    }
    if (key < root->data) {
        root->left = BSTDelete(root->left, key);
    } else if (key > root->data) {
        root->right = BSTDelete(root->right, key);
    } else {
        if (root->left == nullptr) {
            BSTNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            BSTNode* temp = root->left;
            delete root;
            return temp;
        }
        BSTNode* temp = root->right;
        while (temp->left != nullptr) {
            temp = temp->left;
        }
        root->data = temp->data;
        root->right = BSTDelete(root->right, temp->data);
    }
    return root;
}

// 中序遍历打印二叉排序树
void BSTPrint(BSTNode* root) {
    if (root == nullptr) {
        return;
    }
    BSTPrint(root->left);
    cout << root->data << " ";
    BSTPrint(root->right);
}

int main() {
    BSTNode* root = BSTCreate();
    cout << "建立的二叉排序树为: ";
    BSTPrint(root);

    int key;
    cout << "\n请输入要删除的结点的值: ";
    cin >> key;
    root = BSTDelete(root, key);
    cout << "删除结点 " << key << " 后的二叉排序树为: ";
    BSTPrint(root);

    return 0;
}

这个程序允许用户输入要插入的结点值，然后建立一个二叉排序树。用户可以输入一个要删除的结点的值，如果该值存在于树中，则将其删除。最后，程序打印剩余的二叉排序树。

（1）编写顺序表的查找算法 （2）编写折半查找算法。 （3）编写二叉排序树查找算法。

(1) 顺序表的查找算法可以使用线性查找，具体步骤如下：

1. 从表头开始遍历顺序表，依次将每个元素与待查找元素进行比较。
2. 若找到待查找元素，返回其在顺序表中的下标。
3. 若遍历完整个顺序表仍未找到待查找元素，返回-1表示查找失败。

以下是使用C++实现线性查找的示例代码：

int search(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

(2) 折半查找算法是一种效率更高的查找算法，前提是顺序表是有序的。具体步骤如下：

1. 将待查找区间的中间位置作为起始点mid。
2. 将mid位置的元素与待查找元素进行比较。
3. 若mid位置的元素等于待查找元素，则返回mid。
4. 若mid位置的元素大于待查找元素，则在mid左侧的区间中继续查找，重复步骤1~3。
5. 若mid位置的元素小于待查找元素，则在mid右侧的区间中继续查找，重复步骤1~3。
6. 若查找区间为空，则返回-1表示查找失败。

以下是使用C++实现折半查找的示例代码：

int binarySearch(int arr[], int n, int x) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] > x) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

(3) 二叉排序树查找算法是一种基于二叉排序树的查找算法，具体步骤如下：

1. 根据待查找元素的大小关系，从根节点开始递归查找。
2. 若当前节点为空，则返回-1表示查找失败。
3. 若当前节点的值等于待查找元素，则返回当前节点的值。
4. 若当前节点的值大于待查找元素，则继续递归查找当前节点的左子树。
5. 若当前节点的值小于待查找元素，则继续递归查找当前节点的右子树。

以下是使用C++实现二叉排序树查找的示例代码：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int search(TreeNode* root, int x) {
    if (root == NULL) {
        return -1;
    }
    if (root->val == x) {
        return root->val;
    } else if (root->val > x) {
        return search(root->left, x);
    } else {
        return search(root->right, x);
    }
}