Добавление объектов в бинарное дерево поиска

Я совершенно новичок в BST и в том, как они работают, если это совершенно неправильно, было бы признательно, если бы я мог получить ссылку на справочный сайт или что-то в этом роде. прямо сейчас я пишу программу для добавления значений из ArrayList из Strings в BST, и я получаю такие ошибки, как метод compareTo(Node) не определен для типа ArrayList<String>. Я думал, что при наличии extends Comparable будет учитываться сравнение значений ArrayList, но я не использую E. Также мне пришлось добавить приведение к s, чтобы установить его как корень, но мне кажется, что есть более простой способ. Я не знаю, смогу ли я добавить значения ArrayList так, как я это делаю, это просто то, как это выглядит в книге, которую я использую для справки. Это мой код, любая помощь будет оценена по достоинству, я уже пробовал искать вещи в Java API, и это не помогло:

public class BinarySearchTree<E extends Comparable<? super E>>

{

    public void add(ArrayList<String> s, Node n) {


            if (n == null)
                 n = (Node) s;
            else if (s.compareTo(n) < 0)
                 add(s, n.leftChild);
            else
                 add(s, n.rightChild);


    }
}

java binary-search-tree
person Ryan Sayles    schedule 18.03.2012    source источник
comment
что именно делает add()? похоже, вы пытаетесь добавить ArrayLists в BST, а не добавлять значения FROM и ArrayList в BST   -  person mfrankli    schedule 18.03.2012

Ответы (3)


arrow_upward
1
arrow_downward

Думаю, эта ссылка будет вам полезна: Двоичные деревья поиска — Стэнфордская библиотека

person Community    schedule 18.03.2012
comment
Это одна из лучших ссылок, которые я видел. - person SeattleOrBayArea; 19.03.2012

arrow_upward
1
arrow_downward

Прежде всего, класс Node должен расширять Comparable и переопределять в нем метод compareTo. Класс ArrayList не расширяет Comparable, поэтому следующее не будет работать.

s.compareTo(n) ‹ 0

s является ссылкой на ArrayList. Кроме того, вы пытаетесь сравнить ссылку ArrayList со ссылкой Node, что совершенно неверно. Вам нужно сравнить два значения Node.

person Noroi    schedule 18.03.2012

arrow_upward
0
arrow_downward

Похоже, вы пытаетесь добавить весь ArrayList как единый узел вашего BST. Я предполагаю, что вы должны построить BST из элементов ArrayList. Для этого я бы предложил определить две функции:

public Node add(ArrayList<String> s, Node root) {
    for (String elt : s) {
        root = add(elt, root);
    }
}

public Node add(String elt, Node root) {
    if (root == null) {
        root = // new Node with data set to elt
    } else if (elt.compareTo(n.data()) < 0) {
        root.left = add(elt, root.left);
    } else if (elt.compareTo(n.data()) > 0) {
        root.right = add(elt, root.right);
    } else {
        // duplicate element being inserted -- error?
    }
    return root;
}
person Ted Hopp    schedule 18.03.2012
comment
Да, мне нужно добавить каждый элемент из ArrayList в BST. Спасибо вам за помощь! Однако один вопрос: что вы подразумеваете под n.data(). Должен ли я установить n для каждого значения в ArrayList? - person Ryan Sayles; 18.03.2012