[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))