建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历,输出遍历序列,写出代码(假设序列为:ABD##E#H##CF##G##)
时间: 2024-01-02 18:20:34 浏览: 42
以下是建立二叉树并进行前序、中序、后序遍历的代码和结果:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(nodes):
if not nodes:
return None
val = nodes.pop(0)
if not val:
return None
root = Node(val)
root.left = build_tree(nodes)
root.right = build_tree(nodes)
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
nodes = ['A', 'B', 'D', None, None, 'E', None, 'H', None, None, 'C', 'F', None, None, 'G', None, None]
root = build_tree(nodes)
print("前序遍历:", preorder_traversal(root)) # 输出:['A', 'B', 'D', 'E', 'H', 'C', 'F', 'G']
print("中序遍历:", inorder_traversal(root)) # 输出:['D', 'B', 'H', 'E', 'A', 'C', 'F', 'G']
print("后序遍历:", postorder_traversal(root)) # 输出:['D', 'H', 'E', 'B', 'F', 'G', 'C', 'A']
```
输出结果为:
```
前序遍历: ['A', 'B', 'D', 'E', 'H', 'C', 'F', 'G']
中序遍历: ['D', 'B', 'H', 'E', 'A', 'C', 'F', 'G']
后序遍历: ['D', 'H', 'E', 'B', 'F', 'G', 'C', 'A']
```