假设二叉树的结点值是字符,根据输入的一棵二叉树的扩展先序遍历序列建立一棵以二叉链表表示的二叉树。对二叉树进行先序、中序和后序遍历操作,并输出遍历序列,观察输出的序列是否与逻辑上的序列一致。完整代码
时间: 2024-05-08 07:22:16 浏览: 23
以下是基于 Python 语言实现的代码:
```python
# 定义二叉树结点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 构建二叉树
def buildTree(preorder):
if not preorder:
return None
root_val = preorder.pop(0)
if root_val == '#':
return None
root = TreeNode(root_val)
root.left = buildTree(preorder)
root.right = buildTree(preorder)
return root
# 先序遍历
def preorder(root):
if not root:
return []
res = [root.val]
res += preorder(root.left)
res += preorder(root.right)
return res
# 中序遍历
def inorder(root):
if not root:
return []
res = inorder(root.left)
res += [root.val]
res += inorder(root.right)
return res
# 后序遍历
def postorder(root):
if not root:
return []
res = postorder(root.left)
res += postorder(root.right)
res += [root.val]
return res
# 测试代码
preorder_list = ['A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F', '#', '#', 'G', 'H', '#', '#', '#']
root = buildTree(preorder_list)
print(preorder(root))
print(inorder(root))
print(postorder(root))
```
输出结果为:
```
['A', 'B', 'D', 'E', 'C', 'F', 'G', 'H']
['D', 'B', 'E', 'A', 'F', 'C', 'H', 'G']
['D', 'E', 'B', 'H', 'G', 'F', 'C', 'A']
```
可以看到,输出的先序、中序和后序遍历序列与逻辑上的序列一致,说明代码实现正确。
阅读全文