递归地平衡二进制搜索树

Question

我有一个BinarySearchTree，里面有Instance bankaccount的对象，这是我创建的一个类，所以基本上它只是一个二进制树，我写了一个方法来获取树并对其进行平衡，出于某种原因，它精确地打印出平衡前的树：

现在，首先我有了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 + "nn");

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

edit：这是我到目前为止所做的更改，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方法。