设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C,画出这棵二叉树。写出代码
时间: 2024-10-25 07:16:48 浏览: 328
这是一道典型的二叉树构造题,通过先序遍历(根节点 -> 左子树 -> 右子树)和中序遍历(左子树 -> 根节点 -> 右子树),我们可以确定每个节点的位置。
先序遍历中的A是根节点,中序遍历中B位于根节点之前,所以B是左子树的根,D、F在其后,接着是C作为根,E在C之后,G和H在其后。
基于这个信息,我们可以逐步构建二叉树结构。下面是用Python代码实现的例子:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = Node(root_val)
# 找到根值在中序遍历中的索引
root_in_order_index = inorder.index(root_val)
# 分别处理左右子树
root.left = build_tree(preorder[1:root_in_order_index + 1], inorder[:root_in_order_index])
root.right = build_tree(preorder[root_in_order_index + 1:], inorder[root_in_order_index + 1:])
return root
# 先序遍历和中序遍历
preorder = ['A', 'B', 'D', 'F', 'C', 'E', 'G', 'H']
inorder = ['B', 'F', 'D', 'A', 'G', 'E', 'H', 'C']
# 构建二叉树并打印
tree_root = build_tree(preorder, inorder)
print("二叉树结构如下:")
print_inorder(tree_root)
def print_inorder(node):
if node is not None:
print_inorder(node.left)
print(node.val, end=" ")
print_inorder(node.right)
```
运行上述代码后,你会得到按照给定的先序和中序遍历构建的二叉树的结构。注意,这里假设输入的两个列表都是正确的,如果需要处理错误情况,还需要添加额外的检查。
阅读全文