用c语言实现二叉树的各种遍历算法
时间: 2023-08-23 13:08:26 浏览: 44
二叉树的遍历算法主要分为三种:前序遍历、中序遍历和后序遍历。下面是用C语言实现这三种遍历算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) { // 如果遇到-1,表示这个节点为空,返回NULL
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
return root;
}
// 前序遍历
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%d ", root->val); // 先打印根节点的值
preOrder(root->left); // 递归遍历左子树
preOrder(root->right); // 递归遍历右子树
}
// 中序遍历
void inOrder(TreeNode *root) {
if (root == NULL) {
return;
}
inOrder(root->left); // 递归遍历左子树
printf("%d ", root->val); // 打印根节点的值
inOrder(root->right); // 递归遍历右子树
}
// 后序遍历
void postOrder(TreeNode *root) {
if (root == NULL) {
return;
}
postOrder(root->left); // 递归遍历左子树
postOrder(root->right); // 递归遍历右子树
printf("%d ", root->val); // 最后打印根节点的值
}
int main() {
TreeNode *root = createTree();
printf("前序遍历结果:");
preOrder(root);
printf("\n中序遍历结果:");
inOrder(root);
printf("\n后序遍历结果:");
postOrder(root);
printf("\n");
return 0;
}
```
注意,在创建二叉树时,我们约定输入-1表示这个节点为空;在遍历二叉树时,我们先打印根节点的值,然后递归遍历左子树和右子树。具体的实现可以参考上述代码。