Реализация дерева с использованием общих типов в Java

Question

Во-первых, я искал об использовании общих типов в java, однако ответы, которые я нашел, были слишком простыми или сложными. Итак, вот мой точный вопрос.

У меня есть три класса соответственно PerfectTreeControl, Tree и Entry.

Дерево имеет

public class Tree<K> { 
    public Entry <K> root; 

запись имеет

public class Entry<K> { 
    public K element; 
    public Entry<K> parent, left_child, right_child; 


    public Entry(K element) { 
     this.element = element; 
    } 
    public Entry(K element, Entry<K> left, Entry<K> right) { 
     left_child = left; 
     right_child = right; 
     this.element = element; 
    } 

Я пытаюсь понять, в чем разница между родительской записи и запись <K> родителя? Я знаю, что K element может использоваться как целое, String или что-то, что я хочу, но делает то же самое для объекта? Я попытался использовать переменные Entry без параметра, и он только сказал, что Entry является сырым типом и должен быть параметризован, и он все еще работает без ошибок.

Мой второй вопрос о проверке дерева, будь то совершенный или нет. Вот некоторые коды я пробовал до сих пор:

public class PerfectTreeControl { 

    public static boolean isPerfect(Tree<String> tree) { 
     Tree t1 = new Tree(); 
     if(t1.isFull(tree.root)) { 
      int depth = t1.height(tree.root); 
      return t1.everyLeafHasSameDepth(tree.root, depth); 
     } 
     else 
      return false; 
    } 
    } 





public class Tree<K> { 
    public Entry <K> root; 

    public boolean isLeaf(Entry e) { 
     return e.left_child == null && 
       e.right_child == null; 
    } 

    public int height(Entry e) { 
     if(e == null || 
       e.left_child == null && 
       e.right_child == null) 
      return 0; 
     int left = height(e.left_child); 
     int right = height(e.right_child); 

     return 1 + Math.max(left, right); 
    } 

    public boolean isFull(Entry base) { 
     if(isLeaf(base)) 
      return true; 
     else 
      if(base.left_child != null && base.right_child != null) { 
       return isFull(base.left_child) && 
         isFull(base.right_child); 
      } else { 
       return false; 
      } 
    } 


    public int depth(Entry e) { 
     if(e == root) { 
      return 0; 
     } else { 
      return 1 + depth(e.parent); 
     } 
    } 

    public boolean everyLeafHasSameDepth(Entry base, int depth) { 
     if(base == null) 
      return false; 
     else if(isLeaf(base)) 
      return depth(base) == depth; 
     else { 
      return 
        everyLeafHasSameDepth(base.left_child, depth) && 
        everyLeafHasSameDepth(base.right_child, depth); 
     } 
    } 

• класс входа (я написал его в верхней части страницы) Как вы можете видеть, метод isPerfect в классе PerfectTreeControl использует дерево -String- дерево как параметр, и я понятия не имею, что это. В классе Tree я попробовал Entry с и, и опять же никакой разницы. Код не будет работать должным образом, и я полностью смущен.

Answer 1

Дженерики на Java, в принципе, способ назвать конкретный класс внутри объекта, зная, какой класс пока объявлен этот объект. Это полезно, потому что это позволяет компилятору обеспечить согласованность ссылок на этот класс.

Более конкретно, в классе Entry<K>, в любое время вы ссылаетесь K, компилятор Java будет обеспечивать, чтобы все ссылки типа K, по сути, рассматривается как тип K. Например, если вы создаете объект типа Entry<String>, член element этого объекта должен иметь тип String, член parent должен иметь тип Entry<String> и т. Д. Если бы у вас был метод, который возвращал K, компилятор распознал бы, что возвращаемое значение равно String. Если компилятор видит несоответствие здесь - скажем, если вы попытаетесь установить значение member на Integer - он будет жаловаться.

Имейте в виду, что качества, которые я описываю в приведенном выше примере, относятся к конкретному объекту Entry<String>, который вы определили. Если вы определяете Entry<Integer>, не обновляя свой класс Entry, согласованность выполняется в этом новом объекте, за исключением этого времени с K, что означает Integer.

Если вы создаете объект без указания аргумента типа для K, вы используете «сырой тип». Это предотвращает выполнение компилятором правил согласованности и предполагает, что тип K равен Object. Это означает, что вам придется начинать беспокоиться о кастинге, что может оказаться утомительным для правильной работы.

Чтобы проверить, заполнено ли дерево (или «совершенным»), наиболее интуитивный подход является рекурсивным. Рекурсивное правило, используемое в этом сценарии, - «если дети дерева идеальны и имеют одинаковую глубину, дерево идеально».