data-structures - 二分木の事前順トラバーサルシーケンスからインオーダートラバーサルを見つける

Question

二分木 ({a, b, d, c, e} など) の事前順序トラバーサル シーケンスのみを指定しました。タスクは、そこから順序シーケンスを見つけることです。これが重複した質問である場合はご容赦ください....ありがとう

Answer 1

バイナリ ツリーの preorder トラバーサルだけに基づいて inorder トラバーサルを見つけることはできないと思います。二分探索木についてあなたが言ったように、ソートはあなたに順不同のトラバーサルを与えます。

Answer 2

Python で関数を用意して、ポストオーダー トラバーサルからプリオーダー トラバーサルを取得しました。多分それはうまくいけばあなたを助けるでしょう.

例えば、

ポストオーダーをそのように 入力した場合 ポストオーダートラバーサルを入力してください: ACEDBHIGF

予約注文は 予約 注文トラバーサルは GAECFTJOLP

inorder は 次のようになります。in-order traversal は ABCDEFGHI です。

def from_post_order(post_order_items, order_type="pre"):
    bst = BinarySearchTree()
    values = [item for item in post_order_items]
    root = values[-1]  # the last item in the post_order item is ROOT
    bst.insert(root)  # insert ROOT
    values.pop(-1)  # and remove it from post_order_items

    left_child = []  # the left child of ROOT for Post-order
    right_child = []  # the right child of ROOT for Post-order
    for v in values:
        if v > root:
            right_child.append(v)
        else:
            left_child.append(v)

    for i in range(len(left_child + right_child)):
        if len(left_child) != 0:
            bst.insert(left_child[-1])  # insert left child
            left_child.pop(-1)  # remove the inserted left child from the list

        if len(right_child) != 0:
            bst.insert(right_child[-1])  # insert right child
            right_child.pop(-1)  # remove the inserted right child from the list

    if order_type == "pre":
        print("The pre-order traversal is ")
        bst.preorder(print)
    elif order_type == "in":
        print("The in-order traversal is ")
        bst.inorder(print)
    else:
        print("The post-order traversal is ")
        bst.postorder(print)