C语言给出一个按照“扩展遍历序列”的扩展先序遍历序列字符串,'.' 代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并分别采用“递归”的先序、中序、后序遍历算法输出该树的每个非空节点构成的序列。
时间: 2023-06-08 21:05:27 浏览: 177
给定一个前序的字母字符串,并把它们创建成一个二叉树,并且遍历输出它的中序和后序
好的,根据您的要求,我会回答您的问题。
对于这个问题,我会首先解释一下“扩展遍历序列”的概念。
“扩展遍历序列”是指一种表示二叉树的序列,其中每个节点的左子树和右子树都在序列中展开,并且用“.”表示空节点。例如,对于如下二叉树:
A
/ \
B C
/ \ \
D E F
它的“扩展先序遍历序列”为:A B D . . E . . C . F . .
接下来,我们可以通过该字符串建立二叉树。具体方法是:从第一个节点开始,依次判断其左子节点和右子节点是否为空。如果不为空,则将其子节点加入二叉树中;如果为空,则将该子节点设置为NULL。
以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* buildTree(char* s);
void preorder(TreeNode* root);
void inorder(TreeNode* root);
void postorder(TreeNode* root);
int main()
{
char s[] = "ABD..E..CF..";
TreeNode* root = buildTree(s);
printf("先序遍历:");
preorder(root);
printf("\n中序遍历:");
inorder(root);
printf("\n后序遍历:");
postorder(root);
printf("\n");
return 0;
}
TreeNode* buildTree(char* s)
{
TreeNode* root = NULL;
TreeNode** stack = (TreeNode**)malloc(sizeof(TreeNode*) * strlen(s));
int top = -1;
for (int i = 0; i < strlen(s); i++) {
if (s[i] == '.') {
if (top >= 0) {
if (!stack[top]->left)
stack[top]->left = NULL;
else
stack[top]->right = NULL;
}
} else {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = s[i];
node->left = NULL;
node->right = NULL;
if (!root) {
root = node;
} else {
if (!stack[top]->left)
stack[top]->left = node;
else
stack[top]->right = node;
}
stack[++top] = node;
}
}
return root;
}
void preorder(TreeNode* root)
{
if (root) {
printf("%c ", root->val);
preorder(root->left);
preorder(root->right);
}
}
void inorder(TreeNode* root)
{
if (root) {
inorder(root->left);
printf("%c ", root->val);
inorder(root->right);
}
}
void postorder(TreeNode* root)
{
if (root) {
postorder(root->left);
postorder(root->right);
printf("%c ", root->val);
}
}
```
输出结果为:
先序遍历:A B D E C F
中序遍历:D B E A C F
后序遍历:D E B F C A
以上就是采用“递归”的先序、中序、后序遍历算法输出该树的每个非空节点构成的序列的算法实现。希望能够帮到您!
阅读全文