binary-search-tree - BST 上的预购和“tree_insert”

Question

如果我有一个 BST（称之为 - T）并在其上运行 PRE-ORDER，我如何显示/证明在我从预购中获得的序列上运行函数“tree_insert”，我得到完全相同的树- T（我开始）回来了？

谢谢，

Answer 1

对于给定的树的前序遍历，可以形成多个 BST。如果您在预购遍历的同时还进行了 INORDER 遍历，则可以生成唯一的 BST。

Answer 2

例如，假设您有 3 个元素。

插入时，将插入的第一个元素作为根，然后下一个元素（无论是小还是大）将相应地放置在左侧或右侧。前序遍历就是先访问root，然后递归访问左孩子，再递归访问右孩子。所以预购后会显示根，较小的元素，然后是较大的元素。现在尝试再次插入这 3 个元素。您将收到相同的树。（插入的第一个元素将是根。然后较小的元素将再次向左移动，较大的元素将自动向右移动）。您可以使用 6 个不同的场景和 3 个元素对此进行建模。

场景 1：要插入的元素 = {1, 2, 3} 根 = 1，右孩子 = 2，最右边 = 3

做preOrder时，先访问1。没有左孩子，所以接下来访问 2。2 没有左孩子，所以接下来访问 3。(1, 2, 3)

场景 2：要插入的元素 = {2, 1, 3} 根 = 2，左孩子 = 1，右孩子 = 3

做 preOrder 时，首先访问 2。留下孩子 1，所以接下来要访问它。右孩子是 3，所以接下来访问它。(2, 1, 3)

场景 3：要插入的元素 = {3, 1, 2} 根 = 3，左孩子 = 1，左孩子的右孩子（高度为 1）= 2

做 preOrder 时，先访问 3。左孩子是 1，所以接下来访问它。没有 1 的左孩子，所以接下来访问 3。(3, 1, 2)

还有 3 个场景，您可以自己写出来并检查。