若某棵二叉树的先根遍历序列为ABCDEF,中根遍历序列为CBDAEF,则这棵二叉树的后根遍历序列为( )。 (2分)
时间: 2024-05-26 07:15:47 浏览: 23
根据先序遍历和中序遍历可以确定一棵二叉树,由于先序遍历的第一个节点是根节点,因此A为根节点。然后在中序遍历中,找到A的位置,根据中序遍历的性质,A的左边为左子树的中序遍历,右边为右子树的中序遍历。可以发现,左子树的中序遍历为CBD,右子树的中序遍历为AEF。接下来递归处理左子树和右子树即可。由于后序遍历的最后一个节点为根节点,因此该二叉树的后序遍历应该为CDABFE。
相关问题
若某棵二叉树的先根遍历序列为ABCDEF,中根遍历序列为CBDAEF,则这棵二叉树的后根遍历序列为
根据先根遍历序列和中根遍历序列可以重建出原二叉树,然后对这棵二叉树进行后根遍历即可得到后根遍历序列。
先根遍历序列为 ABCDEF,中根遍历序列为 CBDAEF。根据先根遍历序列的第一个元素 A,可以确定根节点为 A。在中根遍历序列中,A 的左边为左子树的节点 CB,右边为右子树的节点 DEF。因此,A 的左子树为以先根遍历序列中 BCD 为先根遍历序列,CB 为中根遍历序列的二叉树,右子树为以先根遍历序列中 EFG 为先根遍历序列,EF 为中根遍历序列的二叉树。
继续递归构建左右子树,得到下图所示的二叉树:
```
A
/ \
B D
/ \
C E
/ \
F G
```
对上述二叉树进行后根遍历,可得后根遍历序列为:C B F G E D A。
因此,该二叉树的后根遍历序列为 CBFGEDA。
二叉树的先序遍历序列为ABCDEF,中序遍历序列为CBDAEF,则后序遍历序列为
根据先序遍历序列找到根节点为A,再在中序遍历序列中找到A的位置,可以将中序遍历序列分为CBDA和EF两部分。由于是二叉树,因此先序遍历序列中B和C一定是A的左右子节点,同理D、E、F一定是A的右子树的节点。
接下来可以递归处理左子树和右子树。左子树的先序遍历序列为BCD,中序遍历序列为CBD,可以依此求得左子树的后序遍历序列DCB。右子树的先序遍历序列为EF,中序遍历序列为EAF,可以依此求得右子树的后序遍历序列AFE。
因此,整棵树的后序遍历序列为DCBAFE。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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_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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![apk](https://img-home.csdnimg.cn/images/20210720083646.png)