二叉排序树的查找、插入算法。（算法设计题）

题目：二叉排序树的查找、插入算法。（算法设计题）

二叉排序树是一种特殊的二叉树，它满足左子树所有节点的键值小于根节点的键值，右子树所有节点的键值大于根节点的键值。二叉排序树可以高效地支持查找、插入、删除等操作。

查找算法：从根节点开始，若当前节点的键值等于目标值，则返回该节点；若当前节点的键值大于目标值，则在左子树中继续查找；若当前节点的键值小于目标值，则在右子树中继续查找。若遍历到叶子节点还未找到，则说明目标值不存在于树中。

插入算法：从根节点开始，若当前节点为空，则将目标值插入该节点；若当前节点的键值等于目标值，则插入失败（节点已存在）；若当前节点的键值大于目标值，则在左子树中继续插入；若当前节点的键值小于目标值，则在右子树中继续插入。

相关问题

给定11个关键字序列22，66, 9，11，6，33，7，56，18，19，16试分别用二分查找（假设已排序）、二叉排序树查找（不做平衡）、散列查找的开地 址法(用线性探查法，模取13的HASH函数）和拉链法（模取7的HASH函数）)来实现查找的平均查找长度

首先，对于二分查找，需要将关键字序列进行排序。排序后，可以通过二分查找算法来查找具体的关键字。平均查找长度为log2(n)+1，其中n为关键字序列的长度。因此，对于长度为11的关键字序列，平均查找长度为4。

对于二叉排序树查找，可以将关键字序列依次插入到二叉排序树中。插入完成后，可以通过中序遍历的方式来查找具体的关键字。由于二叉排序树不一定是平衡的，因此平均查找长度的计算比较复杂，一般采用统计分析方法，平均查找长度的期望值为O(log n)。

对于散列查找的开地址法，可以通过取模取余来计算关键字的散列地址。当出现冲突时，可以通过线性探查法来解决。具体来说，如果散列地址已被占用，则向后依次探查，直到找到一个空地址。平均查找长度取决于散列函数的设计和关键字序列的分布情况，一般来说，平均查找长度为O(1)。

对于散列查找的拉链法，同样可以通过取模取余来计算关键字的散列地址。当出现冲突时，可以将该关键字插入到对应散列地址的链表中。平均查找长度取决于散列函数的设计和关键字序列的分布情况，一般来说，平均查找长度与链表长度有关，但由于散列函数的随机性，可以认为平均查找长度为O(1)。在本题中，模取7的HASH函数可能会导致一些链表过长，影响查找效率。

【问题描述】 以括号形式输入一棵二叉排序树，从键盘输入待查找的元素，并输出元素比较路径。 【输入形式】 从键盘输入一系列数据元素值，以-1作为结束。 输入待查找的元素值。 【输出形式】 以括号形式输出每插入一个数据之和的二叉排序树 输出查找路径 【样例输入】 4 10 0 1 8 6 3 5 3 7 -1 9 【样例输出 //依次以括号形式输出每插入一个数据之和的二叉排序树 4 4(,10) 4(0,10) 4(0(,1),10) 4(0(,1),10(8,)) 4(0(,1),10(8(6,),)) 4(0(,1(,3)),10(8(6,),)) 4(0(,1(,3)),10(8(6(5,),),)) 4(0(,1(,3)),10(8(6(5,),),)) 4(0(,1(,3)),10(8(6(5,7),),)) 4 10 8 //这一行是查找路径,写出上述问题的算法设计思路和解决的关键问题和求解过程中遇到的主要技术难点和小结；

【算法设计思路】

1. 定义二叉排序树结构体，包括元素值和左右子树指针；
2. 以递归方式，依次插入输入的数据元素值，构建二叉排序树；
3. 在插入过程中，记录每次插入后的树结构，并以括号形式输出；
4. 在查找过程中，比较查找元素值与根节点元素值大小，然后递归查找左子树或右子树，同时记录路径，并输出路径。

【解决的关键问题和求解过程中遇到的主要技术难点】

1. 关键问题：如何构建二叉排序树？

解决方法：采用递归方式，对于每个数据元素值，与当前节点进行比较，如果小于当前节点，递归插入左子树，否则递归插入右子树。

2. 关键问题：如何记录插入过程中的树结构，并以括号形式输出？

解决方法：在插入过程中，递归记录每个节点的左右子树，并以括号形式输出，即先输出当前节点值，再输出左括号，递归输出左子树，再输出逗号和右子树，再输出右括号。

3. 关键问题：如何查找指定元素并输出搜索路径？

解决方法：根据二叉排序树的性质，如果待查找元素小于当前节点，递归查找左子树，否则递归查找右子树。在递归过程中，记录搜索路径。如果找到待查找元素，输出搜索路径即可。

【算法实现】

#include <iostream>
using namespace std;

struct BSTNode{
    int data;
    BSTNode *left, *right;
};

void insert(BSTNode *&root, int x) {
    if (root == NULL) {
        root = new BSTNode;
        root->data = x;
        root->left = root->right = NULL;
        return;
    }
    if (x < root->data) {
        insert(root->left, x);
    } else {
        insert(root->right, x);
    }
}

void print(BSTNode *root) {
    if (root == NULL) return;
    cout << root->data;
    if (root->left != NULL || root->right != NULL) {
        cout << "(";
        print(root->left);
        if (root->right != NULL) {
            cout << ",";
            print(root->right);
        }
        cout << ")";
    }
}

bool search(BSTNode *root, int x, string &path) {
    if (root == NULL) {
        return false;
    }
    path += to_string(root->data) + " ";
    if (x == root->data) {
        return true;
    } else if (x < root->data) {
        return search(root->left, x, path);
    } else {
        return search(root->right, x, path);
    }
}

int main() {
    int x;
    BSTNode *root = NULL;
    while (cin >> x && x != -1) {
        insert(root, x);
        print(root);
        cout << endl;
    }
    cin >> x;
    string path = "";
    if (search(root, x, path)) {
        cout << path << endl;
    } else {
        cout << "Not found!" << endl;
    }
    return 0;
}

【小结】

本题实现了二叉排序树的构建和查找，并输出了插入过程中的树结构和查找路径。关键在于递归构建二叉排序树和递归查找元素，同时记录路径。