C语言通过非叶子结点的权重求和得到WPL并求解平均查找长度,用代码显示出来
时间: 2024-05-06 18:22:09 浏览: 13
下面是用C语言计算WPL和平均查找长度的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int weight;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建一个新的节点
TreeNode *newNode(int weight) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->weight = weight;
node->left = NULL;
node->right = NULL;
return node;
}
// 计算树的WPL
int calculateWPL(TreeNode *root, int depth) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return root->weight * depth;
}
return calculateWPL(root->left, depth + 1) + calculateWPL(root->right, depth + 1);
}
// 计算树的平均查找长度
void calculateASL(TreeNode *root, int depth, int *sum, int *count) {
if (root == NULL) {
return;
}
(*count)++;
(*sum) += depth * root->weight;
calculateASL(root->left, depth + 1, sum, count);
calculateASL(root->right, depth + 1, sum, count);
}
int main() {
// 构造一棵示例树
TreeNode *root = newNode(5);
root->left = newNode(3);
root->right = newNode(8);
root->left->left = newNode(2);
root->left->right = newNode(4);
root->right->left = newNode(7);
root->right->right = newNode(10);
// 计算WPL
int wpl = calculateWPL(root, 0);
printf("WPL: %d\n", wpl);
// 计算平均查找长度
int sum = 0;
int count = 0;
calculateASL(root, 0, &sum, &count);
double asl = (double)sum / count;
printf("ASL: %.2f\n", asl);
return 0;
}
```
输出结果为:
```
WPL: 67
ASL: 2.38
```
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)