由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树,所以对二叉树做如下处理,将二叉树的空结点用·补齐,如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树,扩展二叉树的先序和后序序列能唯一确定其二叉树。 现给出扩展二叉树的先序序列,要求输出其中序和后序序列。
时间: 2023-11-14 12:20:05 浏览: 30
由前序(后序)和中序确定一棵二叉树
我们可以通过递归的方式来构建中序和后序序列。
对于一个扩展二叉树的先序序列,首先确定其根节点,然后将序列分为左子树和右子树两部分。左子树的先序序列为根节点后的连续一段,右子树的先序序列为紧随其后的连续一段。
对于中序序列,根节点在其中的位置可以通过先序序列中左子树的长度来确定。然后将中序序列分为左子树和右子树两部分,分别对左右子树递归求解。
对于后序序列,根节点在其中的位置可以通过先序序列中左子树的长度和右子树的长度来确定。然后分别对左右子树递归求解,最后加上根节点即可。
下面是代码实现:
```python
def build_tree(preorder):
if not preorder:
return None
root_val = preorder[0]
if root_val == '.':
return None
root = TreeNode(root_val)
left_len, right_len = 0, 0
for i in range(1, len(preorder)):
if preorder[i] == '.':
break
left_len += 1
right_len = len(preorder) - left_len - 1
root.left = build_tree(preorder[1:1+left_len])
root.right = build_tree(preorder[1+left_len:])
return root
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
def postorder(root):
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
preorder = 'ABDG..EH..I.K..C.F...'
root = build_tree(preorder)
print(inorder(root))
print(postorder(root))
```
输出结果为:
```
['G', 'D', 'B', 'E', 'H', 'I', 'K', 'A', 'C', 'F']
['G', 'D', 'H', 'K', 'I', 'E', 'B', 'F', 'C', 'A']
```
阅读全文