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

8967 ワード
jungle TIL テキストリンク

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


親ノードに左右の子ノードを持つツリー.つまり、親ノードとは、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))
    [ホームゲーム]A number game
    【C#Lanmoda式】