реализация compareTo (сравнивается <T>) для двоичного дерева (общий)

Question

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

Это работает так:

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

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

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

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

classdefinitions:

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

Answer 1

Прямо сейчас, что говорит ваш код:

Существует дерево типа 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>. Сравнение TreeNode<T> с номером TreeNode<T> может быть выполнено путем сравнения элементов, хранящихся внутри TreeNode. Есть причина, почему я отклонился от вашего оригинального дизайна в последней точке (по крайней мере, по имени). Если вы думаете о T как сохраненный элемент, проще подумать о том, как расширить дерево, чтобы поддерживать элемент типа TreeItem, который позволяет вам создавать ассоциативную структуру данных поверх дерева.

Редактировать (в прямой ответ, так как OP запросил разъяснения): Код

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

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 не видно снаружи.

Answer 2

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