首页 文章

balancer 二叉搜索树

提问于
浏览 次
6

好的，我想要一个二元搜索树来 balancer ，我知道为什么它不起作用，但我不知道如何解决它 . 这就是我的 balancer 方法 .

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是我的不 balancer 树开始处的节点 . 首先，我知道我的数组正在以相反的顺序添加值 . 现在我只是测试1,2,3,4,5,6被添加到树中，所以然后我的数组出来654321.我不知道我需要如何添加值到我的数组，以便它将以正确的升序而不是降序添加它们 .

现在，当我查看我的代码时，我知道balanceRecursive（）方法永远不会用于实现数组的上半部分 . 我的问题是我不知道如何编写它以便它会 . 我的任务是用递归来做这件事，我不太熟悉 . 我可以用迭代来做到这一点，但严格定义我必须使用递归 .

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

  • 检查树是否为空

o如果是，打印“空树”

o回归

  • 如果树不是空的

o创建树大小的对象数组

o将索引设置为0

o使用ASCENDING顺序中的所有值填充数组（createAscendingArray（））

o清除树

o从Object数组重新填充Tree（balanceRecursive（））

o将values数组设置为null

（我已经为count（）编写了计算树中节点数的方法，并使用clear（）来清空树 .

balanceRecursive（）应该执行以下操作：使用values数据成员中的值重新填充树 . 必须以适当的顺序添加这些以创建 balancer 树 .

  • 添加中间元素

  • 这会创建两个子阵列，左侧和右侧

  • 添加这些子数组的中间部分

  • 这会创建更多的子数组

  • 继续添加子数组的中间，直到没有

我知道对于这个方法，我从不使用更大的子数组，这是递归的一部分，我无法弄清楚如何实现 . 关于如何清理递归的任何建议？

编辑：

我将createAscendingArray（）更改为以下内容：

private void createAscendingArray(TreeNode<E> current){

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



}

这应该像BST的inOrder遍历一样，对吗？

java arrays algorithm recursion binary-search-tree

2 回答

  • 8

    首先，您不需要复制旧树 . 您可以使用_1824411来就地重新 balancer 它，但不可否认，这比仅读出旧树，清除它并创建一个新树要复杂得多 .

    但至于你的实际问题，你想要的递归函数是

    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 .

    回复于
  • 1

    在插入和删除时完成 balancer ：请参阅Balancing Trees .

    回复于

相关问题