03720: 文本二叉树

http://cs101.openjudge.cn/practice/03720/

如上图，一棵每个节点都是一个字母，且字母互不相同的二叉树，可以用以下若干行文本表示:

A
-B
--*
--C
-D
--E
---*
---F

在这若干行文本中：

每个字母代表一个节点。该字母在文本中是第几行，就称该节点的行号是几。根在第1行
每个字母左边的'-'字符的个数代表该结点在树中的层次（树根位于第0层）
若某第 i 层的非根节点在文本中位于第n行，则其父节点必然是第 i-1 层的节点中，行号小于n,且行号与n的差最小的那个
若某文本中位于第n行的节点(层次是i) 有两个子节点，则第n+1行就是其左子节点，右子节点是n+1行以下第一个层次为i+1的节点
若某第 i 层的节点在文本中位于第n行，且其没有左子节点而有右子节点，那么它的下一行就是 i+1个'-' 字符再加上一个 '*'

给出一棵树的文本表示法，要求输出该数的前序、后序、中序遍历结果

输入

第一行是树的数目 n

接下来是n棵树，每棵树以'0'结尾。'0'不是树的一部分每棵树不超过100个节点

输出

对每棵树，分三行先后输出其前序、后序、中序遍历结果两棵树之间以空行分隔

样例输入

2
A
-B
--*
--C
-D
--E
---*
---F
0
A
-B
-C
0

样例输出

ABCDEF
CBFEDA
BCAEFD

ABC
BCA
BAC

来源: Guo Wei

python

class Node:
    def __init__(self, x, depth):
        self.x = x
        self.depth = depth
        self.lchild = None
        self.rchild = None

    def preorder_traversal(self):
        nodes = [self.x]
        if self.lchild and self.lchild.x != '*':
            nodes += self.lchild.preorder_traversal()
        if self.rchild and self.rchild.x != '*':
            nodes += self.rchild.preorder_traversal()
        return nodes

    def inorder_traversal(self):
        nodes = []
        if self.lchild and self.lchild.x != '*':
            nodes += self.lchild.inorder_traversal()
        nodes.append(self.x)
        if self.rchild and self.rchild.x != '*':
            nodes += self.rchild.inorder_traversal()
        return nodes

    def postorder_traversal(self):
        nodes = []
        if self.lchild and self.lchild.x != '*':
            nodes += self.lchild.postorder_traversal()
        if self.rchild and self.rchild.x != '*':
            nodes += self.rchild.postorder_traversal()
        nodes.append(self.x)
        return nodes


def build_tree():
    n = int(input())
    for _ in range(n):
        tree = []
        stack = []
        while True:
            s = input()
            if s == '0':
                break
            depth = len(s) - 1
            node = Node(s[-1], depth)
            tree.append(node)

            # Finding the parent for the current node
            while stack and tree[stack[-1]].depth >= depth:
                stack.pop()
            if stack:  # There is a parent
                parent = tree[stack[-1]]
                if not parent.lchild:
                    parent.lchild = node
                else:
                    parent.rchild = node
            stack.append(len(tree) - 1)

        # Now tree[0] is the root of the tree
        yield tree[0]


# Read each tree and perform traversals
for root in build_tree():
    print("".join(root.preorder_traversal()))
    print("".join(root.postorder_traversal()))
    print("".join(root.inorder_traversal()))
    print()

python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def parse_tree(lines):
    # last_node_at_level[i] 记录最近一个深度为 i 的真实节点
    last_node_at_level = {}
    # expect_right[i] 标记深度 i 的节点下一个真实节点应该挂在它的 right
    expect_right = {}

    root = None

    for line in lines:
        # 计算深度
        level = 0
        while line[level] == '-':
            level += 1
        val = line[level]

        if val == '*':
            # 标记：depth = level-1 的节点左子为空，下一个真实节点挂到它的 right
            expect_right[level-1] = True
            # 不创建实际节点
            continue

        node = Node(val)
        # 第一个节点当作 root
        if level == 0:
            root = node

        # 如果不是根，就找父节点
        if level > 0:
            parent = last_node_at_level[level-1]
            # 如果父节点标记了 expect_right，则挂到 right
            if expect_right.get(level-1, False):
                parent.right = node
                expect_right[level-1] = False  # 重置标记
            else:
                # 否则，先挂左，再挂右
                if parent.left is None:
                    parent.left = node
                else:
                    parent.right = node

        # 更新同层最新节点
        last_node_at_level[level] = node

    return root

def preorder(root):
    return '' if not root else root.val + preorder(root.left) + preorder(root.right)

def inorder(root):
    return '' if not root else inorder(root.left) + root.val + inorder(root.right)

def postorder(root):
    return '' if not root else postorder(root.left) + postorder(root.right) + root.val

if __name__ == '__main__':
    import sys
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    idx = 1

    for ti in range(n):
        # 读取一棵树的所有行
        lines = []
        while data[idx] != '0':
            lines.append(data[idx])
            idx += 1
        idx += 1  # 跳过 '0'

        root = parse_tree(lines)
        # 输出三种遍历
        print(preorder(root))
        print(postorder(root))
        print(inorder(root))
        if ti != n-1:
            print()

03720: 文本二叉树 ​

03720: 文本二叉树