利用上面创建的二叉链树,采用前序和中序遍历(分别用递归和非递归形式完成)输出信息
时间: 2023-06-12 21:04:51 浏览: 52
以下是采用递归方式实现的前序遍历和中序遍历的代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# 创建二叉树
def create_tree():
root = Node('A')
root.left = Node('B')
root.left.left = Node('D')
root.left.right = Node('E')
root.right = Node('C')
root.right.left = Node('F')
root.right.right = Node('G')
return root
# 递归实现前序遍历
def pre_order_recursion(root):
if root is not None:
print(root.data, end=' ')
pre_order_recursion(root.left)
pre_order_recursion(root.right)
# 递归实现中序遍历
def in_order_recursion(root):
if root is not None:
in_order_recursion(root.left)
print(root.data, end=' ')
in_order_recursion(root.right)
# 测试代码
if __name__ == '__main__':
root = create_tree()
print('前序遍历:', end='')
pre_order_recursion(root)
print('\n中序遍历:', end='')
in_order_recursion(root)
```
输出结果为:
```
前序遍历:A B D E C F G
中序遍历:D B E A F C G
```
以下是采用非递归方式实现的前序遍历和中序遍历的代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# 创建二叉树
def create_tree():
root = Node('A')
root.left = Node('B')
root.left.left = Node('D')
root.left.right = Node('E')
root.right = Node('C')
root.right.left = Node('F')
root.right.right = Node('G')
return root
# 非递归实现前序遍历
def pre_order_iteration(root):
if root is None:
return
stack = [root]
while stack:
node = stack.pop()
print(node.data, end=' ')
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
# 非递归实现中序遍历
def in_order_iteration(root):
if root is None:
return
stack = []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
node = stack.pop()
print(node.data, end=' ')
root = node.right
# 测试代码
if __name__ == '__main__':
root = create_tree()
print('前序遍历:', end='')
pre_order_iteration(root)
print('\n中序遍历:', end='')
in_order_iteration(root)
```
输出结果为:
```
前序遍历:A B D E C F G
中序遍历:D B E A F C G
```