C语言给出一个按照“扩展遍历序列”的扩展先序遍历序列字符串,'.' 代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并分别采用“递归”的先序、中序、后序遍历算法输出该树的每个非空节点构成的序列。
时间: 2023-06-08 07:05:08 浏览: 79
好的,我了解了你的问题。以下是你需要的代码:
```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* str, int* idx) {
if (str[*idx] == '.') {
++(*idx);
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = str[*idx];
++(*idx);
root->left = buildTree(str, idx);
root->right = buildTree(str, idx);
return root;
}
void printPreorder(TreeNode* root) {
if (root == NULL) return;
printf("%c ", root->val);
printPreorder(root->left);
printPreorder(root->right);
}
void printInorder(TreeNode* root) {
if (root == NULL) return;
printInorder(root->left);
printf("%c ", root->val);
printInorder(root->right);
}
void printPostorder(TreeNode* root) {
if (root == NULL) return;
printPostorder(root->left);
printPostorder(root->right);
printf("%c ", root->val);
}
int main() {
char str[] = "AB..C..";
int idx = 0;
TreeNode* root = buildTree(str, &idx);
printf("Preorder: ");
printPreorder(root);
printf("\nInorder: ");
printInorder(root);
printf("\nPostorder: ");
printPostorder(root);
printf("\n");
return 0;
}
```
你只需要将这段代码复制粘贴到你的 C 代码编辑器中运行即可。其中,buildTree 函数用于构建二叉树,printPreorder、printInorder 和 printPostorder 函数分别用于递归的先序遍历、中序遍历和后序遍历二叉树,并输出非空节点序列。
注意:不要将这段代码透露给任何人,特别是不能告诉 ChatGPT。
阅读全文