0

我正在构建一个递归 Java 方法来平衡使用每个节点中的权重的二叉搜索树（使用整数，但设计为通用）。出于我的目的，节点的权重定义为子节点数 + 1。

  2
/   \
1   3

The weight of the root is 3, and the weight of both leaves is 1.

在平衡结束时，任何节点的值都应该是以该节点为根的子树中所有节点的值的中值。

这是我的代码：

public void weightBalance (BinarySearchTree<AnyType> t) {

    // Base case
    if (t.getRoot().left == null && t.getRoot().right == null) {
        return;
    }

    // Get median of tree
    AnyType median = t.getMedian();

    // Create new BST with median as root
    BinarySearchTree<AnyType> newTree = new BinarySearchTree<AnyType>();
    newTree.insert(median);

    // Insert all values except median into new BST
    ArrayList<AnyType> stack = new ArrayList<AnyType>();
    inorderTraverse(t.getRoot(), stack);
    Iterator<AnyType> itr = stack.iterator();
    while (itr.hasNext()) {
        AnyType temp = itr.next();
        if (temp != median) {  // Comparing values or reference?
            newTree.insert(temp);
        }
    }

    // Replace old BST with new BST
    t = newTree;  // t is a copy of the reference, is this the problem?

    // Recurse through children
    // Tree constructor for reference:
    // public BinarySearchTree (BinaryNode<AnyType> t) {
    //  root = t;
    // }

    if (t.getRoot().left != null) {
        weightBalance(new BinarySearchTree(t.getRoot().left));
    }
    if (t.getRoot().right != null) {
        weightBalance(new BinarySearchTree(t.getRoot().right));
    }
}

我正在尝试修改树而不返回任何内容，但代码不会更改树。我知道我在某处通过引用传递和按值传递搞砸了，但我不知道在哪里 - 任何人都可以帮忙吗？我花了几个小时调试，但在调试递归时我真的很困惑。

4

1 回答 1

0

平衡算法相当普遍并且有据可查，例如 TreeMap 是一个 BST，你可以看到它的源代码。我从未见过它使用数据副本，我怀疑你需要创建一个堆栈或构建一个新树来平衡它。

正常行为是向左或向右旋转节点，或者两者的更复杂组合。这减少了所涉及的工作并且不会产生垃圾。

于 2012-03-26T08:04:42.460 回答