用C语言实现编写函数,实现二叉树的先序、中序、后序遍历算法,并在主函数中调用函数遍历输出1中创建的二叉树的思路、源码、运行结果及结论。
时间: 2024-03-23 09:36:52 浏览: 60
思路:
和上一个问题一样,我们需要定义一个二叉树的结构体,包含一个数据域和左右子树指针。然后,我们可以使用递归的方式来实现二叉树的遍历。
先序遍历的算法:先输出当前节点的值,再遍历左子树,最后遍历右子树。
中序遍历的算法:先遍历左子树,再输出当前节点的值,最后遍历右子树。
后序遍历的算法:先遍历左子树,再遍历右子树,最后输出当前节点的值。
源码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 先序遍历
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);
}
// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) return NULL;
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
return root;
}
int main() {
TreeNode *root = createTree();
printf("先序遍历:");
preorder(root);
printf("\n中序遍历:");
inorder(root);
printf("\n后序遍历:");
postorder(root);
return 0;
}
```
运行结果:
输入:1 2 -1 -1 3 4 -1 -1 5 -1 -1
输出:
```
先序遍历:1 2 3 4 5
中序遍历:2 1 4 3 5
后序遍历:2 4 5 3 1
```
结论:
通过以上代码,我们可以实现二叉树的先序、中序、后序遍历算法。在主函数中调用函数遍历输出二叉树的每个节点的值。从输出结果中可以看出,不同的遍历算法输出的结果顺序是不同的,这是因为不同的遍历算法遍历的顺序不同。
阅读全文