java - BinarySearchTree 中的 balance 方法有什么问题？（爪哇）

Question

我创建了一个假设平衡 BinarySearchTree 的方法。

说明是平衡方法应该更新树以使其平衡，这意味着子树高度之间的最大差异不超过 1。

通过以下过程：

• 在树中获取排序值的数组（我们有一个方法可以做到这一点）

• 将树的根分配给 buildTreeUtil 辅助方法的结果（如下所述）

• 调用assignFirst 来更新树的“first”属性

buildTreeUtil(E[], int, int, BSTNode parent) 辅助方法使用排序的值列表重建树。由于它有这个排序列表，它不必搜索插入新值的位置，因此它不会（也不应该）调用 add 方法。相反，它在添加新节点时有选择地从排序的值列表中获取值。它的算法如下：

• 如果“start”参数大于“end”参数，递归应该停止

• 创建一个新节点来存储列表中的中间元素

• 使用列表的左半部分将新节点的左引用分配给递归调用

• 使用列表的右半部分将新节点的右引用分配给递归调用

这是以下代码：

public void balance()
{
    this.root = buildTreeUtil(toArray(), 0, size(), first);
    assignFirst();
}

private BSTNode<E> buildTreeUtil(E[] values, int start, int end, BSTNode<E> parent)
{
    if(start > end)
    {
        return null;
    }
    int mid = (start + end)/2;
    BSTNode<E> node = new BSTNode<E>(values[mid]);

    node.left = buildTreeUtil(values, start, mid - 1, parent.left);

    node.right = buildTreeUtil(values, mid + 1, end, parent.right);

    return node;
}

private void assignFirst()
{
    if (root.left != null)
    {
        first.left = first;
    }
    else
        {
        first = root;
    }
}
@SuppressWarnings("unchecked")
public E[] toArray()
{
    ArrayList<E> aList = new ArrayList<E>();
    E[] arr = (E[]) new Comparable[this.numElements];
    toArray(this.root, aList);
    return aList.toArray(arr);
}

private void toArray(BSTNode<E> node, List<E> aList)
{
    if (node != null)
    {
        toArray(node.left, aList);
        aList.add(node.data);
        toArray(node.right, aList);
    }
}

这只是我剩下的代码，所以有一些有价值的背景信息。

public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;
private BSTNode<E> first;
// post: constructs an empty search tree
public BinarySearchTree()
{
    this.root = null;
    this.numElements = 0;
}
public class Iterator
{
    private BSTNode<E> currentNode;

    public Iterator()
    {
        currentNode = first;
    }

    public boolean hasNext()
    {
        return currentNode != null;
    }

    public E next()
    {
        E value = currentNode.data;
        currentNode = currentNode.next;
        return value;
    }
}
private static class BSTNode<E>
{
    public E data;
    public BSTNode<E> left;
    public BSTNode<E> right;
    public BSTNode<E> parent;
    public BSTNode<E> next;

    public BSTNode(E data)
    {
        this(data, null, null, null, null);
    }

    public BSTNode(E data, BSTNode<E> left, BSTNode<E> right, BSTNode<E> parent, BSTNode<E> next)
    {
        this.data = data;
        this.left = left;
        this.right = right;
        this.parent = parent;
        this.next = next;
    }
  }
}

我不确定错误发生在哪里，或者我是否在 buildTreeUtil 的参数中分配了不正确的值。

标签： javaarraysrecursionbinary-search-treenodes