java - 递归平衡二叉搜索树

Question

我有一个 BinarySearchTree，其中包含我创建的类 Instance bankaccount 的对象，所以基本上它只是一个 binarysearchtree，我写了一个方法来获取树并平衡它，对于一些它在平衡之前准确打印出树的原因:

现在，首先我有 createList 方法，它接受一个列表和一个 tree(one node) 并创建一个 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}(这就是这个比较器的工作原理)然后我希望这棵树是平衡的，但它保持不变。知道代码有什么问题吗？

编辑:这是我到目前为止所做的更改，buildBalancedTree 给我一个 NullpointerException

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);

您正在创建一个新的 BankAccountsBinarySearchTree 对象，然后将该对象的 root(将为 null)传递给 createList 方法。

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