24729: 括号嵌套树
http://cs101.openjudge.cn/practice/24729/
可以用括号嵌套的方式来表示一棵树。表示方法如下：
- 如果一棵树只有一个结点，则该树就用一个大写字母表示，代表其根结点。
- 如果一棵树有子树，则用“树根(子树1,子树2,...,子树n)”的形式表示。树根是一个大写字母，子树之间用逗号隔开，没有空格。子树都是用括号嵌套法表示的树。
给出一棵不超过26个结点的树的括号嵌套表示形式，请输出其前序遍历序列和后序遍历序列。
输入样例代表的树如下图：
输入
一行，一棵树的括号嵌套表示形式
输出
两行。第一行是树的前序遍历序列，第二行是树的后序遍历序列
样例输入
A(B(E),C(F,G),D(H(I)))样例输出
ABECFGDHI
EBFGCIHDA来源：Guo Wei
下面两个代码。先给出用类表示node。
思路：对于括号嵌套树，使用stack记录进行操作中的父节点，node记录正在操作的节点。每当遇见一个字母，将其设为node，并存入stack父节点中；遇到'('，即对当前node准备添加子节点，将其append入stack中，node重新设为None；遇到')'，stack父节点操作完毕，将其弹出并作为操作中的节点node，不断重复建立树，同时最后返出的父节点为树的根root。
前序遍历和后序遍历只要弄清楚意思，用递归很好写，注意这道题并不是二叉树，需要遍历解析树。
python
class TreeNode:
def __init__(self, value): #类似字典
self.value = value
self.children = []
def parse_tree(s):
stack = []
node = None
for char in s:
if char.isalpha(): # 如果是字母，创建新节点
node = TreeNode(char)
if stack: # 如果栈不为空，把节点作为子节点加入到栈顶节点的子节点列表中
stack[-1].children.append(node)
elif char == '(': # 遇到左括号，当前节点可能会有子节点
if node:
stack.append(node) # 把当前节点推入栈中
node = None
elif char == ')': # 遇到右括号，子节点列表结束
if stack:
node = stack.pop() # 弹出当前节点
return node # 根节点
def preorder(node):
output = [node.value]
for child in node.children:
output.extend(preorder(child))
return ''.join(output)
def postorder(node):
output = []
for child in node.children:
output.extend(postorder(child))
output.append(node.value)
return ''.join(output)
# 主程序
def main():
s = input().strip()
s = ''.join(s.split()) # 去掉所有空白字符
root = parse_tree(s) # 解析整棵树
if root:
print(preorder(root)) # 输出前序遍历序列
print(postorder(root)) # 输出后序遍历序列
else:
print("input tree string error!")
if __name__ == "__main__":
main()用字典表示node
python
def parse_tree(s):
stack = []
node = None
for char in s:
if char.isalpha(): # 如果是字母，创建新节点
node = {'value': char, 'children': []}
if stack: # 如果栈不为空，把节点作为子节点加入到栈顶节点的子节点列表中
stack[-1]['children'].append(node)
elif char == '(': # 遇到左括号，当前节点可能会有子节点
if node:
stack.append(node) # 把当前节点推入栈中
node = None
elif char == ')': # 遇到右括号，子节点列表结束
if stack:
node = stack.pop() # 弹出当前节点
return node # 根节点
def preorder(node):
output = [node['value']]
for child in node['children']:
output.extend(preorder(child))
return ''.join(output)
def postorder(node):
output = []
for child in node['children']:
output.extend(postorder(child))
output.append(node['value'])
return ''.join(output)
# 主程序
def main():
s = input().strip()
s = ''.join(s.split()) # 去掉所有空白字符
root = parse_tree(s) # 解析整棵树
if root:
print(preorder(root)) # 输出前序遍历序列
print(postorder(root)) # 输出后序遍历序列
else:
print("input tree string error!")
if __name__ == "__main__":
main()实现了括号嵌套表示树的解析以及前序、后序遍历：
python
class Node:
def __init__(self, val):
self.val = val
self.children = []
def parse_tree(s, i=0):
# 当前字符为结点的值（大写字母）
node = Node(s[i])
i += 1
# 如果下一个字符是'('，说明有子树
if i < len(s) and s[i] == '(':
i += 1 # 跳过'('
while True:
child, i = parse_tree(s, i) # 解析一个子树
node.children.append(child)
# 子树之间用逗号隔开
if i < len(s) and s[i] == ',':
i += 1 # 跳过逗号，继续解析下一个子树
else:
break
i += 1 # 跳过')'
return node, i
def preorder(node, res):
if node is None:
return
res.append(node.val)
for child in node.children:
preorder(child, res)
def postorder(node, res):
if node is None:
return
for child in node.children:
postorder(child, res)
res.append(node.val)
def main():
# 读入一行树的括号嵌套表示形式
s = input().strip()
root, _ = parse_tree(s)
pre_res = []
preorder(root, pre_res)
post_res = []
postorder(root, post_res)
print("".join(pre_res))
print("".join(post_res))
if __name__ == '__main__':
main()代码说明
- Node 类：定义了树的结点，包含结点值
val和子结点列表children。 - parse_tree 函数：采用递归下降的方式解析字符串。遇到大写字母创建结点；若后续遇到 '(' 则说明存在子树，解析所有子树直到遇到 ')'。
- preorder 和 postorder 函数：分别实现前序遍历（先访问结点，再遍历所有子树）和后序遍历（先遍历所有子树，最后访问结点）。
- main 函数：读取输入，构造树，然后输出前序遍历和后序遍历的结果。
这道题的核心在于理解左孩子右兄弟（Left-Child Right-Sibling, LCRS）表示法中，二叉树遍历与原多叉树遍历的关系：
- 二叉树的前序遍历 (Root, Left, Right) = 原多叉树的前序遍历。在 LCRS 中，先访问根，再访问第一个孩子，再访问兄弟，这恰好对应多叉树“根-子树1-子树2...”的顺序。
- 二叉树的中序遍历 (Left, Root, Right) = 原多叉树的后序遍历。这是最巧妙的一点。在二叉树中序遍历中，你会先遍历左子树（原多叉树的所有子孙），然后访问根节点，最后遍历右子树（原多叉树的后续兄弟节点）。对于多叉树的一个节点来说，它的“后序”意味着：先处理完它所有的子节点，再处理它自己。在二叉树结构中，处理完左子树（子孙）后紧接着访问根节点，正好完成了这个逻辑。
- 递归构建逻辑：多叉树转二叉树（左孩子右兄弟法）时，父节点只指向第一个子节点，而后续的兄弟节点应该链接在第一个子节点的右指针链上。
python
class Node:
def __init__(self, val):
self.val = val
self.left = None # 指向第一个孩子
self.right = None # 指向下一个兄弟
def buildTree(s):
i = 0
n = len(s)
def build():
nonlocal i
if i >= n:
return None
# 创建当前节点
node = Node(s[i])
i += 1
# 如果遇到 '('，表示接下来是子节点列表
if i < n and s[i] == "(":
i += 1 # 跳过 '('
# 第一个子节点作为左孩子
node.left = build()
curr = node.left
# 剩下的子节点（由逗号隔开）作为前一个子节点的右兄弟
while i < n and s[i] == ",":
i += 1 # 跳过 ','
curr.right = build()
curr = curr.right
# 处理完所有子节点，跳过 ')'
if i < n and s[i] == ")":
i += 1
return node
return build()
def Print(root):
pre_out = []
post_out = [] # 原多叉树的后序 = 二叉树的中序
def traverse(curr):
if not curr:
return
# 二叉树前序 = 原树前序
pre_out.append(curr.val)
# 递归左子树（原树的孩子）
traverse(curr.left)
# 二叉树中序位置 = 原树后序
post_out.append(curr.val)
# 递归右子树（原树的兄弟）
traverse(curr.right)
traverse(root)
print("".join(pre_out))
print("".join(post_out))
# 主程序
s = input().strip()
root = buildTree(s)
Print(root)