[Today I Learned 07] 1. ツリー巡り


バイナリ検索ツリーとは?


親ノードに左右の子ノードを持つツリー.つまり、親ノードとは、2つのサブノードしかないツリーのことです.

2.ツリーサイクル

  • 前列巡査順はRoot-Left-Rightであった.
  • 中尉の巡察順序はLeft-Root-Rightであった.
  • 後列巡回順はLeft-Right-Rootであった.
    上記のようなバイナリツリーがある場合
    前列の順番は루트, 왼쪽, 오른쪽、つまり3 2 1 4 5 6 7です.
    中位数の順序は왼쪽, 루트, 오른쪽、すなわち1 2 3 5 4 6 7である.
    後列の順序は왼쪽, 오른쪽, 루트、すなわち1 2 5 7 6 4 3である.
  • 3.巡视茨利(#1991)


    上の概念で適切な問題を解く.

    質問する


    バイナリツリーを入力し、前列(preorder遍歴)、中列(inorder遍歴)、後列(postorder遍歴)の結果を出力するプログラムを作成します.

    例えば、上記のバイナリツリーを入力と、
    前衛巡視結果:ABDCEFG/(ルート)(左サブ)(右サブ)
    中位数結果:DBEACFG/(左サブアイテム)(ルート)(右サブアイテム)
    次の結果:DBGFCA/(左サブアイテム)(右サブアイテム)(ルート)
    いいですよ.

    入力


    第1行は、バイナリツリー内のノードの個数N(1≦N≦26)を与える.2行目からN行目には、各ノードとその左側のサブノードと右側のサブノードが与えられる.ノード名はAから始まり,アルファベット大文字順に並び,Aは常にルートノードである.サブノードがない場合.に表示されます.

    しゅつりょく


    1行目は前列、2行目は中列、3行目は後列の結果を出力します.行ごとにN文字を出力し、スペースを残さずに済みます.
    from sys import stdin
    input = stdin.readline
    
    N = int(input())
    graph = {}
    
    for _ in range(N):
        root, *child = map(str, input().split())
        graph[root] = child
    
    answer1 = []
    def pre_order(node):
        answer1.append(node)
        temp = graph[node]
        if '.' != temp[0]:
            pre_order(temp[0])
        if '.' != temp[1]:
            pre_order(temp[1])
    
    answer2 = []
    def in_order(node):
        temp = graph[node]
        if '.' != temp[0]:
            in_order(temp[0])
        answer2.append(node)
        if '.' != temp[1]:
            in_order(temp[1])
    
    answer3 = []
    def post_order(node):
        temp = graph[node]
        if '.' != temp[0]:
            post_order(temp[0])
        if '.' != temp[1]:
            post_order(temp[1])
        answer3.append(node)
    
    pre_order('A')
    in_order('A')
    post_order('A')
    print(''.join(answer1))
    print(''.join(answer2))
    print(''.join(answer3))