我有一个BinarySearchTree，其中包含的是我创建的bankaccount类的实例对象。基本上它只是一个二叉搜索树，我编写了一种方法来对其进行平衡，不知何故该方法输出的正是平衡前的树。
现在，首先我有一个createList方法，它接收一个列表和一个树（一个节点），并通过中序遍历进行遍历，从而创建了一个排序数组ArrayList（DynamicArray）。 然后使用另一种方法以平衡的方式创建树，方法是将数组的中间元素作为根，将左侧中间元素作为左子树的根，将右侧中间元素作为右子树的根。
现在，首先我有一个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}（这就是比较器的工作原理），然后我希望树能够平衡，但它仍然保持不变。有什么想法吗？
编辑：我已经做出了一些更改，而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);
}
createList后打印List<BankAccount> list以验证您是否获得了排序数据。 - Thiyagu