假设二叉树用二叉链存储,给出中序序列和后序序列,构造二叉树并给出先序遍历。
时间: 2023-07-30 13:06:31 浏览: 68
JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】
好的,我会尽力回答你的问题。
首先,我们需要知道二叉树的遍历方式有三种:先序遍历、中序遍历和后序遍历。其中,先序遍历的顺序是:根节点 -> 左子树 -> 右子树;中序遍历的顺序是:左子树 -> 根节点 -> 右子树;后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
给出中序序列和后序序列,我们可以通过递归的方式构造出二叉树。具体步骤如下:
1. 后序序列的最后一个元素为根节点,将其创建为一个节点,并从后序序列中删除。
2. 在中序序列中找到根节点的位置,将中序序列分成左右两个子序列。
3. 递归的构造右子树,将右子树的根节点设置为步骤1中创建的节点,并将右子树的中序序列和后序序列传入递归函数中。
4. 递归的构造左子树,将左子树的根节点设置为步骤1中创建的节点,并将左子树的中序序列和后序序列传入递归函数中。
5. 返回根节点。
构造出二叉树后,我们可以通过先序遍历的方式输出二叉树的节点值。具体步骤如下:
1. 输出当前节点的值。
2. 递归输出左子树的节点值。
3. 递归输出右子树的节点值。
下面是具体的代码实现,其中,中序序列和后序序列分别存储在数组inorder和postorder中,而先序序列则存储在数组preorder中。
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(inorder, postorder):
if not inorder:
return None
root_val = postorder.pop()
root = TreeNode(root_val)
root_idx = inorder.index(root_val)
root.right = buildTree(inorder[root_idx+1:], postorder)
root.left = buildTree(inorder[:root_idx], postorder)
return root
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
root = buildTree(inorder, postorder)
print(preorderTraversal(root)) # [3, 9, 20, 15, 7]
```
希望我的回答能够解决你的问题。
阅读全文