已知先序序列,建立一棵二叉树,输出后序遍历序列,并计算这颗二叉树的高度。输入格式:在一行中给出二叉树的先序序列,*表示空格。输出格式:输出共二行,第一行是二叉树的后序遍历序列,第二行是二叉树的高度。数据结构用C语言生成
时间: 2024-10-22 21:04:19 浏览: 13
在C语言中,我们可以使用递归的方式来解决这个问题。首先,我们需要定义两个函数,一个用于创建二叉树,另一个用于后序遍历并获取高度。以下是关键步骤:
1. **构建二叉树函数**:
- 使用先序遍历的第一个元素作为根节点。
- 对左子树和右子树分别使用剩余部分进行递归调用,直到序列为空。
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* buildTree(char* preorder) {
if (preorder[0] == '\0') return NULL; // 结束标志
int rootVal = atoi(&preorder[0]); // 获取当前节点值
struct TreeNode* root = malloc(sizeof(struct TreeNode));
root->val = rootVal;
char *p = strchr(preorder, ' '); // 找到第一个空格的位置
p++; // 空格后的字符开始是左子树的前序序列
root->left = buildTree(p); // 递归构造左子树
p += strlen(p); // 右子树前序序列从当前位置开始
root->right = buildTree(p); // 递归构造右子树
return root;
}
```
2. **后序遍历和计算高度函数**:
- 后序遍历通常通过栈实现,将待访问的节点入栈,同时将左子树和右子树也推入栈,最后出栈的是当前节点。
- 高度的计算可以通过递归的方式完成,基本情况是一个叶子节点的高度为1,其他情况为左右子树高度的最大值加1。
```c
void printPostOrder(struct TreeNode* node, char* postorder) {
if (!node) return;
printPostOrder(node->left, postorder);
printPostOrder(node->right, postorder);
sprintf(postorder, "%d ", node->val); // 输出节点值
}
int height(struct TreeNode* node) {
if (!node) return 0;
int leftHeight = height(node->left);
int rightHeight = height(node->right);
return max(leftHeight, rightHeight) + 1;
}
```
然后,在主程序中调用这两个函数,得到后序遍历序列和高度,并输出结果:
```c
int main() {
char preorder[] = "9 3 15 20 7 10 5"; // 示例输入
char postorder[100];
struct TreeNode* root = buildTree(preorder);
printPostOrder(root, postorder);
printf("\n");
printf("Height: %d\n", height(root));
return 0;
}
```
注意,这里的代码假设输入的字符串中每个整数之间用空格隔开,且数组足够大以存储结果。如果需要处理更复杂的情况,如输入由用户输入或者读取文件等,还需要额外的错误检查和输入解析代码。
阅读全文