04082: 树的镜面映射
http://cs101.openjudge.cn/practice/04082/
一棵树的镜面映射指的是对于树中的每个结点，都将其子结点反序。例如，对左边的树，镜面映射后变成右边这棵树。
a a
/ | \ / | \
b c f ===> f c b
/ \ / \
d e e d我们在输入输出一棵树的时候，常常会把树转换成对应的二叉树，而且对该二叉树中只有单个子结点的分支结点补充一个虚子结点“$”，形成“伪满二叉树”。
例如，对下图左边的树，得到下图右边的伪满二叉树
a a
/ | \ / \
b c f ===> b $
/ \ / \
d e $ c
/ \
d f
/ \
$ e然后对这棵二叉树进行前序遍历，如果是内部结点则标记为0，如果是叶结点则标记为1，而且虚结点也输出。
现在我们将一棵树以“伪满二叉树”的形式输入，要求输出这棵树的镜面映射的宽度优先遍历序列。
输入
输入包含一棵树所形成的“伪满二叉树”的前序遍历。 第一行包含一个整数，表示结点的数目。 第二行包含所有结点。每个结点用两个字符表示，第一个字符表示结点的编号，第二个字符表示该结点为内部结点还是外部结点，内部结点为0，外部结点为1。结点之间用一个空格隔开。 数据保证所有结点的编号都为一个小写字母。
输出
输出包含这棵树的镜面映射的宽度优先遍历序列，只需要输出每个结点的编号，编号之间用一个空格隔开。
样例输入
9
a0 b0 $1 c0 d0 $1 e1 f1 $1样例输出
a f c b e d提示
样例输入输出对应着题目描述中的那棵树。
根据给定的伪满二叉树前序遍历，输出其镜面映射的宽度优先遍历序列。镜面映射是指将每个节点的子节点顺序反转，而宽度优先遍历则需要按层级遍历所有节点。
思路
- 输入处理：读取输入的节点数目和前序遍历序列。
- 层级计算：通过遍历前序序列，维护当前层级信息。内部节点（标记为0）会增加层级，而外部节点（标记为1）会减少层级。
- 层级分组：将每个非虚节点按计算的层级分组。
- 逆序输出：对每个层级的节点逆序，并按层级顺序合并所有节点。
python
from collections import defaultdict
n = int(input())
if n == 0:
print()
exit()
preorder = input().split()
# 初始化根节点
root = preorder[0][0]
root_type = preorder[0][1]
tier = defaultdict(list)
tier[0].append(root)
nodes = [root]
level = 0
types = {root: root_type}
for i in range(1, n):
current = preorder[i]
name = current[0]
typ = current[1]
types[name] = typ
prev_node = nodes[-1]
prev_type = types[prev_node]
# 计算层级变化
if prev_type == '1':
level -= 1
else:
level += 1
nodes.append(name)
# 只添加非虚节点到对应层级
if name != '$':
tier[level].append(name)
# 按层级顺序排序并逆序每层节点
sorted_levels = sorted(tier.items(), key=lambda x: x[0])
result = []
for level, chars in sorted_levels:
result.extend(reversed(chars))
print(' '.join(result))代码解释
- 输入处理：读取输入的节点数和前序序列，处理根节点。
- 层级计算：遍历前序序列中的每个节点，根据前一个节点的类型（内部或外部）调整当前层级。
- 层级分组：将每个非虚节点添加到对应的层级列表中。
- 逆序输出：对每个层级的节点进行逆序处理，并按层级顺序合并所有结果，生成最终的宽度优先遍历序列。
这种方法避免了显式构建树结构，直接通过前序序列的遍历和层级计算，高效地得到镜面映射后的遍历结果。
python
import sys
from collections import deque
sys.setrecursionlimit(10000)
# --- 第一步：读取输入并分割成 token 列表 ---
n = int(sys.stdin.readline().strip()) # 结点总数（包括虚节点）
tokens = sys.stdin.readline().split() # 每个 token 形如 'a0'、'b1'、'$1'
# --- 第二步：将前序序列解析成“伪满二叉树” ---
idx = 0 # 全局索引，用于在 tokens 列表中遍历
class BinNode:
__slots__ = ('label', 'is_leaf', 'left', 'right')
def __init__(self, label, is_leaf):
self.label = label # 结点字符（小写字母或 '$'）
self.is_leaf = is_leaf # True=叶子或虚节点，False=内部节点
self.left = None # 左子指针（在左-子/右-兄弟表示中存第一孩子）
self.right = None # 右子指针（同一层的下一个兄弟）
def parse_binary():
"""
递归按前序解析伪满二叉树：
- 如果当前是内部节点（flag=='0'），则继续读两个子节点
- 如果是叶子或虚节点（flag=='1'），则不再递归
"""
global idx
label = tokens[idx][0]
flag = tokens[idx][1]
idx += 1
node = BinNode(label, flag == '1')
if not node.is_leaf:
# 内部节点必然有左右两个孩子
node.left = parse_binary()
node.right = parse_binary()
return node
root_bin = parse_binary() # 根节点
# --- 第三步：将“左-子/右-兄弟”二叉树转换回 N 叉树，忽略 '$' 虚节点 ---
class NaryNode:
__slots__ = ('label', 'children')
def __init__(self, label):
self.label = label # 真实结点字符
self.children = [] # 孩子列表
def build_nary(bin_node):
"""
将二叉表示转换成 N 叉表示：
- 跳过 bin_node 为 None 或 label=='$'
- bin_node.left 指向第一个孩子；通过 .right 链接拿到所有兄弟
"""
if bin_node is None or bin_node.label == '$':
return None
nnode = NaryNode(bin_node.label)
child = bin_node.left
while child:
nch = build_nary(child)
if nch:
nnode.children.append(nch)
child = child.right
return nnode
root = build_nary(root_bin)
# --- 第四步：对 N 叉树做镜像（对每个节点的孩子列表反序） ---
def mirror_nary(node):
if node is None:
return
node.children.reverse()
for ch in node.children:
mirror_nary(ch)
mirror_nary(root)
# --- 第五步：宽度优先遍历并输出结果 ---
q = deque([root])
res = []
while q:
u = q.popleft()
res.append(u.label)
for ch in u.children:
q.append(ch)
# 最终只输出结点编号，空格分隔
print(' '.join(res))读取与分割
- 读入结点数
n（包含真实结点和虚节点$）。 - 按空格分割出形如
a0、$1的 token 列表。
- 读入结点数
解析伪满二叉树
- 利用前序遍历特点，递归构建二叉树结构（左-子/右-兄弟编码）。
'0'标记内部节点，需继续读左右两棵子树；'1'标记叶子或虚节点。
还原 N 叉树
- 跳过所有 label 为
'$'的节点。 - 通过左指针找第一个孩子，通过右指针串联剩余兄弟。
- 跳过所有 label 为
镜像操作
- 递归对每个节点的子节点列表做
reverse()，即完成“左右子树互换”效果。
- 递归对每个节点的子节点列表做
宽度优先遍历
- 使用队列按层次输出，最终打印各真实结点的标签，空格分隔。
该方案时间复杂度约 O(n)，空间复杂度 O(n)。
前序遍历（Preorder Traversal）是二叉树遍历的一种方式，它的遍历顺序是先访问根节点，然后按照左子树和右子树的顺序递归地遍历子树。
print_tree函数不仅仅是简单地进行宽度优先遍历，而是通过一系列的栈和队列操作来间接实现了镜像映射的效果。
print_tree函数：实现了宽度优先遍历的变种。首先，它遍历树的“右侧视图”，将遇到的非虚节点按遍历顺序存入栈s中。然后，通过逆序将栈s的内容移入队列Q中，以此实现宽度优先遍历的某种形式。对于树的每一层，都先遍历右子树，再遍历左子树，最后将栈s中的元素逆序放回队列Q以继续遍历。这个过程通过间接的方式实现了镜面映射的效果。
发现“镜面”这一要求看着吓人，实际上没什么，它不会改变层与层之间的关系，只要每一层逆序输出就好。
另外发现：04082 树的镜面映射，同样程序用了两遍，lin28~35, line45~52. 在KMP中，也是有同样程序用了两遍。
在这个二叉树中，右节点是和自己“同级”的，左节点是自己的“下级”。这样建立二叉树之后，就能直接写出广度优先遍历，而不需要再把二叉树变为原来的树了。
python
from collections import deque
class TreeNode:
def __init__(self, x):
self.x = x
self.children = []
def create_node():
return TreeNode('')
def build_tree(tempList, index):
node = create_node()
node.x = tempList[index][0]
if tempList[index][1] == '0':
index += 1
child, index = build_tree(tempList, index)
node.children.append(child)
index += 1
child, index = build_tree(tempList, index)
node.children.append(child)
return node, index
def print_tree(p):
Q = deque()
s = deque()
# 遍历右子节点并将非虚节点加入栈s
while p is not None:
if p.x != '$':
s.append(p)
p = p.children[1] if len(p.children) > 1 else None
# 将栈s中的节点逆序放入队列Q
while s:
Q.append(s.pop())
# 宽度优先遍历队列Q并打印节点值
while Q:
p = Q.popleft()
print(p.x, end=' ')
# 如果节点有左子节点，将左子节点及其右子节点加入栈s
if p.children:
p = p.children[0]
while p is not None:
if p.x != '$':
s.append(p)
p = p.children[1] if len(p.children) > 1 else None
# 将栈s中的节点逆序放入队列Q
while s:
Q.append(s.pop())
n = int(input())
tempList = input().split()
# 构建多叉树
root, _ = build_tree(tempList, 0)
# 执行宽度优先遍历并打印镜像映射序列
print_tree(root)按左儿子右兄弟的规则慢慢把树搓出来
python
# 童溯 数学科学学院
class binarynode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.children = []
self.parent = None
n = int(input())
lst = input().split()
stack = []
nodes = []
for x in lst:
temp = binarynode(x[0])
nodes.append(temp)
if stack:
if stack[-1].left:
stack[-1].right = temp
stack.pop()
else:
stack[-1].left = temp
if x[1] == "0":
stack.append(temp)
for x in nodes:
if x.left and x.left.value != "$":
x.children.append(x.left)
x.left.parent = x
if x.right and x.right.value != "$":
x.parent.children.append(x.right)
x.right.parent = x.parent
for x in nodes:
x.children = x.children[::-1]
lst1 = [nodes[0]]
for x in lst1:
if x.children:
lst1 += x.children
print(" ".join([x.value for x in lst1]))一步一步来。先把前序输入+内外节点的信息转成二叉树，第二步是把二叉树转成原来的树，第三步是bfs镜像输出。
python
# 叶晨熙 化学与分子工程
class Noden:
def __init__(self, value):
self.child = []
self.value = value
self.parent = None
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
self.parent = None
def bfs(noden):
queue.pop(0)
out.append(noden.value)
if noden.child:
for k in reversed(noden.child):
queue.append(k)
if queue:
bfs(queue[0])
def ex(node):
ans.append(node.value)
if node.left:
ex(node.left)
if node.right:
ex(node.right)
def reverse(node):
if node.right == None:
return node
else:
return reverse(node.parent)
def build(s, node, state):
if not s:
return
if state == '0':
new = Node(s[0][0])
node.left = new
new.parent = node
else:
pos = reverse(node.parent)
new = Node(s[0][0])
pos.right = new
new.parent = pos
build(s[1:], new, s[0][1])
def bi_to_n(node):
if node.left:
if node.left.value != '$':
newn = Noden(node.left.value)
dic[node.left] = newn
dic[node].child.append(newn)
newn.parent = dic[node]
bi_to_n(node.left)
if node.right:
if node.right.value != '$':
newn = Noden(node.right.value)
dic[node.right] = newn
dic[node].parent.child.append(newn)
newn.parent = dic[node].parent
bi_to_n(node.right)
n = int(input())
k = input().split()
root = Node(k[0][0])
k.pop(0)
if k:
build(k, root, k[0][1])
ans = []
ex(root)
#print(ans)
dic = {}
dic[root] = Noden(root.value)
bi_to_n(root)
rootn = dic[root]
#print(rootn)
queue = [rootn]
out =[]
bfs(rootn)
print(' '.join(out))就是按照伪满二叉树构造特点分层。遇到1标记的叶子节点就说明下一个是兄弟节点上移一层输出。
python
# 赵策 数学科学学院
from collections import defaultdict
n=int(input())
preorder=input().split()
root,type=list(preorder[0])
dic={}
nodes=[root]
dic[root]=type
tier=defaultdict(list)
tier[0].append(root)
level=0
for i in range(1,n):
name,type=list(preorder[i])
dic[name]=type
if dic[nodes[-1]]=='1':
level-=1
else:
level+=1
nodes.append(name)
if name!='$':
tier[level].append(name)
res=''
for i in sorted(tier.items()):
res+=''.join(i[1])[::-1]
print(' '.join(res))镜面映射简单，每层倒着输出就行；关键是这个树怎么构建，其实是斜着来表示树的层级，具体实现有点类似dfs，遇到顶就回溯
构建的数据结构很有意思，其实就是一个双层列表，我给他起了个名字叫梯子
python
# 赵新坤 物理学院
class ladder:
def __init__(self):
self.height=-1
self.matrix=[]
def add_level(self):
self.height+=1
self.matrix.append([])
def insert_i_level(self,node,level):
if self.height<level:
self.add_level()
self.matrix[level].append(node)
def traversal(Ladder):
ans=[]
for i in range(Ladder.height+1):
stack=[]
for j in Ladder.matrix[i]:
stack.insert(0,j)
ans.extend(stack)
print(' '.join(ans))
n=int(input())
data=[str(x) for x in input().split()]
L=ladder()
level=0
while data:
# print(f'current level is {level}')
p=data.pop(0)
if p =='$1':
level-=1
# print('turn right')
else:
L.insert_i_level(p[0],level)
# print(f'add {p[0]} into level {level}')
if p[-1]!='1':
level+=1
else:
level-=1
#for i in range(L.height+1):
# print(L.matrix[i])
traversal(L)