1

像许多新手一样，我的头因递归而爆炸。我查找了很多关于 SO 的答案/解释。但我仍然不清楚这个概念。（这不是家庭作业，我正在尝试重新学习我没有学过的东西，递归从来都不是字符串点）

给定一个前序遍历，构造一棵二叉树。使用递归，它必须看起来很简单:) 但我就是不明白。

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

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

  2. 递归如何插入节点，例如以下预购？

    12, 10, 6, 13

15 是根，5、3 和左

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

    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++) 是正确的方法吗？或者我是不是把这一切都搞错了——动态编程和递归以及分而治之的混搭......

4

1 回答 1

0

  1. 它不能已经有左/右孩子。您称它为根，它没有子项可启动。然后你为左孩子调用它并在适当的地方创建孩子并为这些孩子调用函数等等。一旦你向右走，你就再也不会访问左边的孩子，而且你不能从一个调用它的孩子的函数到达一个节点（因为树上没有连接，除了递归堆栈）。

  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, 所以什么也不做
        • 13 > 12, 必须是的右孩子12, 所以什么也不做
      • 创造node(12).right = node(13)
      • 来电buildbst(node(13), arr, 3)
        • 哦，看，没有更多的元素，我们完成了。

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

  • 您的代码只会创建一个左孩子或右孩子，而不是两者（因为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，如果我们获得更大的值，我们会传递并停止处理元素。

于 2013-03-01T08:58:58.750 回答