将字符串排序建成二叉排序树并计算平均查长度应用题
题意：给定一个字符串,将其中的每个字符作为一个节点构建一个二叉排序树,并计算平均查长度。
思路：首先将字符串中的每个字符取出来,并按照字典序进行排序,将它们依次插入到二叉排序树中,最终得到一个排好序的二叉排序树。然后,通过遍历二叉树来计算平均查长度。
具体实现：
1.定义二叉排序树节点的结构体,包含字符数据和左右子树指针：
```C++
typedef struct Node {
    char data;
    struct Node* leftChild;
    struct Node* rightChild;
}Node;
```
2.定义一个insert函数,将每个字符插入到二叉排序树中：
```C++
Node* insert(Node* root, char data) {
    if (root == nullptr) {
        root = new Node();
        root->data = data;
        root->leftChild = nullptr;
        root->rightChild = nullptr;
    } else {
        if (data < root->data) {
            root->leftChild = insert(root->leftChild, data);
        } else if (data > root->data) {
            root->rightChild = insert(root->rightChild, data);
        }
    }
    return root;
}
字符串长度排序
```
3.定义一个getDepth函数,用来计算树的深度：
```C++
int getDepth(Node* root) {
    if (root == nullptr) {
        return 0;
    } else {
        int leftDepth = getDepth(root->leftChild);
        int rightDepth = getDepth(root->rightChild);
        return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
    }
}
```
4.定义一个dfs函数,用来遍历二叉树并计算查长度：
```C++
void dfs(Node* root, int depth, int& sum) {
    if (root == nullptr) {  // 达到叶子结点,将该路径长度加到sum上
        sum += depth;
        return;
    }
    dfs(root->leftChild, depth + 1, sum);  // 递归遍历左右子树
    dfs(root->rightChild, depth + 1, sum);
}
```
5.最后,将每个字符插入到二叉排序树中,并调用dfs函数计算平均查长度：
```C++
int main() {
    string s = "abcfedg";
    int n = s.size();
    Node* root = nullptr;
    for (int i = 0; i < n; i++) {
        root = insert(root, s[i]);
    }
    int depth = getDepth(root);  // 计算树的深度
    int sum = 0;
    dfs(root, 0, sum);  // 遍历二叉树并计算查长度
    double avgLen = sum / (double)n;
    cout << "平均查长度为：" << avgLen << endl;
    return 0;
}
```
输出结果：
```C++
平均查长度为：3.42857
```
因此,对于给定的字符串"abcfedg",将它们插入到二叉排序树中并遍历计算平均查长度,结果为3.42857。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。