好的,我正在尝试让二叉搜索树达到平衡,我知道它为什么不起作用,但我不知道如何修复它。这就是我的平衡方法。
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<E> 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 是一个预定义的私有(private) int 变量,values 也是一个预定义的 Object[]。 Root 是我的不平衡树开始处的节点。首先,我知道我的数组以相反的顺序添加值。现在我只是测试将 1、2、3、4、5、6 添加到树中,所以我的数组结果为 654321。我不确定我需要如何将值添加到我的数组,以便它将以正确的升序而不是降序添加它们。
现在,当我查看我的代码时,我知道 balanceRecursive() 方法永远无法实现数组的上半部分。我的问题是我不知道如何写它才能做到。我的任务是用递归来做这件事,我不太熟悉。我可以用迭代来做到这一点,但严格定义我必须使用递归。
平衡应该是这样工作的: balance() 的算法
- 检查树是否为空
o 如果是,打印“Empty Tree”
o 返回
- 如果树不为空
o 创建树大小的对象数组
o 将索引设置为 0
o 使用升序排列的所有值填充数组 (createAscendingArray())
o 清除树
o 从对象数组(balanceRecursive())重新填充树
o 将值数组设置为空
(我已经为 count() 编写了方法来计算树中的节点数,并为 clear() 编写了清空树的方法)
balanceRecursive() 应该做以下事情 用值数据成员中的值重新填充树。这些必须以适当的顺序添加以创建平衡树。
添加中间元素
这将创建两个子数组,一个左侧和一个右侧
在那些子数组的中间添加
这会创建更多的子数组
不断添加子数组的中间,直到没有为止
我知道对于这种方法,我从不使用更大的子数组集,这是我不知道如何实现的递归部分。关于如何清理我的递归有什么建议吗?
编辑:
我将 createAscendingArray() 更改为以下内容:
private void createAscendingArray(TreeNode<E> current){
if(current == null)
return;
createAscendingArray(current.getLeftNode());
values[index] = current.getData();
index++;
createAscendingArray(current.getRightNode());
}
这应该像 BST 的 inOrder 遍历一样起作用,对吗?
最佳答案
首先,你不需要复制老树。您可以使用 Stout-Warren algorithm 就地重新平衡它,尽管不可否认,这比只读出旧树、清除它并创建一个新树要复杂一些。
但至于你的实际问题,你想要的递归函数是
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>
所以你不需要转换为类型 E
当你读出它时。
关于java - 平衡二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20341423/