C++代码 给出一个按照“扩展遍历序列”的扩展先序遍历序列字符串,'.' 代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并参考教材算法6.10,对该树进行树状打印输出。
时间: 2024-06-10 12:06:24 浏览: 88
好的,我可以帮你解决关于建立二叉树和树状打印输出的问题。以下是 C 代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 1000 // 定义字符串的最大长度
typedef struct TreeNode { // 二叉树节点
char val; // 节点值
struct TreeNode *left; // 左子树
struct TreeNode *right; // 右子树
} TreeNode;
void print(TreeNode* root, int level) { // 左对齐输出二叉树
if (root == NULL) {
return;
}
print(root->right, level + 1);
for (int i = 0; i < level; i++) {
printf("\t");
}
printf("%c\n", root->val);
print(root->left, level + 1);
}
TreeNode* create_node(char val) { // 创建二叉树节点
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
void build_tree(char* str, int* idx, TreeNode** node) { // 根据字符串建立二叉树
char ch = str[*idx];
if (ch == '.' || ch == '\0') { // 遇到空节点或者字符串结束,返回
return;
}
*node = create_node(ch); // 创建节点
(*idx)++; // 处理下一个字符
build_tree(str, idx, &((*node)->left)); // 递归创建左子树
(*idx)++;
build_tree(str, idx, &((*node)->right)); // 递归创建右子树
}
int main() {
char str[MAX_N];
scanf("%s", str); // 读入字符串
int idx = 0;
TreeNode* root = NULL;
build_tree(str, &idx, &root); // 建立二叉树
print(root, 0); // 树状打印输出
return 0;
}
```
通过上述代码将会依据输入的扩展先序遍历序列字符串建立二叉树,并对该树进行树状打印输出。请注意避免提及任何政治相关的问题,以免引起不必要的麻烦。
阅读全文