1

我正在尝试在给定排序值的 ArrayList 的情况下构建二叉搜索树。在尝试创建最有效的树时，我取中间值，并将其添加到树中。然后递归地取最左边的值并找到这些值的中间输入 THAT 到树中。

完成后，右侧也是如此。

我使用以下行调用 balanceBST() 方法：

balanceBST(iterator.list, 0, iterator.list.size() - 1);

假设 iterator.list 是一个包含以下值的整数的 ArrayList：
{5, 17, 24, 31, 44, 55, 71, 81, 82, 83, 84, 85, 97}

public void balanceBST(ArrayList<E> values, int start, int end){
  int mid = (start + end) / 2;
  while(mid >= 0 && end > mid){ 
      insert(values.get(mid));
      balanceBST(values, start, mid - 1);
      balanceBST(values, mid + 1, end);
    }
}

insert(element) 方法负责将事物输入二叉树。

这会产生各种错误，我认为它发生在 mid 接近 0 或 end 接近 mid 时会发生混乱，但我自己遵循了逻辑，我不明白为什么会崩溃。

编辑：

对于那些将来阅读本文的人，非常感谢@David。以下解决了该问题：

  public void balanceBST(ArrayList<E> values, int start, int end){
  int mid = (start + end) / 2;
  if(end < 0 || start > end) return;
      insert(values.get(mid));
      balanceBST(values, start, mid - 1);
      balanceBST(values, mid + 1, end);
  }
4

1 回答 1

2

当您对 balanceBST 进行递归调用时，您不希望 while 循环会导致重复插入条目。将 while 更改为终止测试并返回。注意只插入 >= 0 和 < 结束并在两者都为假时退出。

于 2013-08-04T08:50:58.713 回答