简单说一下前序遍历,后序遍历,中序遍历关系和区别
时间: 2023-06-30 20:23:48 浏览: 151
前序遍历、后序遍历和中序遍历都是二叉树遍历的方法。
前序遍历:先遍历根节点,再遍历左子树,最后遍历右子树。
中序遍历:先遍历左子树,再遍历根节点,最后遍历右子树。
后序遍历:先遍历左子树,再遍历右子树,最后遍历根节点。
它们的区别在于遍历的顺序不同,因此访问节点的顺序也不同。同时它们也有着重要的区别:
1. 前序遍历是最自然的遍历方式,可以方便地生成一个树的拷贝。
2. 后序遍历在一些应用中比较常见,例如表达式求值。
3. 中序遍历则可以将一个二叉搜索树(BST)转换成一个有序的数组。
相关问题
如何通过前序遍历和后序遍历推出中序遍历?
通过前序遍历和后序遍历推出中序遍历的方法如下:
1. 首先,我们知道前序遍历的顺序是:根节点 -> 左子树 -> 右子树,而后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
2. 根据前序遍历的特点,我们可以得到根节点的值。
3. 接下来,我们需要找到根节点在后序遍历中的位置。在后序遍历中,根节点的位置是在最后一个元素。
4. 根据根节点在后序遍历中的位置,我们可以将后序遍历分为左子树和右子树两部分。
5. 然后,我们可以根据左子树和右子树的长度,在前序遍历中找到左子树和右子树的范围。
6. 递归地对左子树和右子树进行相同的操作,直到只剩下一个节点。
7. 最后,我们可以得到中序遍历的顺序。
根据前序遍历和后序遍历得到中序遍历 Python
根据前序遍历和后序遍历得到中序遍历的方法如下:
```python
def getInorder(preorder, inorder, postorder):
if len(preorder) == 0:
return []
if len(preorder) == 1:
return [preorder[0]]
root = postorder[-1]
rootIndex = inorder.index(root)
leftInorder = inorder[:rootIndex]
rightInorder = inorder[rootIndex+1:]
leftPreorder = preorder[1:1+len(leftInorder)]
rightPreorder = preorder[1+len(leftInorder):]
leftPostorder = postorder[:len(leftInorder)]
rightPostorder = postorder[len(leftInorder):-1]
left = getInorder(leftPreorder, leftInorder, leftPostorder)
right = getInorder(rightPreorder, rightInorder, rightPostorder)
return left + [root] + right
```
其中,preorder表示前序遍历结果,inorder表示中序遍历结果,postorder表示后序遍历结果。函数的返回值为中序遍历结果。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)