用户输入前序序列和中序序列,输出后序序列,用数组存放/和\,并图形化打印出二叉树。用C语言写完整代码
时间: 2024-03-25 14:38:43 浏览: 50
二叉树的前序,中序,后序排列C语言程序
好的,我会尽力回答您的问题。与您之前的问题类似,这个问题也需要用到二叉树的知识。在本问题中,我们需要用到前序序列和中序序列来构建二叉树,并输出后序序列并图形化打印出二叉树,并用字符数组存放/和\来表示二叉树的边。
以下是完整代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 100
typedef struct Node {
char val;
struct Node *left;
struct Node *right;
} Node;
// 根据前序序列和中序序列构建二叉树
Node *buildTree(char *preorder, char *inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
Node *root = (Node *)malloc(sizeof(Node));
root->val = preorder[preStart];
int idx = inStart;
while (idx <= inEnd && inorder[idx] != preorder[preStart]) {
idx++;
}
root->left = buildTree(preorder, inorder, preStart + 1, preStart + idx - inStart, inStart, idx - 1);
root->right = buildTree(preorder, inorder, preStart + idx - inStart + 1, preEnd, idx + 1, inEnd);
return root;
}
// 输出后序序列
void postOrder(Node *root) {
if (root) {
postOrder(root->left);
postOrder(root->right);
printf("%c ", root->val);
}
}
// 打印二叉树
void printTree(Node *root, char tree[MAX_N][MAX_N], int x, int y) {
if (root) {
tree[x][y] = root->val;
if (root->left) {
tree[x + 1][y - 1] = '/';
printTree(root->left, tree, x + 2, y - 2);
}
if (root->right) {
tree[x + 1][y + 1] = '\\';
printTree(root->right, tree, x + 2, y + 2);
}
}
}
int main() {
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
Node *root = buildTree(preorder, inorder, 0, 6, 0, 6);
printf("后序序列:");
postOrder(root);
printf("\n");
char tree[MAX_N][MAX_N];
memset(tree, ' ', sizeof(tree));
printTree(root, tree, 0, MAX_N / 2);
for (int i = 0; i < MAX_N; i++) {
for (int j = 0; j < MAX_N; j++) {
printf("%c", tree[i][j]);
}
printf("\n");
}
return 0;
}
```
在上述代码中,我们首先定义了一个 `Node` 结构体,用于表示二叉树的节点。然后,我们定义了三个函数:
- `buildTree` 函数:根据前序序列和中序序列构建二叉树。
- `postOrder` 函数:输出后序序列。
- `printTree` 函数:打印二叉树。
在 `main` 函数中,我们定义了两个数组 `preorder` 和 `inorder`,分别表示前序序列和中序序列。然后,我们调用 `buildTree` 函数构建二叉树,并调用 `postOrder` 函数输出后序序列。接着,我们定义了一个二维字符数组 `tree`,用于存放二叉树的图形化表示。我们调用 `printTree` 函数填充 `tree` 数组,并打印出二叉树。注意,我们在打印二叉树时,需要将二维字符数组中的空格字符替换为空格符,以保证输出的格式正确。
希望这个代码能够对您有所帮助!
阅读全文