ArrayList를 사용하여 이진 검색 트리 균형 조정

Question

클래스 할당을 위해 배열에 값을 순서대로 저장하고이 값을 사용하여 이진 검색 트리의 균형을 유지할 수있는 제공된 BinarySearchTree 클래스에 메서드를 추가해야합니다 새로운 나무를 만드십시오. 그러나 메서드를 실행하려고하면 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); 
    } 
} 
} 

Answer 1

NullPointerException은 결코 balanceArray을 초기화하지 않는다는 사실에서 비롯된 것 같습니다.

inOrderQueue 및 balanceArray은 한 작업과 관련되어 있으므로 필드 (IMHO)로 선언하면 안됩니다. 나는 그곳에서 논증을 사용할 것이다.

I 클래스 BSTNode이 표시되지 않는, 그래서는이 같은 가정 :

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

    ... 
} 

:

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

여기에 내가 균형을 할 것입니다 방법