реализация compareTo (Comparable) для бинарного дерева (Generic)

Я создаю двоичное дерево с узлами ключ - значение.

Это работает следующим образом: пример двоичного дерева(эти числа являются ключами)

Порядок следующий: Если вы реализуете новый узел, вы даете ключ и значение (не важно), он будет проверять, есть ли уже узел, если нет, он создаст его как первый узел. теперь он проверяет, меньше ли ключ, чем ключ первого узла, если да, то он будет помещать его в качестве левого узла, если его еще нет, если он есть, то он повторит это и проверит его снова. То же самое для больший ключ / правый узел. Если ключ равен ключу текущего узла, он будет переопределять узел.

Этот метод работает, если я использую что-то вроде int. Теперь я хочу сделать это как универсальный, поэтому я хочу добавить compareTo из сопоставимого интерфейса, потому что я мог бы проверить, является ли ключ меньше, равен или больше, чем ключ текущего узла. Я знаю, что мне нужно использовать ключи, но я не могу сам кодировать какой-либо метод compareTo. Я не знаю, как заставить его работать.

@Override
public int compareTo(TreeNode<Type> node) {
    //method
}

Атрибуты В настоящее время я использую в своей программе: Узлы(первый,предыдущий,левый,правый), ключ, значение Ключ типа, значение Узел myNodes (предыдущий,...)

Определения классов: 

public class Tree<Type> {
    ...
    public class TreeNode<Type extends Comparable<Type>>{
        ...
    }
    public int compareTo(TreeNode<Type> Node){
        //method
    }
}
2 2
generics compareto

2 ответа:

Прямо сейчас ваш код говорит следующее:

Существует дерево типа type, которое можно сравнить с другими деревьями типа type.

То, что вы, по-видимому, хотите сказать:

Существует дерево, построенное из элементов типа type, которые сопоставимы со своим собственным типом.

В этом случае вы должны определить дерево следующим образом: 

public class Tree<T extends Comparable<T>> {
     private class TreeNode<F extends<Comparable<F>> implements Comparable<TreeNode<F>>{
           private F f;
           ...
           public F getF(){return this.f;}
           @Override
           public int compareTo(TreeNode<F> node){
               return this.f.compareTo(node.getF());
           }
     }
     //Use TreeNode<T> here
     ...
}

Краткий итог: у вас есть Tree типа T, который является типом, который может быть по сравнению с другими объектами типа T. Элементы в дереве представлены TreeNode<T>, которые можно сравнить с другими TreeNode<T>. Сравнение a TreeNode<T> С a TreeNode<T> может быть выполнено путем сравнения элементов, хранящихся внутри TreeNode. Есть причина, по которой я отклонился от вашего первоначального замысла в последнем пункте (по крайней мере, по названию). Если вы думаете о T как о сохраненном элементе, то проще подумать о том, как расширить дерево для поддержки элемента типа TreeItem, что позволяет построить ассоциативную структуру данных поверх дерево.

Edit (в прямом ответе, поскольку ОП запросил разъяснение):

Код OP был примерно таким в момент ответа: 

public class Tree<T> implements Comparable<Tree<T>>{
    ...
    TreeNode<???>{...}

}

Подумайте о том, что TreeNode имеет фиксированный член int key; на секунду. Вы хотите построить Tree: поэтому вам нужно TreeNode s, которые можно сравнить друг с другом (т. е. TreeNode implements Comparable<TreeNode>), чтобы построить Tree. Вы реализуете compareTo с int - сравнениями. Теперь у вас есть неродовой Tree.

Чтобы иметь возможность сделать Tree generic, вам нужен generic TreeNode. Таким образом, вы делаете TreeNode универсальным и заменяете ранее фиксированное поле int key; на F f;. Теперь вы больше не можете реализовать сравнение, основанное на int-сравнениях, поэтому TreeNode должен быть каким-то образом сопоставим с другими экземплярами TreeNode. Было бы здорово, если бы мы могли делегировать это функции сравнения F. Чтобы убедиться, что это работает, тип должен быть TreeNode<F extends Comparable<F>>. Конечно, нам все еще нужна основная гипотеза сопоставимых TreeNodes, чтобы вы в конечном итоге получили

class TreeNode<F extends<Comparable<F>> implements Comparable<TreeNode<F>>.

Теперь у вас есть общий TreeNode<F>, который можно сравнить с другими экземплярами TreeNode<F>.

Теперь вы можете построить общий Tree<T> из этих узлов, пока T является чем-то, что можно сравнить с другими T s, поэтому Tree<T extends Comparable<T>>. Поскольку вы не хотите затенять тип внутреннего класса, вы различаете T и F и создаете экземпляр TreeNode<T>s, когда используете их внутри функций дерева. Существование F не видно извне.

4

Одним из требований к бинарному дереву является то, что значения узлов должны быть упорядочены, поэтому вы должны сделать свой универсальный тип для TreeNode <T extends Comparable<T>> вместо просто <T>. Тогда ваш compareTo метод может просто делегировать узлу compareTo.

1