сравнимо используется как структура в двоичном дереве

У меня есть двоичное дерево на Java, которое прекрасно работает. Но я хочу улучшить содержимое данных в узле. В настоящее время я могу добавить к нему значения, например:

for( int i = 1; i <=10; i++ )
    t.insert( new Integer( i ) );

Что добавит такой элемент:

public void insert( Comparable item ) {
    current = parent = grand = header;
    nullNode.element = item;
    ...
}

Вот формат дерева:

private static class RedBlackNode {
    // Constructors
    RedBlackNode( Comparable theElement ) {
        this( theElement, null, null );
    }

    RedBlackNode( Comparable theElement, RedBlackNode lt, RedBlackNode rt ) {
        element  = theElement;
        left     = lt;
        right    = rt;
        color    = RedBlackTree.BLACK;
    }

    Comparable   element;    // The data in the node
    RedBlackNode left;       // Left child
    RedBlackNode right;      // Right child
    int          color;      // Color
}

Для показа дерева мне это нравится:

private void printTree( RedBlackNode t ) {
    if( t != nullNode ) {
        printTree( t.left );
        System.out.println(t.element);
        printTree( t.right );
    }
}

При программировании на многих других языках элемент будет объявлен как структура для этот образец кода в Java объявлен как Comparable, и в настоящее время принимает только один элемент как целое число. Мой вопрос в том, как я могу использовать его аналогично структуре, чтобы иметь возможность также манипулировать ею, например, в этом псевдокоде:

System.out.println(t.element.valueInt);
System.out.println(t.element.firstNameString);
System.out.println(t.element.lastNameString);

Я пробовал разные комбинации синтаксиса на основе некоторых предыдущих сообщений, но пока ни одна из них не сработала.

Для текущей версии кода с добавленными комментариями проверьте Gist.

Мы глубоко признательны за все предложения.


java data-structures comparable binary-tree
person Emma Yazzie    schedule 18.05.2014    source источник
comment
Я думаю, вам понадобится реализовать интерфейс Comparable и переопределить метод compareTo ().   -  person gyanu    schedule 18.05.2014

Ответы (1)


arrow_upward
5
arrow_downward

Comparable - это интерфейс. Это может реализовать любой класс. Поскольку единственное, что дереву нужно знать о своих узлах, - это то, как сравнивать, и поскольку Comparable предоставляет именно такие знания, для дерева достаточно использования Comparable.

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

public class RedBlackTree <T extends Comparable<? super T>> {
    private static class RedBlackNode {
        ...
       T element;
    }
}

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

При создании RedBlackTree вам необходимо указать тип узла, например:

RedBlackTree<MyClass> tree = new RedBlackTree<MyClass>();

Конечно, MyClass должен реализовывать Comparable. Общий эффект от изменения заключается в том, что когда ваш код получает элемент из дерева, он становится строго типизированным, что позволяет вам получить доступ к его методам и полям без приведения.

person Sergey Kalinichenko    schedule 18.05.2014
comment
Не могли бы вы расширить этот синтаксис: <T extends Comparable<? super T>>? Я новичок в дженериках И Comparable интерфейсе, так что комбинация просто взорвала меня .... - person rocksNwaves; 10.05.2021