用循环体输入生成二叉树,输入quit停止生成二叉树,并生成先序中序和后序输出
时间: 2023-12-03 13:44:15 浏览: 69
先序中序后序三种方法遍历一棵二叉树
5星 · 资源好评率100%
好的,以下是一个用循环体输入生成二叉树,并输出先序、中序和后序遍历结果的示例代码:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def build_tree(input_list):
if not input_list:
return None
root = Node(input_list.pop(0))
queue = [root]
while input_list:
cur_node = queue.pop(0)
left_val = input_list.pop(0)
if left_val != 'None':
cur_node.left = Node(left_val)
queue.append(cur_node.left)
if not input_list:
break
right_val = input_list.pop(0)
if right_val != 'None':
cur_node.right = Node(right_val)
queue.append(cur_node.right)
return root
def preorder_traversal(root):
if not root:
return []
result = [root.value]
result += preorder_traversal(root.left)
result += preorder_traversal(root.right)
return result
def inorder_traversal(root):
if not root:
return []
result = inorder_traversal(root.left)
result += [root.value]
result += inorder_traversal(root.right)
return result
def postorder_traversal(root):
if not root:
return []
result = postorder_traversal(root.left)
result += postorder_traversal(root.right)
result += [root.value]
return result
# 主程序
input_list = []
while True:
val = input("请输入节点的值(输入quit结束输入):")
if val.lower() == 'quit':
break
input_list.append(val)
root = build_tree(input_list)
print("先序遍历结果:", preorder_traversal(root))
print("中序遍历结果:", inorder_traversal(root))
print("后序遍历结果:", postorder_traversal(root))
```
这里的 `build_tree` 函数接受一个列表作为输入,其中 `'None'` 表示空节点,其他字符串表示节点的值。函数会返回输入列表所表示的二叉树的根节点。这个函数利用了一个队列来辅助建立二叉树。
`preorder_traversal`、`inorder_traversal` 和 `postorder_traversal` 分别是先序、中序和后序遍历的实现函数,它们都接受一个二叉树的根节点作为输入,返回遍历结果。
主程序中,我们不断输入节点的值,直到输入 `quit` 为止。然后调用 `build_tree` 函数建立二叉树,并分别输出先序、中序和后序遍历的结果。
阅读全文