一棵二叉树的结点若无子树,则可将其子树看作 “.”,输入时,按照前序序列的顺序输入该结点的内容。对 下图,其输入序列为 ABD..EH...CF.I..G..。 [输出] 若为空二叉树,则输出:THIS IS A EMPTY BINARY TREE。若二叉树不空,按后序序列输出,对上例,输出结果为:DHEBIFGCA。
时间: 2024-02-11 08:05:24 浏览: 20
好的,我知道了。这是一道关于二叉树输入输出的问题。根据题目所给的输入序列,我们可以构建出以下的二叉树:
```
A
/ \
B C
/ \ / \
. D E F
/ / \
. I .
/
G
```
对于这个问题,我们可以使用递归的方式来进行后序遍历,并输出每一个结点的值。具体的实现可以参考下面的代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder):
if len(preorder) == 0:
return None
val = preorder.pop(0)
if val == '.':
return None
root = TreeNode(val)
root.left = build_tree(preorder)
root.right = build_tree(preorder)
return root
def postorder_traversal(root):
if root is None:
return
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end='')
preorder = list(input().strip())
if len(preorder) == 0:
print('THIS IS A EMPTY BINARY TREE')
else:
root = build_tree(preorder)
postorder_traversal(root)
```
输入样例:ABD..EH...CF.I..G..
输出样例:DHEBIFGCA
相关推荐
![](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)
![](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)