data-structures - 从二叉树的前序遍历序列中找到中序遍历

Question

我只给出了一个二叉树的前序遍历序列（例如{a, b, d, c, e}），任务是从中找出有序序列。如果这是一个重复的问题，请原谅我....谢谢

Answer 1

我认为您无法仅根据二叉树的前序遍历来找出中序遍历。正如您对二叉搜索树所说，排序将为您提供中序遍历。

Answer 2

我在 Python 中准备了一个函数来从后序遍历中获取前序遍历。也许这会帮助你希望。

例如，

如果像这样 输入后序输入后序遍历：ACEDBHIGF

预购将是 预购遍历是 GAECFTJOLP

中序将是 中序遍历是 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)