编一个程序,读入用户输入的一串先序遍历字符串,根据输入建立一棵二叉树, 并输出该二叉树的层次遍历序列。层次遍历是指逐层访问,每一层又按从左到右的次序访问结点。
时间: 2023-06-05 22:06:05 浏览: 78
好的,这是一个算法问题,可以为你编写程序实现该功能。以下是程序代码:
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def build_tree(self, preorder):
if not preorder:
return None
root_val = preorder.pop(0)
if root_val is None:
return None
root = TreeNode(root_val)
root.left = self.build_tree(preorder)
root.right = self.build_tree(preorder)
return root
def level_order(self):
if self.root is None:
return []
level = [self.root]
result = []
while level:
next_level = []
for node in level:
if node:
result.append(node.value)
next_level.append(node.left)
next_level.append(node.right)
level = next_level
return result
preorder = list(map(int, input().split()))
tree = BinaryTree()
tree.root = tree.build_tree(preorder)
print(tree.level_order())
```
你可以将一串先序遍历的序列输入程序,程序将会输出该二叉树的层次遍历序列。