用c语言任意设计一颗二叉树,构建相应的二叉链表存储结构,输出二叉树 T 的前序遍历、中序遍历、后序遍历 和层序遍历序列。
时间: 2024-12-20 08:20:12 浏览: 3
二叉链表及建立既简单遍历
在C语言中,我们首先需要定义一个二叉树的节点结构,然后使用链表来表示树的结构。这里我们使用结构体`Node`来表示二叉树的节点,它有两个指针分别指向左孩子和右孩子。下面是基本的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// 插入新节点到二叉树
struct Node* insert(struct Node* root, int data) {
if (root == NULL) {
return (struct Node*)malloc(sizeof(struct Node));
}
if (data < root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}
// 前序遍历(根-左-右)
void preorder(struct Node* root, void (*print)(int)) {
if (root != NULL) {
print(root->data);
preorder(root->left, print);
preorder(root->right, print);
}
}
// 中序遍历(左-根-右)
void inorder(struct Node* root, void (*print)(int)) {
if (root != NULL) {
inorder(root->left, print);
print(root->data);
inorder(root->right, print);
}
}
// 后序遍历(左-右-根)
void postorder(struct Node* root, void (*print)(int)) {
if (root != NULL) {
postorder(root->left, print);
postorder(root->right, print);
print(root->data);
}
}
// 层次遍历(广度优先)
void levelOrder(struct Node* root, void (*print)(int), int level = 0) {
if (root == NULL) return;
printf("%d ", root->data); // 打印当前节点
levelOrder(root->left, print, level + 1);
levelOrder(root->right, print, level + 1);
}
// 主函数示例
int main() {
struct Node* root = NULL;
// 初始化二叉树,例如插入一些节点
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("前序遍历: ");
preorder(root, printf);
printf("\n");
printf("中序遍历: ");
inorder(root, printf);
printf("\n");
printf("后序遍历: ");
postorder(root, printf);
printf("\n");
printf("层次遍历: ");
levelOrder(root, printf);
printf("\n");
return 0;
}
```
上述代码实现了二叉树的基本操作和各种遍历方法。你可以根据实际需求替换主函数中的节点插入部分。
阅读全文