白駿5639バイナリ検索ツリー/python

1294 ワード
テキストリンク

  • を入力して電位巡視を行います.
  • 入力値の個数は与えられていない.
  • ノードの数が正しくない(10000以下)ため、入力方法も重要である
    • .
    出力
  • 本/左/右>左/右/根.
  • preorder=[]フォワードツアー結果のボウル.
  • while,try~文で値が入力されるまで.
    • function : postorder(start, end)
  • 配列のインデックスを返し、後方巡視
    • を行う.
  • root = preorder [ start ]
    ->ルートノード
    • に設定
  • 配列を巡り、右サブノードの位置(idx)を検索します.
  • start = start + 1, end = idx//start = idx, end = end
  • は、再帰関数を再呼び出す2つの部分に分かれている.
  • 印刷(ルート)>>後列巡回、送信後出力ルートノード.
  • if start>=end:すべての配列を返し、
    • を返します.
    import sys

sys.setrecursionlimit(10 ** 6)

preorder = []


def postorder(start, end):
    if start >= end:
        return
    root = preorder[start]

    if preorder[end - 1] <= root:
        postorder(start + 1, end)
        print(root)
        return

    idx = 0
    for i in range(start + 1, end):
        if preorder[i] > root:
            idx = i
            break
    postorder(start + 1, idx)
    postorder(idx, end)
    print(root)


while True:
    try:
        preorder.append(int(sys.stdin.readline()))
    except:
        break

postorder(0, len(preorder))
    [航海99 3期]WIL 58初回ログ
    毎日5分間「パラメータ」をエンコード