对于类分配,我需要在提供的binarysearchtree类中添加一种方法,该类将通过存储数组中的dropect in andray和使用这些值来平衡二进制搜索树构造一棵新树。但是,当我尝试运行该方法时,我会得到NullPoInterException。如何更改我的方法以正确平衡我的二进制搜索树?
我在下面包含了我的代码(试图将其简化为问题所需的内容);底部的两种方法是我试图用于平衡的方法。
package ch08;
import ch05.queues.*;
import java.util.ArrayList;
public class BinarySearchTree<T extends Comparable<T>> implements BSTInterface<T>{
protected BSTNode<T> root; // reference to the root of this BST
protected LinkedUnbndQueue<T> inOrderQueue;
protected ArrayList<T> balanceArray;
public BinarySearchTree(){
root = null;
}
public int reset(int orderType){
int numNodes = size();
if (orderType == INORDER){
inOrderQueue = new LinkedUnbndQueue<T>();
inOrder(root);
}
return numNodes;
}
public T getNext (int orderType){
if (orderType == INORDER)
return inOrderQueue.dequeue();
}
public void balanceTree() {
int count = reset(INORDER);
for(int i = 0; i < count; i++) {
balanceArray.add(getNext(INORDER));
}
BinarySearchTree<T> tree = new BinarySearchTree<T>();
tree.insertTree(0, count - 1);
this.root = tree.root;
}
public void insertTree(int low, int high){
if(low == high) {
add(balanceArray.get(low));
}
else if((low + 1) == high) {
add(balanceArray.get(low));
add(balanceArray.get(high));
}
else {
int mid = (low + high) / 2;
add(balanceArray.get(mid));
insertTree(low, mid - 1);
insertTree(mid + 1, high);
}
}
}
我猜nullpoInterException来自以下事实:您永远不会初始化balanceArray
。
您不应将inOrderQueue
和balanceArray
声明为字段(IMHO),因为它们仅与一个操作有关。我会在那里使用参数。
我看不到类BSTNode
,所以我认为这是这样的:
public class BSTNode<T extends Comparable<T>> {
T value;
BSTNode<T> left;
BSTNode<T> right;
public BSTNode(T value, BSTNode<T> left, BSTNode<T> right) {
this.value = value;
this.left = left;
this.right = right;
}
}
这是我要进行平衡的方式:
public class BinarySearchTree<T extends Comparable<T>> {
protected BSTNode<T> root; // reference to the root of this BST
public BinarySearchTree() {
root = null;
}
// creates a tree from a sorted list
private BinarySearchTree(List<T> list) {
root = buildTree(list, 0, list.size());
}
public BinarySearchTree<T> balancedTree() {
List<T> list = new ArrayList<>();
inOrder(root, list);
return new BinarySearchTree(list);
}
private void inOrder(BSTNode<T> node, List<T> list) {
if (node != null) {
inOrder(node.left, list);
list.add(node.value);
inOrder(node.right, list);
}
}
private BSTNode<T> buildTree(List<T> list, int i, int size) {
if (size == 0) {
return null;
} else {
int half = size/2;
int mid = i+half;
return new BSTNode<T>(list.get(mid),
buildTree(list, i, half),
buildTree(list, mid+1, size-half-1));
}
}
...
}