编写一个建立如下图所示二叉树的程序,并分别按照前序遍历二叉树次序、中序遍历二叉树次序和后序遍历二叉树次序输出显示二叉树各结点的信息。
时间: 2023-12-10 12:33:29 浏览: 79
二叉树的三种遍历
4星 · 用户满意度95%
好的,建立二叉树的程序可以使用结构体来实现。以下是一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
char data; // 存储节点数据
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
char data;
scanf("%c", &data);
if (data == '#') { // 如果输入的是#,表示该节点为空
return NULL;
}
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode)); // 为节点分配内存空间
node->data = data;
node->left = createTree(); // 递归创建左子树
node->right = createTree(); // 递归创建右子树
return node;
}
// 前序遍历二叉树
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%c ", root->data); // 输出节点数据
preOrder(root->left); // 递归遍历左子树
preOrder(root->right); // 递归遍历右子树
}
// 中序遍历二叉树
void inOrder(TreeNode *root) {
if (root == NULL) {
return;
}
inOrder(root->left); // 递归遍历左子树
printf("%c ", root->data); // 输出节点数据
inOrder(root->right); // 递归遍历右子树
}
// 后序遍历二叉树
void postOrder(TreeNode *root) {
if (root == NULL) {
return;
}
postOrder(root->left); // 递归遍历左子树
postOrder(root->right); // 递归遍历右子树
printf("%c ", root->data); // 输出节点数据
}
int main() {
printf("请输入二叉树的节点信息,空节点用#表示:\n");
TreeNode *root = createTree(); // 创建二叉树
printf("前序遍历结果为:");
preOrder(root); // 前序遍历
printf("\n中序遍历结果为:");
inOrder(root); // 中序遍历
printf("\n后序遍历结果为:");
postOrder(root); // 后序遍历
printf("\n");
return 0;
}
```
在程序中,我们首先定义了一个二叉树的结构体,包含节点数据和左右子树指针。然后使用递归的方式创建二叉树,输入节点数据时,如果输入的是#,表示该节点为空。接着,我们分别实现了前序遍历、中序遍历和后序遍历的函数,这些函数都是递归实现的。最后在主函数中调用这些函数,输出遍历结果。
阅读全文