3

我有一个BinarySearchTreeInstance 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 + "\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);

    }
4

1 回答 1

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

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

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

于 2019-01-03T09:08:51.193 回答