[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))
Reference
この問題について([Today I Learned 07] 1. ツリー巡り), 我々は、より多くの情報をここで見つけました https://velog.io/@yunchanpark/Today-I-Learned-07-1.-트리-순회テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol