бинарное дерево поиска

Question

Привет У меня есть список массивов, в котором есть некоторые цифры, такие как {23,16,45,26,2,5,9} и я хочу создать двоичное дерево поиска с этим списком массивов, который равен "array", а его элементами являются объекты, имеющие 2 поля, 1)digit2)level, но здесь я просто хочу использовать его digit поле. это DoublyLinkedList. это мой код, но он выдаст исключение. Пожалуйста, помогите мне, спасибо.

    private void method(ArrayList<Element> array) {
    DNode header = new DNode(null, null, null);
    DNode trailer = new DNode(null, header, null);
    header.next = trailer;
    DNode node = new DNode(array.get(0), header, trailer);
    dList.addLast(node);
    header = node
    for(int i = 1;i<array.size();i++){
    makeBST(node, array.get(i));
    }
}

private void makeBST(DNode node, Element e) {

    if (!e.equals(node.getElement())) {
        DNode nodeOne = new DNode(e, null, null);
        if (node.getElement().getDigit() > e.getDigit()) {
            node.prev = nodeOne;
        } else if (node.getElement().getDigit() < e.getDigit()) {
            node.next = node;
        }
    }
    if (e.getDigit() < node.getElement().getDigit()) {
        makeBST(node.prev, e);
    }
    makeBST(node.next, e);
}

Исключение:

Exception in thread "main" java.lang.StackOverflowError
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:43)
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)

первая строка исключения для этой строки кода:

if (!e.equals(node.getElement())) 

Answer 1

вашему рекурсивному методу "private void makeBST (DNode node, Element e)" требуется некоторый тип конечного условия (путь потока, который не позволит ему вызываться самому);как таковой, он продолжает вызывать себя рекурсивно, что и вызывает ошибку переполнения стека.

Answer 2

Ваш код в основном:

private void makeBST(DNode node, Element e) {
    // ... (the rest of your code)
    makeBST(node.next, e);
}

Это почти эквивалентно:

private void makeBST(DNode node, Element e) {
    while(true) {
        // ... (the rest of your code)
        node = node.next;
    }
}

Вы только что сделали бесконечный цикл (но не с while, а с рекурсией).Поскольку размер стека очень ограничен, после некоторых итераций вы получаете StackOverflowError.

Но в любом случае, если это всего лишь образовательный эксперимент, то все в порядке.Если вам просто нужен работающий BST, используйте java.util.TreeSet или java.util.TreeMap.

Answer 3

Я вижу, что вы пытаетесь, но вы далеки от решения.

Вы используете рекурсию, поэтому вам нужен стоп-кейс ... которого у вас нет.

Вы, вероятно, также должны иметь if ... else if ... вместо того, что вы получили (если ... if ...)

Эта строка if (!e.equals(node.getElement())) { тоже не имеет смысла ...

Ознакомьтесь со статьями в Википедии о бинарных деревьях и бинарных деревьях поиска ... возможно, это поможет.

Answer 4

У вас есть StackOverflowError, которая указывает на бесконечную (ну, по крайней мере, потенциально) ошибку рекурсии.

p.s. почему бы просто не использовать TreeMap<K,V>, где K - индекс ваших данных, а V - значение данных?