1.利用二叉树的扩展遍历序列生成二叉树,并将二叉树的三种遍历序列全部输出;
时间: 2023-06-22 09:21:57 浏览: 68
二叉树的扩展遍历序列是一种特殊的遍历方式,可以通过该序列构建出唯一的二叉树。具体步骤如下:
1. 首先,读入扩展遍历序列。
2. 创建一个栈,用于存储节点。
3. 从左到右遍历扩展遍历序列中的字符:
a. 如果遇到一个节点值,则创建一个新节点,并将该节点的左右子节点指针赋值为 NULL,然后将该节点入栈。
b. 如果遇到一个字符“#”,则弹出栈顶节点,并将该节点的右子节点指针赋值为栈顶节点,然后再弹出栈顶节点,并将该节点的左子节点指针赋值为栈顶节点,最后将该节点入栈。
4. 最后,栈中剩余的节点就是根节点。
下面是一个示例代码,可以生成二叉树并输出其前序、中序、后序遍历序列:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char value;
struct node* left;
struct node* right;
} Node;
Node* build_tree(char* str) {
Node* root = NULL;
Node* stack[100];
int top = -1;
int i = 0;
while (str[i] != '\0') {
if (str[i] != '#') {
Node* node = (Node*)malloc(sizeof(Node));
node->value = str[i];
node->left = NULL;
node->right = NULL;
stack[++top] = node;
} else {
Node* right = stack[top--];
Node* left = stack[top--];
Node* node = stack[++top];
node->value = '#';
node->left = left;
node->right = right;
if (top == 0) {
root = node;
} else {
stack[top - 1]->left = node;
}
}
i++;
}
return root;
}
void preorder(Node* root) {
if (root != NULL) {
printf("%c ", root->value);
preorder(root->left);
preorder(root->right);
}
}
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%c ", root->value);
inorder(root->right);
}
}
void postorder(Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%c ", root->value);
}
}
int main() {
char str[] = "ABD##E##CF###";
Node* root = build_tree(str);
printf("Preorder traversal: ");
preorder(root);
printf("\nInorder traversal: ");
inorder(root);
printf("\nPostorder traversal: ");
postorder(root);
printf("\n");
return 0;
}
```
输出结果为:
```
Preorder traversal: A B D E C F
Inorder traversal: D B E A F C
Postorder traversal: D E B F C A
```