c语言完成用二叉链表作为存储结构,输入序列建立一棵二叉排序树,然后中序遍历这棵二叉树
时间: 2023-08-10 16:22:33 浏览: 114
头歌数据结构二叉树的二叉链表存储及基本操作
5星 · 资源好评率100%
好的,让我来简单介绍一下二叉排序树的概念和实现思路。
二叉排序树又称为二叉搜索树,是一种特殊的二叉树,它满足以下条件:
1. 对于任意结点,它的左子树中的所有结点的值都小于它的值;
2. 对于任意结点,它的右子树中的所有结点的值都大于它的值;
3. 左右子树都是二叉排序树。
根据这个定义,我们可以用二叉链表来实现一棵二叉排序树。具体实现思路如下:
1. 定义二叉树的结点类型,包括结点的值、左右子结点指针;
2. 定义一个函数,用于向二叉排序树中插入一个结点;
3. 读入一组序列,依次插入到二叉排序树中;
4. 中序遍历整棵二叉排序树,输出结点的值。
下面是具体的代码实现,你可以参考一下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点类型
typedef struct node {
int value;
struct node* left;
struct node* right;
} Node;
// 向二叉排序树中插入一个结点
Node* insert(Node* root, int value) {
if (root == NULL) {
// 如果当前结点为空,就创建一个新的结点
Node* node = (Node*)malloc(sizeof(Node));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
} else if (value < root->value) {
// 如果插入的值小于当前结点的值,就插入到左子树中
root->left = insert(root->left, value);
} else {
// 如果插入的值大于等于当前结点的值,就插入到右子树中
root->right = insert(root->right, value);
}
return root;
}
// 中序遍历二叉排序树
void inorder(Node* root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->value);
inorder(root->right);
}
int main() {
// 读入一组序列,依次插入到二叉排序树中
int n, value;
scanf("%d", &n);
Node* root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &value);
root = insert(root, value);
}
// 中序遍历整棵二叉排序树,输出结点的值
inorder(root);
return 0;
}
```
这样就完成了二叉排序树的建立和中序遍历。当然,这只是一个简单的实现,如果你想进一步了解二叉排序树的相关知识,可以参考一些经典的算法教材。
阅读全文