用户输入前序序列和中序序列,输出后序序列,并图形化打印出二叉树。用C语言写完整代码
时间: 2023-08-10 09:42:31 浏览: 108
好的,我会尽力回答您的问题。首先,需要明确的是,您的问题需要用到二叉树的知识。二叉树是一种常见的数据结构,它由节点和边组成。每个节点至多有两个子节点,分别称为左子节点和右子节点。在二叉树中,每个节点都有一个值,通常称为节点值。在本问题中,我们需要用到前序序列和中序序列来构建二叉树,并输出后序序列并图形化打印出二叉树。
以下是完整代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
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, int level) {
if (root) {
printTree(root->right, level + 1);
for (int i = 0; i < level; i++) {
printf(" ");
}
printf("%c\n", root->val);
printTree(root->left, level + 1);
}
}
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");
printf("二叉树:\n");
printTree(root, 0);
return 0;
}
```
在上述代码中,我们首先定义了一个 `Node` 结构体,用于表示二叉树的节点。然后,我们定义了三个函数:
- `buildTree` 函数:根据前序序列和中序序列构建二叉树。
- `postOrder` 函数:输出后序序列。
- `printTree` 函数:打印二叉树。
在 `main` 函数中,我们定义了两个数组 `preorder` 和 `inorder`,分别表示前序序列和中序序列。然后,我们调用 `buildTree` 函数构建二叉树,并调用 `postOrder` 函数输出后序序列。最后,我们调用 `printTree` 函数打印二叉树。
希望这个代码能够对您有所帮助!
阅读全文