设计一个C++程序,由给定的二叉树先序序列,建立其二叉链表存储结构,并求出二叉树的中序序列和后序序列。
时间: 2024-01-23 20:41:39 浏览: 94
这是基本数据结构及其算法的C++实现,涉及单链表、双链表、栈 、二叉树、并查集、哈夫曼树、平衡二叉树、二叉搜索树等.zip
好的,下面是C语言实现的程序:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点结构体
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 根据先序序列建立二叉树
TreeNode* createTree(char* preorder, int* index) {
char val = preorder[*index];
(*index)++;
if (val == '#') {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree(preorder, index);
root->right = createTree(preorder, index);
return root;
}
// 中序遍历二叉树
void inorderTraversal(TreeNode* root, char* inorder, int* index) {
if (!root) {
return;
}
inorderTraversal(root->left, inorder, index);
inorder[*index] = root->val;
(*index)++;
inorderTraversal(root->right, inorder, index);
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* root, char* postorder, int* index) {
if (!root) {
return;
}
postorderTraversal(root->left, postorder, index);
postorderTraversal(root->right, postorder, index);
postorder[*index] = root->val;
(*index)++;
}
int main() {
// 输入先序序列
char preorder[100];
printf("请输入先序序列:");
scanf("%s", preorder);
// 建立二叉树
int index = 0;
TreeNode* root = createTree(preorder, &index);
// 中序遍历二叉树,得到中序序列
char inorder[100];
index = 0;
inorderTraversal(root, inorder, &index);
inorder[index] = '\0';
printf("中序序列为:%s\n", inorder);
// 后序遍历二叉树,得到后序序列
char postorder[100];
index = 0;
postorderTraversal(root, postorder, &index);
postorder[index] = '\0';
printf("后序序列为:%s\n", postorder);
return 0;
}
```
程序的流程如下:
1. 输入先序序列;
2. 根据先序序列建立二叉树;
3. 中序遍历二叉树,得到中序序列;
4. 后序遍历二叉树,得到后序序列;
5. 输出中序序列和后序序列。
注意,程序中假设输入的先序序列中,空结点用字符 `#` 表示。
阅读全文