帮我用C语言编程实现二叉树的二叉链表数据结构定义,并创建一棵二叉树、采用先序遍历,中序遍历以及后序遍历,输出对应的三种遍历结果,二叉树可以用键盘输入储存。
时间: 2024-11-18 18:17:09 浏览: 0
在C语言中,我们可以使用结构体来定义二叉树节点及其关联的二叉链表。首先,我们定义一个二叉树节点结构:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点
typedef struct TreeNode {
int data; // 节点值
struct TreeNode* left; // 左子节点指针
struct TreeNode* right; // 右子节点指针
} Node;
// 创建一个新的节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 插入节点到二叉链表
void insertNode(Node** root, int value) {
if (*root == NULL) {
*root = createNode(value);
} else if (value < (*root)->data) {
insertNode(&(*root)->left, value);
} else {
insertNode(&(*root)->right, value);
}
}
// 先序遍历(根-左-右)
void preOrderTraversal(Node* node) {
if (node != NULL) {
printf("%d ", node->data); // 访问当前节点
preOrderTraversal(node->left); // 遍历左子树
preOrderTraversal(node->right); // 遍历右子树
}
}
// 中序遍历(左-根-右)
void inOrderTraversal(Node* node) {
if (node != NULL) {
inOrderTraversal(node->left); // 遍历左子树
printf("%d ", node->data); // 访问当前节点
inOrderTraversal(node->right); // 遍历右子树
}
}
// 后序遍历(左-右-根)
void postOrderTraversal(Node* node) {
if (node != NULL) {
postOrderTraversal(node->left); // 遍历左子树
postOrderTraversal(node->right); // 遍历右子树
printf("%d ", node->data); // 访问当前节点
}
}
int main() {
Node* root = NULL; // 初始为空
// 输入节点,假设用户通过标准输入
char input;
while ((input = getchar()) != EOF && input != '\n') {
insertNode(&root, input - '0');
}
// 打印先序遍历结果
printf("Preorder Traversal: ");
preOrderTraversal(root);
printf("\n");
// 打印中序遍历结果
printf("Inorder Traversal: ");
inOrderTraversal(root);
printf("\n");
// 打印后序遍历结果
printf("Postorder Traversal: ");
postOrderTraversal(root);
printf("\n");
return 0;
}
```
在这个示例中,程序首先接收用户从键盘输入的一系列数字作为节点值构建二叉树。然后分别执行先序、中序和后序遍历,并打印出相应的遍历结果。
阅读全文