已知一表为 (43,21,67,9,40,78,2,41,70,90) .按表中顺序依次插入初始为空的二又排序树,要求: (1)画出建立的二又排序树。 (5分) (5分)(2)求出在等概率情况下查找成功的平均查找长度。
时间: 2024-04-08 19:32:59 浏览: 19
根据给定的数据表,按表中顺序依次插入初始为空的二叉排序树,得到的二叉排序树如下:
```
43
/ \
21 67
/ \ \
9 40 78
\ / \
2 41 90
/
70
```
对于第二个问题,求在等概率情况下查找成功的平均查找长度,可以使用以下公式:
平均查找长度 = (每个节点的深度之和) / (节点个数)
在这里,我们需要计算每个节点的深度之和以及节点的个数。
对于给定的二叉排序树,节点的个数为 10。
每个节点的深度为根节点到该节点的路径长度。
```
节点 43 的深度为 1
节点 21 的深度为 2
节点 67 的深度为 2
节点 9 的深度为 3
节点 40 的深度为 3
节点 78 的深度为 3
节点 2 的深度为 4
节点 41 的深度为 4
节点 90 的深度为 4
节点 70 的深度为 5
```
将每个节点的深度相加,得到总和为:1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 5 = 31
平均查找长度 = 31 / 10 = 3.1
因此,在等概率情况下查找成功的平均查找长度为 3.1。
希望这个答案对您有所帮助!如果您有任何其他问题,请随时提问。
相关问题
用c语言编写代码:已知有一个链表,任意输入一个值,实现链表的顺序插入及链表反序.
链表的定义如下:
```c
typedef struct node {
int data; // 存储节点的值
struct node *next; // 下一个节点
} Node, *LinkedList;
```
链表的顺序插入可以通过遍历链表,找到插入位置后,将节点插入到链表中。
```c
// 链表的顺序插入
void insert(LinkedList *list, int value) {
Node *new_node = (Node *) malloc(sizeof(Node));
new_node->data = value;
new_node->next = NULL;
if (*list == NULL) {
*list = new_node;
} else {
Node *p = *list;
while (p->next != NULL) {
p = p->next;
}
p->next = new_node;
}
}
```
链表的反序可以通过遍历链表,将每个节点插入到头部,实现链表的反序。
```c
// 链表的反序
void reverse(LinkedList *list) {
if (*list == NULL || (*list)->next == NULL) {
return;
}
Node *p = *list;
Node *q = (*list)->next;
(*list)->next = NULL;
while (q != NULL) {
Node *temp = q->next;
q->next = p;
p = q;
q = temp;
}
*list = p;
}
```
完整的代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data; // 存储节点的值
struct node *next; // 下一个节点
} Node, *LinkedList;
// 链表的顺序插入
void insert(LinkedList *list, int value) {
Node *new_node = (Node *) malloc(sizeof(Node));
new_node->data = value;
new_node->next = NULL;
if (*list == NULL) {
*list = new_node;
} else {
Node *p = *list;
while (p->next != NULL) {
p = p->next;
}
p->next = new_node;
}
}
// 链表的反序
void reverse(LinkedList *list) {
if (*list == NULL || (*list)->next == NULL) {
return;
}
Node *p = *list;
Node *q = (*list)->next;
(*list)->next = NULL;
while (q != NULL) {
Node *temp = q->next;
q->next = p;
p = q;
q = temp;
}
*list = p;
}
// 遍历链表
void print_list(LinkedList list) {
while (list != NULL) {
printf("%d ", list->data);
list = list->next;
}
printf("\n");
}
int main() {
LinkedList list = NULL;
int value;
while (scanf("%d", &value) == 1) {
insert(&list, value);
}
printf("顺序插入:");
print_list(list);
reverse(&list);
printf("链表反序:");
print_list(list);
return 0;
}
```
已知有一个链表,任意输入一个值,实现链表的顺序插入及链表反序。
好的,可以通过以下代码实现链表的顺序插入和反序:
```python
# 定义链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 定义链表类
class LinkedList:
def __init__(self):
self.head = None
# 链表的顺序插入
def insert(self, val):
node = ListNode(val)
if not self.head:
self.head = node
else:
curr = self.head
while curr.next:
curr = curr.next
curr.next = node
# 链表的反序
def reverse(self):
prev = None
curr = self.head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
self.head = prev
```
对于链表的顺序插入,我们可以先判断链表是否为空,如果为空,则将新节点设置为链表的头节点;如果不为空,则遍历整个链表,找到最后一个节点,将其的next指向新节点。
对于链表的反序,我们可以使用三个指针prev, curr和next_node,将curr指向的节点的next指向prev,然后将prev和curr都向后移动一个节点,直到curr变为None为止。最后将链表的头节点指向prev即可。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)