编写一个程序,在自定义函数中完成下列功能并在主函数进行测试: (1)根据测试数据画出二叉树,按照先序遍历写出读入字符的顺序,建立相应的二叉链表。 (2)输出二叉树的后序遍历序列。 测试数据: 先序遍历序列:ABDGCEF 中序遍历序列:DGBAECF
时间: 2024-11-22 19:46:04 浏览: 37
为了编写这样的程序,我们可以使用Python语言以及字典来表示二叉树节点,并利用递归的方式实现先序遍历和后序遍历。这里是一个简单的示例:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_binary_tree(preorder, inorder):
if not preorder or not inorder:
return None
# 根据中序遍历找到根节点
root_val = inorder[0]
root = Node(root_val)
# 通过先序遍历找到root的位置
index = preorder.index(root_val)
# 分别构建左子树和右子树
root.left = build_binary_tree(preorder[:index], inorder[1:index+1])
root.right = build_binary_tree(preorder[index+1:], inorder[index+1:])
return root
def in_order_traversal(node):
if node is None:
return []
return in_order_traversal(node.left) + [node.val] + in_order_traversal(node.right)
# 测试数据
preorder = "ABDGCEF"
inorder = "DGBAECF"
# 构建二叉树
tree_root = build_binary_tree(preorder.split(), inorder.split())
# 先序遍历
print("先序遍历序列:", '->'.join(preorder))
# 后序遍历
postorder = in_order_traversal(tree_root)
print("后序遍历序列:", '->'.join(postorder))
阅读全文