1

我需要以以下（奇怪的）方式创建一个二叉搜索树：

我得到一个数组（A[n]）。A[1] 成为树的根。

  • 然后，我将 A[1]+A[2] 插入到根的左子树（subtree1，下面使用），并将 A[1]-A[2] 插入到根的右子树（subtree2）。

  • 我将 A[1]+A[2]+A[3] 插入 subtree1 (subtree3) 的左子树，将 A[1]+A[2]-A[3] 插入 subtree1 (subtree4) 的右子树。

  • 然后，我将 A[1]-A[2]+A[3] 插入到 subtree2 (subtree5) 的左子树和 A[1]-A[2]-A[3] 到 subtree2 (subtree6) 的右子树）。

  • 我对 subtree3、subtree4、subtree5、subtree6 重复，直到到达数组的末尾。

所以，基本上，数组的第一个元素成为树的根，然后我向下移动：每个左子树的值都是其父元素加上数组的下一个元素的总和，每个右子树的值都是它的父元素和数组中的下一个元素。

我知道我需要使用递归的概念，但要以一种修改的方式。在这里输入我的问题并试图向除了我的大脑之外的其他人解释它实际上使我形成它的方式给了我一些尝试的想法但我可以看到我正在处理的问题是一个常见的问题所以也许你可以给我对如何使用递归来构建树的一些指示。

环顾其他问题和讨论，我知道有一项反对提出完整解决方案的政策，所以我想明确表示我不是在寻求解决方案，而是寻求指导。如果有人想看看我可以告诉你我已经做了什么。

4

1 回答 1

0

进行递归的方法是始终假设您已经拥有一个工作函数。那么让我们看看[使用Java语法]...

Tree buildTree(int currentSum, int[] array, int index, boolean sign);

假设这行得通。那么你需要在索引 i 处构建一棵树吗？

// current value to look at at this level
int curValue = array[index];
// depending on sign, it may be negative
if (!sign) { 
  curValue *= -1;
}
// add it to the running total
int nodeValue = currentSum + curValue;
Node nd = new Node(nodeValue);

nd.left = buildTree(nodeValue, array, index + 1, true);
nd.right = buildTree(nodeValue, array, index + 1, false);

基本上就是这样。您需要处理边缘情况：index = array.length、创建第一个节点等

于 2011-03-24T01:27:33.360 回答