依次输入表(30, 15, 28,20,24, 10, 12,68,35,50,46,55)中的元素,生成一棵二叉排序树,要 求: 1、试画出生成之后的二叉排序树。 2、对该二叉排序数作中根遍历,写出遍历序列。 3、编程构建一个二叉排宇树,并中根遍历验证上述结果。并写出c语言代码
时间: 2024-02-20 15:56:58 浏览: 11
1. 生成的二叉排序树如下图所示:
```
30
/ \
15 35
/ \ \
10 20 50
/ \ / \
12 24 46 55
\
68
```
2. 中根遍历序列为:10 12 15 20 24 30 35 46 50 55 68
3. 以下是构建二叉排序树并验证的 C 代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
void insert(struct TreeNode** root, int val) {
if (*root == NULL) {
*root = createNode(val);
}
else if (val < (*root)->val) {
insert(&((*root)->left), val);
}
else {
insert(&((*root)->right), val);
}
}
void inorderTraversal(struct TreeNode* root, int* result, int* index) {
if (root) {
inorderTraversal(root->left, result, index);
result[(*index)++] = root->val;
inorderTraversal(root->right, result, index);
}
}
int main() {
struct TreeNode* root = NULL;
int nums[] = { 30, 15, 28, 20, 24, 10, 12, 68, 35, 50, 46, 55 };
int len = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < len; i++) {
insert(&root, nums[i]);
}
int* result = (int*)malloc(len * sizeof(int));
int index = 0;
inorderTraversal(root, result, &index);
printf("中根遍历序列为:");
for (int i = 0; i < len; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}
```
输出结果为:中根遍历序列为:10 12 15 20 24 30 35 46 50 55 68,与中根遍历序列相同,验证成功。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)