本题目要求用先序序列和后序序列构造一棵正则二叉树(树中结点个数不超过10个),并输出其中序序列。 c语言实现
时间: 2024-05-01 12:19:36 浏览: 56
我明白了,您想要用先序序列和后序序列构造一棵正则二叉树,并输出其中序序列,这是一个经典的问题。以下是 C 语言实现的代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void inorder(TreeNode *t) {
if (t != NULL) {
inorder(t->left);
printf("%c ", t->data);
inorder(t->right);
}
}
TreeNode *buildTree(char *pre, char *post, int n) {
if (n == 0) {
return NULL;
}
TreeNode *t = (TreeNode *) malloc(sizeof(TreeNode));
t->data = *pre;
if (n == 1) {
t->left = NULL;
t->right = NULL;
return t;
}
int i;
for (i = 0; i < n; i++) {
if (*(post + i) == *(pre + 1)) {
break;
}
}
t->left = buildTree(pre + 1, post, i + 1);
t->right = buildTree(pre + i + 2, post + i + 1, n - i - 2);
return t;
}
int main() {
int n;
char pre[MAX_SIZE], post[MAX_SIZE];
printf("Enter the number of nodes (<= 10): ");
scanf("%d", &n);
printf("Enter the preorder traversal: ");
scanf("%s", pre);
printf("Enter the postorder traversal: ");
scanf("%s", post);
TreeNode *root = buildTree(pre, post, n);
printf("Inorder traversal: ");
inorder(root);
return 0;
}
```
在程序中,`buildTree` 函数用于构造二叉树,`inorder` 函数用于输出其中序序列。详细代码解释请见注释。这是一个经典问题,希望能对您有所帮助!
阅读全文