递归平衡二叉查找树

Question

我有一个＜code＞BinarySearchTree＜/code＞，里面有Instance bankaccount的对象，这是我创建的一个类，所以基本上它只是一个二进制搜索树，我编写了一个方法，它将获取树并对其进行平衡，因为某些原因，它在平衡之前准确地打印出树：

现在，首先我有createList方法，它接受一个列表和一个树（一个节点）并通过按顺序检查树数据来创建树数据的arrayList（DynamicArray），因此它是一个排序数组。然后使用另一种方法以平衡的方式创建树，方法是使数组的中间元素根，然后左中间是左子树的根，右中间是右子树的根

import java.util.Comparator;
import java.util.Iterator;

public class BankAccountsBinarySearchTree extends BinarySearchTree<BankAccount>{

public BankAccountsBinarySearchTree(Comparator<BankAccount> myComparator) {
    super(myComparator);
}

//Complete the following method
public void balance(){


    // create a sorted list and a binary tree
    List<BankAccount> list = new DynamicArray<BankAccount>();
    BankAccountsBinarySearchTree tree = new BankAccountsBinarySearchTree(comparator);
    createList(tree.root, (DynamicArray<BankAccount>) list);

    // build balanced tree recursively
    buildBalancedTree(tree, list, 0, list.size()-1);
}

//Complete the following method
private void buildBalancedTree(BankAccountsBinarySearchTree tree, List<BankAccount> list, int low, int high){

        // base case
        if (low > high)
            return ;

        // Get the middle element and make it root
        int mid = (low + high) / 2;
        tree.root.data = list.get(mid);

        // create left and right subtrees and go on to balance each
    BankAccountsBinarySearchTree leftTree = new BankAccountsBinarySearchTree(comparator);
    BankAccountsBinarySearchTree rightTree = new BankAccountsBinarySearchTree(comparator);

    buildBalancedTree(leftTree, list , low, mid - 1);
    buildBalancedTree(rightTree, list, mid + 1, high);

    root.left = leftTree.root;
    root.right = rightTree.root;


}

// method to create a list with all objects of BankAccountBinarySearchTree in a sorted array because it's in Order.
private void createList(BinaryNode<BankAccount> root, DynamicArray<BankAccount> list)
{
    // Base case
    if (root == null)
        return;

    // Store nodes in Inorder (which is sorted
    // order for BST)
    createList(root.left, list);
    list.add(root.data);
    createList((BinarySearchNode) root.right, list);
}

public Iterator<BankAccount> iterator(){
    return new FilteredBankAccountsIterator(this);
}

}

出于某种原因，如果我这样做：

Comparator<BankAccount> c = new AccountComparatorByNumber();

   BankAccountsBinarySearchTree t3 = new BankAccountsBinarySearchTree(c);
    t3.insert(new BankAccount("a", 2, 0));
    t3.insert(new BankAccount("a", 1, 0));
    t3.insert(new BankAccount("a", 3, 0));
    t3.insert(new BankAccount("a", 4, 0));
    t3.insert(new BankAccount("a", 5, 0));
    t3.insert(new BankAccount("a", 6, 0));
    t3.insert(new BankAccount("a", 7, 0));
    t3.insert(new BankAccount("a", 8, 0));
    System.out.println("----------unbalanced t3:----------\n" + t3);
    t3.balance();
    System.out.println("\n----------balanced t3:----------\n" + t3 + "\n\n");

首先，它将使用一个比较器按数字对数组进行排序，因此数组应该是{1，2，3，4，5，6，7，8}(这是比较器的工作方式)，然后我希望树是平衡的，但它保持不变。你知道代码有什么问题吗？

编辑：这是我到目前为止所做的更改，并且构建平衡树给了我一个空指针异常

public void balance(){


        // create a sorted list and a binary tree
        List<BankAccount> list = new DynamicArray<BankAccount>();

        BankAccountsBinarySearchTree tree = new BankAccountsBinarySearchTree(comparator);

        tree.root = this.root;

        createList(tree.root, (DynamicArray<BankAccount>) list);


        // build balanced tree recursively
        buildBalancedTree(tree, list, 0, list.size()-1);

    }

Answer 1

BankAccountsBinarySearchTree tree = new BankAccountsBinarySearchTree(comparator);
createList(tree.root, (DynamicArray<BankAccount>) list);

您正在创建一个新的BankAcCountsBinary SearchTree对象，然后将该对象的root（将为空）传递给createList方法。

您需要将当前对象的根（未显示在代码中）传递给 createList 方法。