c语言对一组输入数据构建相应的二叉排序树,并利用其中序遍历对数据进行升序排序
时间: 2023-06-15 19:08:26 浏览: 139
二叉排序树是一种特殊的二叉树,它满足以下性质:
1. 左子树所有节点的值都小于根节点的值;
2. 右子树所有节点的值都大于根节点的值;
3. 左右子树都是二叉排序树。
所以,我们可以按照以下步骤构建二叉排序树:
1. 定义二叉树节点的结构体,包括节点值、左右子节点指针。
2. 定义二叉排序树的根节点指针。
3. 读入输入数据,依次插入到二叉排序树中。
4. 对二叉排序树进行中序遍历,输出排序后的数据。
下面是一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点的结构体
typedef struct node {
int val;
struct node *left, *right;
} Node;
// 定义二叉排序树的根节点指针
Node *root = NULL;
// 二叉排序树插入节点
void insert(Node **node, int val) {
if (*node == NULL) {
*node = malloc(sizeof(Node));
(*node)->val = val;
(*node)->left = (*node)->right = NULL;
} else if (val < (*node)->val) {
insert(&((*node)->left), val);
} else if (val > (*node)->val) {
insert(&((*node)->right), val);
}
}
// 中序遍历二叉排序树
void inorder(Node *node) {
if (node != NULL) {
inorder(node->left);
printf("%d ", node->val);
inorder(node->right);
}
}
int main() {
int n, val;
printf("请输入数据个数:");
scanf("%d", &n);
printf("请输入 %d 个整数:", n);
for (int i = 0; i < n; i++) {
scanf("%d", &val);
insert(&root, val);
}
printf("排序后的数据为:");
inorder(root);
printf("\n");
return 0;
}
```
当输入数据为 `5 3 2 7 6 8` 时,输出如下:
```
请输入数据个数:6
请输入 6 个整数:5 3 2 7 6 8
排序后的数据为:2 3 5 6 7 8
```
阅读全文