c语言二叉树排序
时间: 2023-10-03 18:09:15 浏览: 45
二叉树排序是一种基于二叉树数据结构的排序算法,其基本原理是将待排序元素按照一定的规则插入到一棵空的二叉树中,然后按照中序遍历的顺序将元素输出,即可得到有序的序列。
下面是使用C语言实现二叉树排序的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 向二叉树中插入一个元素
TreeNode* insert(TreeNode* root, int val) {
if (root == NULL) {
root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = NULL;
root->right = NULL;
} else if (val < root->val) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
return root;
}
// 中序遍历二叉树,输出有序序列
void inorder(TreeNode* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
}
int main() {
TreeNode* root = NULL;
int n, val;
printf("请输入待排序元素的个数:");
scanf("%d", &n);
printf("请输入待排序的元素:");
for (int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
printf("排序后的序列为:");
inorder(root);
printf("\n");
return 0;
}
```
在上面的代码中,我们定义了一个二叉树结构体 TreeNode,其中包含节点的值 val,以及左右子节点的指针 left 和 right。insert 函数用于向二叉树中插入一个元素,它的实现过程就是将待插入元素与当前节点的值进行比较,如果小于当前节点的值,则递归地将元素插入到当前节点的左子树中,否则递归地将元素插入到当前节点的右子树中。inorder 函数用于中序遍历二叉树,并输出有序序列。
最后,在 main 函数中,我们先读入待排序元素的个数,然后逐个读入元素并插入到二叉树中,最后调用 inorder 函数输出排序后的序列。