java - 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;
    }

我试图了解 Entry 父级和 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 方法使用 Tree -String-tree 作为参数，我不知道它是什么。在 Tree 类中，我尝试了 Entry 和 ，并且再次没有区别。代码无法正常工作，我完全困惑了。

Answer 1

从根本上来说，Java 中的泛型是一种在对象中命名特定类的方法，并且在声明该对象之前知道是哪个类。这很有用，因为它允许编译器强制对该类的引用之间的一致性。

更具体地说，在你的类(class)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 。这意味着您将不得不开始担心类型转换，而正确执行此操作可能会很乏味。

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