平衡二叉搜索树

Question

平衡二叉搜索树

javaarraysalgorithmrecursionbinary-search-tree

7

好的，我正在尝试让二叉搜索树平衡，我知道为什么它不能工作，但我不知道如何修复它。这是我用来平衡的方法。

    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是预定义的私有int变量，values也是预定义的Object[]。Root是我的不平衡树起始节点。首先，我知道我的数组是按相反顺序添加值的。现在我只是测试用1、2、3、4、5、6添加到树中，所以我的数组输出为654321。我不确定我需要如何将值的添加放置到我的数组中，以便它们按正确的升序而不是降序添加。

现在当我看我的代码时，我知道balanceRecursive()方法永远不会用于实现数组的前一半。我的问题是我不知道如何编写它才能这样做。我被要求使用递归来完成这个任务，但我对递归不是很熟悉。我可以用迭代来完成这个任务，但严格定义必须使用递归。

平衡应该像这样工作：平衡（）算法

检查树是否为空如果是，则打印“空树” 返回

如果树不为空创建对象数组，大小与树相同将索引设置为0 以升序填充数组（createAscendingArray()）清除树从对象数组重新填充树（balanceRecursive()）将值数组设置为null

（我已经编写了计算树中节点数的count()方法和清空树的clear()方法）

balanceRecursive()应该执行以下操作使用values数据成员重新填充树。这些必须按适当的顺序添加，以创建平衡的树。

添加中间元素这将创建两个子数组，一个左侧和一个右侧添加这些子数组的中间值这将创建更多的子数组继续添加子数组的中间值，直到没有

我知道对于这个方法，我从来没有使用过更大的子数组，并且那就是我无法实现的递归部分。有什么建议可以清理我的递归吗？

编辑：我将我的createAscendingArray()更改为以下内容：

    private void createAscendingArray(TreeNode<E> current){

    if(current == null)
        return;
    createAscendingArray(current.getLeftNode());
    values[index] = current.getData();
    index++;
    createAscendingArray(current.getRightNode());



}

我应该像BST的inOrder遍历一样工作，我是正确的吗？

- Neonjoe

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andy Jones · Accepted Answer

首先，您不需要复制旧树。您可以使用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>，这样在读取时就不需要强制转换为类型 E。