为二叉树（通用）实现 compareTo (Comparable<T>)

Question

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

它是这样工作的：

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

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

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

我目前在我的程序中使用的属性是：节点（第一个，上一个，左，右），键，值输入键值节点 myNodes（上一个，...）

类定义：

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

Answer 1

二叉树的要求之一是节点值必须排序，因此您应该为 TreeNode <T extends Comparable<T>> 创建通用类型，而不仅仅是 <T>。然后你的 compareTo 方法可以委托给节点的 compareTo.

Answer 2

现在您的代码是：

有一棵类型为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
     ...
}

简短摘要：您有一个类型为 T 的 Tree，该类型可以与类型为 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，可以相互比较（即TreeNode implements Comparable<TreeNode>）来建一个Tree。您使用 int-comparisons 实现 compareTo。你现在有一个非通用的 Tree.

为了能够使 Tree 通用，您需要通用 TreeNode。因此，您使 TreeNode 通用，并将以前固定的字段 int key; 替换为 F f;。现在你不能再实现基于 int 比较的比较，所以 TreeNode 必须以某种方式与 TreeNode 的其他实例进行比较。如果我们可以将其委托给 F 的比较函数，那就太好了。为确保有效，类型必须为 TreeNode<F extends Comparable<F>>。当然我们仍然需要可比较的 TreeNodes 的基本假设成立所以你最终得到

class TreeNode<F extends<Comparable<F>> implements Comparable<TreeNode<F>>。

您现在有一个通用的 TreeNode<F>，可以与 TreeNode<F> 的其他实例进行比较。

现在你可以从这些节点构建一个通用的 Tree<T>，只要 T 是可以与其他 T 进行比较的东西，所以 Tree<T extends Comparable<T>>。由于您不想隐藏内部 class 的类型，因此当您在树的函数中使用它们时，您会区分 T 和 F 并实例化 TreeNode<T>s。 F的存在从外面是看不出来的

为二叉树（通用）实现 compareTo (Comparable<T>)

implementing compareTo (Comparable<T>) for a Binary Tree(Generic)

java

generics

compareto

nodes