利用中序和后序表达式建立二叉树
时间: 2023-12-14 21:40:07 浏览: 97
Mid_Pre_Post.rar_pre_二叉树
利用中序和后序表达式建立二叉树的步骤如下:
1. 后序表达式的最后一个元素为根节点。
2. 在中序表达式中找到根节点的位置,根节点左侧的元素为其左子树,右侧的元素为其右子树。
3. 对于后序表达式,将其分为左子树和右子树两部分,分别对左右子树进行递归建树。
4. 递归建树直到后序表达式和中序表达式为空。
以下是一个Python实现的代码示例:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(inorder, postorder):
if not inorder or not postorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
root_index = inorder.index(root_val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index+1:]
left_postorder = postorder[:root_index]
right_postorder = postorder[root_index:len(postorder)-1]
root.left = buildTree(left_inorder, left_postorder)
root.right = buildTree(right_inorder, right_postorder)
return root
```
其中,inorder为中序表达式,postorder为后序表达式。函数返回建立完成的二叉树的根节点。
阅读全文