请用C语言给出一个按照“扩展遍历序列”的扩展先序遍历序列字符串,'.' 代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并计算及输出该二叉树的高度。
时间: 2023-06-07 21:12:14 浏览: 159
给定一个前序的字母字符串,并把它们创建成一个二叉树,并且遍历输出它的中序和后序
对于这个问题,我可以提供以下 C 语言代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100
// 定义二叉树结构体
typedef struct TreeNode {
char val; // 节点内容
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
// 创建二叉树
TreeNode* createTree(char *s, int *pos) {
if (s[*pos] == '.') { // 空节点返回 NULL
(*pos)++;
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode)); // 创建新节点
root->val = s[*pos];
(*pos)++;
root->left = createTree(s, pos); // 创建左子树
root->right = createTree(s, pos); // 创建右子树
return root;
}
// 计算二叉树高度
int countHeight(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftHeight = countHeight(root->left); // 左子树高度
int rightHeight = countHeight(root->right); // 右子树高度
return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1; // 取更高的那个子树高度
}
int main() {
char s[MAX_LEN];
fgets(s, MAX_LEN, stdin); // 读入扩展先序遍历字符串
int len = strlen(s);
s[len - 1] = '\0'; // 把换行符删除
int pos = 0;
TreeNode *root = createTree(s, &pos); // 创建二叉树
int height = countHeight(root); // 计算高度
printf("%d\n", height);
return 0;
}
请将上述代码复制到 C 语言编译器中编译运行,输入扩展先序遍历序列后即可输出该二叉树的高度。
阅读全文