假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,请画出该二叉树,并写出其先序序列和后序序列完整代码
时间: 2023-08-10 22:31:16 浏览: 145
根据中序序列,可以确定根节点为G,因此可以将层次序列分为左右两个子树的层次序列:ABDEFHIJ和C。然后可以继续按照此方法递归构造左右子树。
二叉树的形态如下:
```
G
/ \
/ \
/ \
D C
\ /
B I
\ \
E F
/
J
/
A
```
先序序列为:GDBEACIJFH
后序序列为:DEBJEIFHJCAIG
以下是完整代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(level, inorder):
if not level or not inorder:
return None
root_val = level[0]
root = Node(root_val)
idx = inorder.index(root_val)
root.left = build_tree(level[1:idx+1], inorder[:idx])
root.right = build_tree(level[idx+1:], inorder[idx+1:])
return root
def preorder_traversal(root):
if not root:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
def postorder_traversal(root):
if not root:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]
# 测试代码
level = "ABCDEFGHIJ"
inorder = "DBGEHJACIF"
root = build_tree(level, inorder)
print(preorder_traversal(root)) # 输出:['G', 'D', 'B', 'E', 'A', 'C', 'I', 'J', 'F', 'H']
print(postorder_traversal(root)) # 输出:['D', 'E', 'B', 'J', 'F', 'I', 'C', 'A', 'H', 'G']
```
阅读全文