请用C语言写出, 给出一个按照“扩展遍历序列”的扩展先序遍历序列字符串,'.' 代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并计算及输出该二叉树的高度。
时间: 2023-06-08 11:06:20 浏览: 118
给定一个前序的字母字符串,并把它们创建成一个二叉树,并且遍历输出它的中序和后序
好的,我已经理解您的问题。针对您的问题,我可以提供以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
};
typedef struct TreeNode treeNode;
int get_height(treeNode *root);
treeNode *build_tree(char *str, int index, int length) {
treeNode *root = NULL;
if (index < length && str[index] != '.') {
root = (treeNode*)malloc(sizeof(treeNode));
root->val = str[index];
root->left = build_tree(str, 2 * index + 1, length);
root->right = build_tree(str, 2 * index + 2, length);
}
return root;
}
int main() {
char str[] = "AB..E.F..CG.H..";
int length = strlen(str);
treeNode *root = build_tree(str, 0, length);
printf("height=%d\n", get_height(root));
return 0;
}
int get_height(treeNode *root) {
if (root == NULL) {
return 0;
}
int left_height = get_height(root->left);
int right_height = get_height(root->right);
return (left_height > right_height ? left_height : right_height) + 1;
}
```
该代码可以按照您提供的“扩展遍历序列”,建立一棵二叉树,并计算并输出该二叉树的高度。
阅读全文