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 函数：读取输入，构造树，然后输出前序遍历和后序遍历的结果。

24729: 括号嵌套树 ​

24729: 括号嵌套树