编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树。例如如下的先序遍历字符串:abc##de#g##f### ,其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对
时间: 2023-05-03 14:00:34 浏览: 83
本题是要编写一个程序,读入用户输入的一串字符,根据此字符串建立一个二叉树。例如下面的先序遍历字符串:abc##de#g##f###,其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对其进行后序遍历。
相关问题
编一个程序,读入用户输入的一串先序遍历字符串,根据输入建立一颗二叉树,并输出该二叉树的层次遍历序列
好的,我可以帮你编写这个程序。以下是程序代码:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Tree:
def __init__(self, val):
self.root = Node(val)
def buildTree(self, nodes):
if not nodes:
return None
root_val = nodes.pop(0)
if root_val == "#":
return None
root = Node(root_val)
root.left = self.buildTree(nodes)
root.right = self.buildTree(nodes)
return root
def levelOrder(self):
queue = [self.root]
res = []
while queue:
node = queue.pop(0)
if node:
res.append(node.val)
queue.append(node.left)
queue.append(node.right)
return res
if __name__ == "__main__":
nodes = input().strip().split()
tree = Tree(nodes[0])
root = tree.buildTree(nodes[1:])
res = tree.levelOrder()
print(' '.join(res))
```
这个程序可以读入用户输入的一串先序遍历字符串,建立一颗二叉树,并输出该二叉树的层次遍历序列。你只需要输入先序遍历字符串,程序就会返回层次遍历序列。如果你有其他问题,可以继续问我。
编一个程序,读入用户输入的一串先序遍历字符串,根据输入建立一棵二叉树, 并输出该二叉树的层次遍历序列
好的,我可以帮你编写该程序。以下是使用 Python 语言的实现方法:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder):
if not preorder:
return None
root = TreeNode(preorder[0])
if len(preorder) == 1:
return root
i = 1
while i < len(preorder) and preorder[i] < root.val:
i += 1
root.left = build_tree(preorder[1:i])
root.right = build_tree(preorder[i:])
return root
def level_order_traversal(root):
if not root:
return []
res = []
queue = [root]
while queue:
level = []
for _ in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
# 输入先序遍历字符串
preorder = input('请输入先序遍历字符串:').split()
# 构建二叉树
root = build_tree(preorder)
# 输出层次遍历序列
print(level_order_traversal(root))
```
你可以将先序遍历字符串输入程序中,程序会输出该二叉树的层次遍历序列。注意程序中使用了树节点的定义和层次遍历的实现。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)