编写一个C语言程序,完成二叉树的先序创建、先序遍历、中序遍历、后序遍历等操作
时间: 2024-10-29 16:20:11 浏览: 26
在C语言中,我们可以使用结构体来表示二叉树节点,并分别编写函数来实现先序、中序和后序遍历。这里是一个简单的示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左子树指针
struct TreeNode* right; // 右子树指针
} TreeNode;
// 创建新节点
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 先序遍历(根-左-右)
void preOrderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// 中序遍历(左-根-右)
void inOrderTraversal(TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->val);
inOrderTraversal(root->right);
}
}
// 后序遍历(左-右-根)
void postOrderTraversal(TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->val);
}
}
int main() {
// 创建一个简单二叉树示例
TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
// 遍历方式选择
printf("Preorder traversal: ");
preOrderTraversal(root);
printf("\nInorder traversal: ");
inOrderTraversal(root);
printf("\nPostorder traversal: ");
postOrderTraversal(root);
return 0;
}
```
在这个示例中,我们首先定义了二叉树节点,然后实现了创建节点、先序、中序和后序遍历的函数。在`main`函数里,我们创建了一个简单的二叉树并演示了三种遍历方式。
阅读全文