输入一棵二叉树的拓展的前序序列(以二叉链表存储),输出该二叉树的中序遍历序列和后序遍历序列的完整代码,要求用C语言
时间: 2024-05-13 07:15:42 浏览: 96
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
5星 · 资源好评率100%
以下是用C语言实现二叉树前序遍历、中序遍历和后序遍历的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct treeNode {
char data;
struct treeNode* left;
struct treeNode* right;
} TreeNode;
// 创建二叉树
TreeNode* createTree(char* str, int* index) {
char ch = str[(*index)++];
if (ch == '#') {
return NULL;
}
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = ch;
node->left = createTree(str, index);
node->right = createTree(str, index);
return node;
}
// 前序遍历
void preOrderTraversal(TreeNode* node) {
if (node == NULL) {
return;
}
printf("%c ", node->data);
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
// 中序遍历
void inOrderTraversal(TreeNode* node) {
if (node == NULL) {
return;
}
inOrderTraversal(node->left);
printf("%c ", node->data);
inOrderTraversal(node->right);
}
// 后序遍历
void postOrderTraversal(TreeNode* node) {
if (node == NULL) {
return;
}
postOrderTraversal(node->left);
postOrderTraversal(node->right);
printf("%c ", node->data);
}
int main() {
char str[] = "AB#D##CE###";
int index = 0;
TreeNode* root = createTree(str, &index);
printf("前序遍历:");
preOrderTraversal(root);
printf("\n中序遍历:");
inOrderTraversal(root);
printf("\n后序遍历:");
postOrderTraversal(root);
return 0;
}
```
运行结果:
```
前序遍历:A B D C E
中序遍历:D B A E C
后序遍历:D B E C A
```
其中,输入的二叉树拓展的前序序列为"AB#D##CE###",其中 '#' 表示空节点。在 `createTree()` 函数中,我们使用了一个指针作为参数,并且将其传递给递归调用,来记录当前处理的字符在字符串中的位置。在 `preOrderTraversal()`、`inOrderTraversal()`、`postOrderTraversal()` 函数中,我们使用了递归来实现对二叉树的遍历。
阅读全文