平衡二叉搜索树
好吧，我想要一个二元搜索树来平衡，我知道为什么它不起作用，但我不知道如何解决它。 这就是我的平衡方法。
public void balance(){ if(isEmpty()){ System.out.println("Empty Tree"); return; } if(!isEmpty()){ values = new Object[count()]; index = 0; createAscendingArray(root); clear(); balanceRecursive(0, index); values = null; } } private void createAscendingArray(TreeNode current){ if(current == null) return; if(current.getLeftNode() != null) createAscendingArray(current.getLeftNode()); else if(current.getRightNode() != null) createAscendingArray(current.getRightNode()); values[index] = current.getData(); index++; } private void balanceRecursive(int low, int high){ if(low == high) return; else if(low > high/2) balanceRecursive(high/2, high); else if(low < high/2) balanceRecursive(low, high/2); E insert = (E) values[(low + high)/2]; insertItem(insert); } 为了增加一些清晰度，index是预定义的私有int变量，values也是预定义的Object []。 Root是我的不平衡树开头的节点。 首先，我知道我的数组正在以相反的顺序添加值。 现在我只是测试1,2,3,4,5,6被添加到树中，所以然后我的数组出来654321.我不知道我需要如何添加值到我的数组，以便它将以正确的升序而不是降序添加它们。
现在当我查看我的代码时，我知道balanceRecursive（）方法永远不会用于实现数组的上半部分。 我的问题是我不知道如何写它以便它会。 我的任务是用递归来做这件事，我不太熟悉。 我可以用迭代来做到这一点，但严格定义我必须使用递归。
平衡应该像这样工作：平衡算法（）
- 检查树是否为空
o如果是，打印“空树”
o回归
- 如果树不是空的
o创建树大小的对象数组
o将索引设置为0
o使用ASCENDING顺序中的所有值填充数组（createAscendingArray（））
o清除树
o从Object数组重新填充树（balanceRecursive（））
o将values数组设置为null
（我已经为count（）编写了计算树中节点数的方法，并使用clear（）来清空树。
balanceRecursive（）应该执行以下操作：使用values数据成员中的值重新填充树。 必须以适当的顺序添加这些以创建平衡树。
-
添加中间元素
-
这会创建两个子arrays，左侧和右侧
-
添加这些子数组的中间部分
-
这会创建更多的子数组
-
继续添加子数组的中间，直到没有
我知道这个方法我从来没有使用更大的子数组，这是递归的一部分，我无法弄清楚如何实现。 关于如何清理递归的任何建议？
编辑：
我将createAscendingArray（）更改为以下内容：
private void createAscendingArray(TreeNode current){ if(current == null) return; createAscendingArray(current.getLeftNode()); values[index] = current.getData(); index++; createAscendingArray(current.getRightNode()); }
这应该像BST的inOrder遍历一样，对吗？
首先，您不需要复制旧树。 您可以使用Stout-Warren算法就地重新平衡它，但不可否认，这比仅读出旧树，清除它并创建一个新树要复杂一些。
但至于你的实际问题，你想要的递归函数是
private void balanceRecursive(int low, int high){ if(low == high) return; int midpoint = (low + high)/2; E insert = (E) values[midpoint]; insertItem(insert); balanceRecursive(midpoint+1, high); balanceRecursive(low, midpoint); }
另外，不要使用values对象数组，使用List这样在读出它时就不需要转换为E类型。
插入和删除时完成平衡：请参阅平衡树 。