c语言写一个二叉树的先序,中序,后序遍历要求采用递归的算法
时间: 2023-10-19 09:02:46 浏览: 92
C语言实现二叉树的前序、中序、后续遍历(递归法)
好的,我可以回答这个问题。下面是使用递归算法来实现二叉树的先序、中序、后序遍历的c语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node, *Tree;
// 先序遍历
void preOrder(Tree tree) {
if (tree != NULL) {
printf("%d ", tree->data);
preOrder(tree->left);
preOrder(tree->right);
}
}
// 中序遍历
void inOrder(Tree tree) {
if (tree != NULL) {
inOrder(tree->left);
printf("%d ", tree->data);
inOrder(tree->right);
}
}
// 后序遍历
void postOrder(Tree tree) {
if (tree != NULL) {
postOrder(tree->left);
postOrder(tree->right);
printf("%d ", tree->data);
}
}
// 创建二叉树
Tree createTree(void) {
Node *node;
int data;
scanf("%d", &data);
if (data == -1) { // -1表示该节点为空
node = NULL;
} else {
node = (Node *)malloc(sizeof(Node));
if (node == NULL) {
printf("创建节点失败\n");
return NULL;
}
node->data = data;
node->left = createTree();
node->right = createTree();
}
return node;
}
int main() {
Tree tree;
printf("请输入二叉树中各个节点的值(-1表示该节点为空):\n");
tree = createTree();
printf("\n先序遍历结果:");
preOrder(tree);
printf("\n中序遍历结果:");
inOrder(tree);
printf("\n后序遍历结果:");
postOrder(tree);
return 0;
}
```
以上代码中,我们定义了 `Node` 结构体表示节点,`Tree` 实际上就是二叉树的根节点。通过 `createTree` 函数创建二叉树,用户需要输入各个节点的值,-1 表示为空。三个遍历函数 `preOrder` 、`inOrder` 和 `postOrder` 分别实现了先序、中序、后序遍历的递归算法。在 `main` 函数中先创建二叉树,然后依次调用三个遍历函数即可。
阅读全文