ArrayListを使用したバイナリ検索ツリーの均衡化

Question

クラスの割り当てのために、バイナリ検索ツリーのバリューを配列順に格納し、それらの値を使用してメソッドをBinarySearchTreeクラスに追加する必要があります新しいツリーを構築する。しかし、メソッドを実行しようとするとnullPointerExceptionが発生します。バイナリ検索ツリーの適切なバランスを取る方法を変更するにはどうすればよいですか？

私は自分のコードを以下に挙げました（問題を解決するために必要な部分だけを切り取ろうとしています）。下の2つのメソッドは、バランスを取るために使用しようとしているメソッドです。

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は、1つの操作にのみ関連するため、フィールド（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)); 
     } 
    } 

    ... 
}