用C语言实现编写函数,实现二叉树的先序、中序、后序遍历算法,并在主函数中调用函数遍历输出1中创建的二叉树的思路、源码及结论。
时间: 2024-03-23 19:36:51 浏览: 51
二叉树的非递归先序中序后序(数据结构和算法分析)
思路:
首先,我们需要定义一个二叉树的结构体,包含一个数据域和左右子树指针。然后,我们可以使用递归的方式来实现二叉树的遍历。
先序遍历的算法:先输出当前节点的值,再遍历左子树,最后遍历右子树。
中序遍历的算法:先遍历左子树,再输出当前节点的值,最后遍历右子树。
后序遍历的算法:先遍历左子树,再遍历右子树,最后输出当前节点的值。
源码:
```
#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;
}
```
结论:
通过以上代码,我们可以实现二叉树的先序、中序、后序遍历算法。在主函数中调用函数遍历输出二叉树的每个节点的值。
阅读全文