假设二叉树的结点值是字符,根据输入的一棵二叉树的扩展先序遍历序列建立一棵以二叉链表表示的二叉树。对二叉树进行先序、中序和后序遍历操作,并输出遍历序列,观察输出的序列是否与逻辑上的序列一致。完整代码
时间: 2024-05-01 08:23:37 浏览: 59
以下是基于Python实现的代码:
```python
# 定义二叉树结点类
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 通过扩展先序遍历序列建立二叉树
def build_tree(preorder):
if not preorder:
return None
root_val = preorder.pop(0)
if root_val == '#':
return None
root = TreeNode(int(root_val))
root.left = build_tree(preorder)
root.right = build_tree(preorder)
return root
# 先序遍历二叉树
def preorder_traversal(root):
if not root:
return []
res = [root.val]
res += preorder_traversal(root.left)
res += preorder_traversal(root.right)
return res
# 中序遍历二叉树
def inorder_traversal(root):
if not root:
return []
res = inorder_traversal(root.left)
res += [root.val]
res += inorder_traversal(root.right)
return res
# 后序遍历二叉树
def postorder_traversal(root):
if not root:
return []
res = postorder_traversal(root.left)
res += postorder_traversal(root.right)
res += [root.val]
return res
# 测试
preorder = ['1', '2', '4', '#', '#', '5', '#', '#', '3', '6', '#', '#', '7', '#', '#']
root = build_tree(preorder)
assert preorder_traversal(root) == ['1', '2', '4', '5', '3', '6', '7']
assert inorder_traversal(root) == ['4', '2', '5', '1', '6', '3', '7']
assert postorder_traversal(root) == ['4', '5', '2', '6', '7', '3', '1']
```
以上代码实现了建立二叉树、先序遍历、中序遍历和后序遍历四个操作。测试代码通过扩展先序遍历序列建立了一棵二叉树,并分别输出了先序遍历序列、中序遍历序列和后序遍历序列,并与逻辑上的序列进行了对比。
阅读全文