Балансировка двоичного дерева поиска с использованием ArrayList

Для назначения класса мне необходимо добавить метод к предоставленному классу 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);
    }
 }
}

java arraylist tree binary-search-tree tree-balancing
person shamstu    schedule 14.12.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я предполагаю, что NullPointerException возникает из-за того, что вы никогда не инициализируете balanceArray.

Вы не должны объявлять inOrderQueue и balanceArray как поля (ИМХО), потому что они относятся только к одной операции. Я бы использовал аргументы там.

Я не вижу класс 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));
        }
    }

    ...
}
person Maurice Perry    schedule 14.12.2017