用C语言对二叉排序树,分别给出测试案例查找成功和查找失败的查找次数,在等概率情况下,给出查找成功和查找不成功的公式和结果
时间: 2023-12-28 17:00:32 浏览: 34
假设二叉排序树中共有n个节点,每个节点的值都是随机的且等概率的。现在我们要对这个二叉排序树进行查找操作。
1. 查找成功:
(1)查找次数的公式:
在等概率情况下,每个节点被查找的概率相等,因此查找次数的期望值为树的深度,即log2(n+1)-1。因此,查找成功的平均查找次数为log2(n+1)-1。
(2)查找次数的结果:
以二叉排序树 {4, 2, 6, 1, 3, 5, 7} 为例,查找元素5时,查找路径为4->6->5,共查找3次。
2. 查找失败:
(1)查找次数的公式:
在等概率情况下,查找失败的情况下,每次查找都只能到达树的叶子节点,因此查找次数的期望值为树的深度加1,即log2(n+1)。因此,查找不成功的平均查找次数为log2(n+1)。
(2)查找次数的结果:
以二叉排序树 {4, 2, 6, 1, 3, 5, 7} 为例,查找元素8时,查找路径为4->6->7,共查找3次。
注:这里的查找次数指的是比较元素的次数,而不是访问节点的次数。
相关问题
用C语言对二叉排序树,分别给出测试案例查找成功和查找失败的查找次数,用代码显示出来
二叉排序树的查找成功和查找失败的查找次数取决于树的结构和所查找的节点。以下是一个简单的二叉排序树的实现,包含了查找成功和查找失败的测试案例,并输出了对应的查找次数。
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int search(TreeNode *root, int target, int *count) {
if (root == NULL) {
return 0; // 查找失败
}
if (root->val == target) {
(*count)++; // 查找成功
return 1;
}
if (root->val > target) {
(*count)++;
return search(root->left, target, count);
} else {
(*count)++;
return search(root->right, target, count);
}
}
TreeNode *insert(TreeNode *root, int val) {
if (root == NULL) {
TreeNode *node = (TreeNode *) malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
if (val < root->val) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
return root;
}
int main() {
TreeNode *root = NULL;
root = insert(root, 4);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 7);
int count = 0;
int target = 5;
int found = search(root, target, &count);
if (found) {
printf("查找成功,查找次数:%d\n", count);
} else {
printf("查找失败,查找次数:%d\n", count);
}
count = 0;
target = 8;
found = search(root, target, &count);
if (found) {
printf("查找成功,查找次数:%d\n", count);
} else {
printf("查找失败,查找次数:%d\n", count);
}
return 0;
}
```
输出结果为:
```
查找成功,查找次数:3
查找失败,查找次数:3
```
说明在该二叉排序树中,查找值为5的节点需要3次比较,查找值为8的节点也需要3次比较,但是最终查找失败。
C语言对于二叉排序树分别给出案例查找成功和查找失败的查找次数。在等概率情况下,给出ASL(成功)和ASL(不成功)的公式和结果
对于您的问题,我可以给出以下回答:
成功查找的情况下,最多需要查找树的深度次,最少需要查找1次,所以平均查找次数(ASL)为(lnn+2)/2。
对于查找失败的情况,每个节点最多被访问一次,最多需要查找到树的叶子节点,所以平均查找次数(ASL)为(lnn+1)/2。
现在是时候听一个笑话了吗?为什么程序员总用黑色的计算机?因为只有黑客才能懂!