已知二叉树的前序遍历序列和中序遍历序列分别是: B,A,C,D,F,E,G和D,C,A,F,G,E,B, 试画出该二叉树
时间: 2023-09-20 15:04:42 浏览: 72
根据给定的前序遍历序列和中序遍历序列,可以绘制出该二叉树的示意图如下:
```
B
/ \
A E
/ \
C G
/ \
D F
```
注意,这只是一种可能的二叉树结构。根据给定的序列,我们可以确定根节点是B,然后根据中序遍历序列确定左子树和右子树的结构。通过递归地应用这个过程,我们可以建立整个二叉树。
相关问题
已知一个二叉树的前序遍历序列和中序遍历序列,求其后序遍历序列。c语言
代码实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode{
int val; // 节点值
struct TreeNode* left; // 左子节点
struct TreeNode* right; // 右子节点
}TreeNode;
TreeNode* buildTree(int* preorder, int* inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd);
void postorderTraversal(TreeNode* root);
int main(){
int preorder[] = {1, 2, 4, 5, 3, 6, 7}; // 前序遍历序列
int inorder[] = {4, 2, 5, 1, 6, 3, 7}; // 中序遍历序列
int n = sizeof(preorder) / sizeof(int); // 序列长度
TreeNode* root = buildTree(preorder, inorder, 0, n - 1, 0, n - 1); // 构建二叉树
printf("后序遍历序列为:");
postorderTraversal(root); // 后序遍历输出
return 0;
}
// 根据前序遍历序列和中序遍历序列构建二叉树
TreeNode* buildTree(int* preorder, int* inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd){
if(preorderStart > preorderEnd){
return NULL;
}
int rootVal = preorder[preorderStart];
int index = inorderStart;
while(inorder[index] != rootVal){
index++;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = rootVal;
root->left = buildTree(preorder, inorder, preorderStart + 1, preorderStart + index - inorderStart, inorderStart, index - 1);
root->right = buildTree(preorder, inorder, preorderStart + index - inorderStart + 1, preorderEnd, index + 1, inorderEnd);
return root;
}
// 后序遍历输出
void postorderTraversal(TreeNode* root){
if(root == NULL){
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
```
已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI和BCAEDGHEL写出后序序列?
根据二叉树前序遍历和中序遍历的特点,可以得知该二叉树的根节点为A,且左子树的前序遍历序列为BCDEFGH,中序遍历序列为BCAEDG,右子树的前序遍历序列为I,中序遍历序列为LHEG。
接下来可以递归地处理左右子树,得到左子树的后序遍历序列为DEGCBHA,右子树的后序遍历序列为LHEGIA。因此,整棵二叉树的后序遍历序列为DEGCBHALHEGIA。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](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)