请使用c语言实现上面要求
时间: 2023-08-20 18:07:34 浏览: 39
好的,请看下面的代码,这是一种基于递归的实现方式:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 50
typedef struct _Node {
char data;
struct _Node *left;
struct _Node *right;
} Node;
// 根据先序遍历和中序遍历构建二叉树
Node* build_tree(char *preorder, char *inorder, int len) {
if (len == 0) {
return NULL;
}
Node *root = (Node*)malloc(sizeof(Node));
root->data = preorder[0];
root->left = NULL;
root->right = NULL;
int i;
for (i = 0; i < len; i++) {
if (inorder[i] == preorder[0]) {
break;
}
}
root->left = build_tree(preorder+1, inorder, i);
root->right = build_tree(preorder+i+1, inorder+i+1, len-i-1);
return root;
}
// 计算二叉树的高度
int calc_height(Node *root) {
if (root == NULL) {
return 0;
}
int left_height = calc_height(root->left);
int right_height = calc_height(root->right);
return (left_height > right_height ? left_height : right_height) + 1;
}
int main() {
int n;
char preorder[MAXN+1], inorder[MAXN+1];
scanf("%d%s%s", &n, preorder, inorder);
Node *root = build_tree(preorder, inorder, n);
int height = calc_height(root);
printf("%d\n", height);
return 0;
}
```
这里的 `build_tree()` 函数和 `calc_height()` 函数分别用于构建二叉树和计算二叉树的高度。在 `build_tree()` 函数中,我们递归地构建左右子树,而在 `calc_height()` 函数中,我们递归地计算左右子树的高度,并返回左右子树高度的最大值加1。
需要注意的是,这里我们使用了动态内存分配来构建二叉树,需要最后释放内存以避免内存泄漏。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)