怎样根据中序遍历输出先序和后序遍历结果,用C语言实现
时间: 2024-05-15 17:18:19 浏览: 73
可以使用递归的方式实现中序、先序和后序遍历的输出。代码如下:
```
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int value) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->value);
inorderTraversal(root->right);
}
}
void preorderTraversal(struct Node* root) {
if (root != NULL) {
printf("%d ", root->value);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
void postorderTraversal(struct Node* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->value);
}
}
int main() {
/*
* 构造如下二叉树:
* 1
* / \
* 2 3
* / \
* 4 5
*/
struct Node* root = createNode(1);
root->left = createNode(2);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right = createNode(3);
printf("中序遍历结果:");
inorderTraversal(root);
printf("\n");
printf("先序遍历结果:");
preorderTraversal(root);
printf("\n");
printf("后序遍历结果:");
postorderTraversal(root);
printf("\n");
return 0;
}
```
输出结果为:
```
中序遍历结果:4 2 5 1 3
先序遍历结果:1 2 4 5 3
后序遍历结果:4 5 2 3 1
```
其中,中序遍历输出结果为先左子树遍历,再根节点遍历,最后右子树遍历;先序遍历输出结果为先根节点遍历,再左子树遍历,最后右子树遍历;后序遍历输出结果为先左子树遍历,再右子树遍历,最后根节点遍历。
阅读全文