java - 为二叉树(通用)实现 compareTo (Comparable)

Question

我正在生成一个带有键值节点的二叉树。

它是这样工作的:

顺序如下:如果你实现一个新节点，你给一个键和一个值(不重要)，它将检查是否已经有一个节点，如果没有，它将创建它作为第一个节点。现在它检查 key 是否小于第一个节点的 key ，如果是这样，如果还没有，它将把它作为左节点，如果有，它将迭代到那个并再次检查它。对于较大的键/右节点也是如此。如果键等于当前节点的键，它将覆盖该节点。

如果我使用像 int 这样的东西，这个方法是有效的。现在我想把它作为一个通用的，所以我想从 Comparable 接口(interface)添加 compareTo，因为我可以检查键是否小于、等于或大于当前节点的键。我知道我必须使用键，但我不能自己编写任何 compareTo 方法。我不确定如何让它发挥作用。

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

我目前在我的程序中使用的属性是:节点(第一个，上一个，左，右)，键，值输入键值节点 myNodes(previous,...)

类定义:

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 .你用 int 实现 compareTo -比较。你现在有一个非通用的 Tree .

能够制作Tree通用的，你需要一个通用的 TreeNode .所以你做TreeNode通用并替换以前固定的字段 int key;通过 F f; .现在你不能再实现基于 int 比较的比较，所以 TreeNode必须与 TreeNode 的其他实例相媲美不知何故。如果我们可以将其委托(delegate)给 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>当您在树的函数中使用它们时。 F的存在从外面是看不到的。