algorithm - 从预购构建 BST

Question

像许多新手一样，递归让我头晕目眩。我查了很多关于 SO 的答案/解释。但我仍然不清楚这个概念。 (这不是作业，我正在尝试重新学习我没有学过的东西，递归从来都不是一个字符串点)

给定一个先序遍历，构造一棵二叉树。对于递归，它必须看似简单 :) 但我就是无法理解。

我看到 arr 的顺序必须按照插入节点的顺序。让我烦恼的是:

1. 如果节点已经有左/右怎么办？这是如何运作的？

2. 递归如何插入节点，比如下面的预序？

   12, 10, 6, 13
   

15为根、5、3、左

6 作为 10 的左 child 如何正确插入？

    12
 10   13
6*

这是框架代码:

main()
{
   int[] arr = {};
   //make the first node a root node.
   node n = new node(arr[0]);
   buildbst(n, arr, 0)
}

buildbst(node root, int[] arr, int i)
{
   if (i == arr.length) return;

   if (arr[i] < root.data)
      root.left = new node (arr[i]);
   else
      root.right = new node(arr[i]);

   buildbst(root.left, arr, i++);
   buildbst(root.right, arr, i++);
}

编辑:

我刚刚意识到，如果我传入递归调用 buildbst(root.left, arr+i, i++)那是正确的方法吗？还是我处理这一切都是错误的 - 动态规划和递归以及分而治之的大杂烩......

Answer 1

1. 它不能已经有左/右 child 。你称它为根，它没有 child 开始。然后你为左边的 child 调用它并在适当的地方创建 child 并为这些 child 调用函数等等。一旦你向右移动，你就再也不会访问左边的 child ，并且你无法从对其子节点调用的函数到达节点(因为除了递归堆栈之外，树上没有任何连接)。

2. 这是给定 12, 10, 6, 13 时应该发生的情况:

   • 创建根 12
   • 调用 buildbst(node(12), arr, 1)
     • 创建 node(12).left = node(10)
     • 调用 buildbst(node(10), arr, 2)
       • 创建 node(10).left = node(6)
       • 调用 buildbst(node(6), arr, 3)
         • 13 > 12，必须是 12 的右 child ，所以什么都不做
       • 13 > 12，必须是 12 的右 child ，所以什么都不做
     • 创建 node(12).right = node(13)
     • 调用 buildbst(node(13), arr, 3)
       • 哦，看，没有更多元素了，我们完成了。

以上不是您的代码会发生的情况，原因有两个:

• 你的代码只会创建一个左或右 child ，而不是两者(因为 if-else))
• 你的代码没有must be right child of '12'检查，有点复杂

下面的代码应该覆盖它。

node buildbst(int[] arr)
{
   node n = new node(arr[0]);
   // 9999999999 is meant to be > than the biggest element in your data
   buildbst(n, arr, 1, 9999999999);
   return node;
}

int buildbst(node current, int[] arr, int i, int biggestSoFar)
{
    if (i == arr.length) return i;

    // recurse left
    if (arr[i] < current.data)
    {
      current.left = new node(arr[i++]);
      i = buildbst(current.left, arr, i, current.data);
    }

    // recurse right
    if (i < arr.length && arr[i] < biggestSoFar)
    {
      current.right = new node(arr[i++]);
      i = buildbst(current.right, arr, i, biggestSoFar);
    }

    return i;
}

解释:

biggestSoFar 的目的是防止:

    15                          15
   /                            /\
  5     versus (the correct)   5  20
 / \                          /
1   20                       1

例如从15向左递归时，我们需要在获取元素> 15时立即停止处理元素，这将在我们获取时发生20。因此，我们传递 current.data 并在获得更大的值时停止处理元素。

例如，当从 5 开始递归时，我们需要在获得元素 > 15 时立即停止处理元素，这将在我们获得 时发生20。因此，我们传递 biggestSoFar 并在获得更大值时停止处理元素。