在Java中使用泛型类型的树实现

首先我已经搜索了关于java中泛型类型的用法，但是我发现的答案太简单或复杂了。所以这是我确切的问题。在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; 
    }

我想了解什么是进入母体和Entry <ķ>父母之间有什么区别？我知道K element可以用作整数，字符串或任何我想要的，但是对于对象来说是否也是这样？我试图使用不带参数的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); 
     } 
    }

入门级（我写在页面的顶部）如你所见，在PerfectTreeControl类isPerfect方法使用树-String-树作为参数，我不知道它是什么。在Tree类中，我尝试了Entry，并且再次没有区别。代码将无法正常工作，我完全困惑。

来源

2012-06-30 nihirus

你不应该担心原始类型。它们只是为了向后兼容，并且不应该使用通用类型的原始版本。（即在你的代码中，无处不在使用'Entry '。） – millimoose

定义通用对象有什么意义？更清楚的是，将对象定义为泛型而不是普通对象有什么优势？对象已经可以将你在类中定义的任何东西当作一个变量，字符串，int等等。我错过了什么？ – nihirus

@nihirus：如果您在任何地方使用普通对象，则每次需要将值转换为所需类型时，都需要执行某些操作。 – Tudor

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。这意味着你将不得不开始担心投射，这可能很难做到。

要检查树是否已满（或“完美”），最直观的方法是递归。在这种情况下使用的递归规则是“如果一棵树的孩子是完美的并且具有相同的深度，那么树就是完美的。”

来源

2012-06-30 22:43:21 cheeken

在Java中使用泛型类型的树实现

回答

相关问题