M07161: 森林的带度数层次序列存储
dfs + bfs, http://cs101.openjudge.cn/practice/07161/
对于树和森林等非线性结构，我们往往需要将其序列化以便存储。有一种树的存储方式称为带度数的层次序列。我们可以通过层次遍历的方式将森林序列转化为多个带度数的层次序列。
例如对于以下森林：
两棵树的层次遍历序列分别为：C E F G K H J / D X I
每个结点对应的度数为：3 3 0 0 0 0 0 / 2 0 0
我们将以上序列存储起来，就可以在以后的应用中恢复这个森林。在存储中，我们可以将第一棵树表示为C 3 E 3 F 0 G 0 K 0 H 0 J 0，第二棵树表示为D 2 X 0 I 0。
现在有一些通过带度数的层次遍历序列存储的森林数据，为了能够对这些数据进行进一步处理，首先需要恢复他们。
输入
输入数据的第一行包括一个正整数n，表示森林中非空的树的数目。 随后的 n 行，每行给出一棵树的带度数的层次序列。 树的节点名称为A-Z的单个大写字母。
输出
输出包括一行，输出对应森林的后根遍历序列。
样例输入
2
C 3 E 3 F 0 G 0 K 0 H 0 J 0
D 2 X 0 I 0样例输出
K H J E F G C X I D是 DFS + BFS 结合的题目。 利用队列根据“带度数的层次序列”构造树，然后进行后根遍历。代码如下：
python
from collections import deque
import sys
# 定义树的结点
class Node:
def __init__(self, value, degree):
self.value = value
self.degree = degree
self.children = []
# 根据带度数的层次序列构造树
def build_tree(tokens):
# tokens 的格式：[字母, 度数, 字母, 度数, ...]
# 第一个结点为根
root = Node(tokens[0], int(tokens[1]))
queue = deque([root])
index = 2 # 下一个待处理的token索引
while queue and index < len(tokens):
current = queue.popleft()
# current.degree 个孩子依次出现在 tokens 中
for _ in range(current.degree):
# 每个孩子由两个元素构成：字母和度数
child = Node(tokens[index], int(tokens[index+1]))
current.children.append(child)
queue.append(child)
index += 2
return root
# 后根遍历（后序遍历）：先遍历所有子树，再访问根节点
def postorder(node, output):
for child in node.children:
postorder(child, output)
output.append(node.value)
def main():
input_lines = sys.stdin.read().splitlines()
if not input_lines:
return
n = int(input_lines[0].strip())
result = []
# 对于每一棵树进行构造并后序遍历
for i in range(1, n+1):
# 将一行的内容按空格分割
tokens = input_lines[i].split()
if not tokens:
continue
root = build_tree(tokens)
temp = []
postorder(root, temp)
result.extend(temp)
# 输出时以空格分隔各个结点
print(" ".join(result))
if __name__ == "__main__":
main()代码说明
构造树：
利用队列按照层次顺序为每个结点分配其子结点，注意每个结点的子结点个数由紧随其后读入的数字决定。后根遍历：
递归地先遍历所有子树，然后将当前结点值加入输出列表。主函数：
读取输入，依次构造每棵树，并将每棵树的后序遍历结果依次合并，最后按要求格式输出。
python
# 23n2300011075(才疏学浅)
from collections import deque
class Node:
def __init__(self):
self.value=None
self.degree=0
self.childs=[]
def build():
node=Node()
node.value=l.pop(0)
node.degree=int(l.pop(0))
return node
def Tree():
root=build()
q=deque([root])
while q:
node=q.popleft()
for i in range(node.degree):
child=build()
node.childs.append(child)
q.append(child)
return root
def lastorder(tree):
for child in tree.childs:
lastorder(child)
print(tree.value,end=" ")
n=int(input())
for _ in range(n):
l=list(input().split())
tree=Tree()
lastorder(tree)python
from collections import deque
def postorder(node, children, result):
if node in children:
for child in children[node]:
postorder(child, children, result)
result.append(node)
def process_tree(tree_data):
nodes = deque()
children = {}
it = iter(tree_data)
root = next(it)
degree = int(next(it))
nodes.append((root, degree))
children[root] = []
while nodes:
current_node, degree = nodes.popleft()
for _ in range(degree):
if not it:
break
child = next(it)
child_degree = int(next(it))
if current_node not in children:
children[current_node] = []
children[current_node].append(child)
nodes.append((child, child_degree))
children[child] = []
# 后根遍历
result = []
postorder(root, children, result)
return result
def main():
n = int(input().strip())
forest_data = []
for _ in range(n):
forest_data.append(input().strip().split())
results = []
for tree_data in forest_data:
result = process_tree(tree_data)
results.extend(result)
print(" ".join(results))
if __name__ == "__main__":
main()