为二叉树（通用）实现compareTo（可比较的<T>）

我正在用键值节点生成二叉树。为二叉树（通用）实现compareTo（可比较的<T>）

它的工作原理是这样的： example Binary Tree(those numbers are the keys)

的排序如下：如果你实现你给一个键和一个值（并不重要），它会检查是否有一个节点已如果没有一个新的节点将它创建为第一个节点。现在它检查密钥是否小于第一个节点的密钥，如果是的话，它会将它作为左节点（如果还没有的话），如果有一个它将迭代并重新检查它。较大的键/右节点相同。如果密钥等于当前节点的密钥，它将覆盖该节点。

如果我使用类似int的东西，此方法正在工作。现在我想做它作为一个通用的，所以我想从Comparable接口添加compareTo，因为我可以检查密钥是否小于，等于或大于当前节点的密钥。我知道我必须使用这些键，但我无法自己编写任何compareTo方法。我不知道如何让它工作。目前我使用我的程序

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

属性是：节点（第一，以前，左，右），键，值类型键，值节点myNodes（上，...）

classdefinitions：

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

来源

2015-01-09 NhatNienne

基本上，您不必实现compareTo，因为已经为Java中的数字和字符串类型实现了Comparable接口，并且您可以为任何其他**特定的**自定义类编写任何其他实现。在树中，你只需要使用它。但是，由于我无法理解你问题的最后部分，所以试图更清楚。 – 2015-01-09 23:10:45

所以首先我不知道哪些类型会依赖于我的老师。所以我必须得到一个compareTo的通用版本，它比较两个节点的通用密钥并检查哪一个是“较小”或“较大” ”。最后一部分只是说明每个属性是如何定义的 – NhatNienne 2015-01-09 23:13:21

现在你的代码说的话是：

有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型，这是可以比较T类型的其他对象的类型的Tree。树中的元素由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。您执行compareTo与int-比较。您现在有一个非通用的Tree。

为了能够使Tree通用，您需要一个通用的TreeNode。因此，您制作TreeNode通用并将F f;替换原来的固定字段int key;。现在，您不能再基于int比较来实施比较，因此TreeNode必须以某种方式与TreeNode的其他实例相比。如果我们可以将它委托给F的比较函数，那将很酷。为了确保工作，类型必须是TreeNode<F extends Comparable<F>>。当然，我们仍然需要可比较的TreeNode的基本假设，以便最终得到

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的存在。

来源

2015-01-09 23:28:15 midor

不！ @NhatNienne请勿在人们开始回答后更新问题。这意味着现有的答案是没有道理的;并使任何人都无法提供后续答案，这可能会或可能不会比这个更好。堆栈溢出旨在成为对未来用户有用的问题和答案的存储库。如果你改变了这个问题，它会使问题与答案不符，并且使问题和整套答案对除你以外的任何人都完全无用。请取消你的编辑！ – 2015-01-09 23:56:35

编辑我的问题回来（如果我没记错的话）。但@midor所以如果我正确地理解了你的代码，你正在定义F f;（f将在我的构造函数中定义）作为对象字符串或任何我的类型，并生成它作为我保存的密钥，我想检查？所以compareTo比较键现在我是吧？（如果我不了解它们，不想复制它们） – NhatNienne 2015-01-10 09:52:38

一对二叉树的要求是，该节点的值必须是有序的，所以你应该让你的泛型类型为TreeNode<T extends Comparable<T>>，而不是仅仅<T>。然后你的compareTo方法可以委托给节点的compareTo。

来源

2015-01-09 23:13:30 chrylis

like（取我的问题的代码） return key.compareTo（node.key）;？会用我的类定义更新我的问题。 – NhatNienne 2015-01-09 23:14:57

@NhatNienne正是。请注意，你会想为'hashCode'和'equals'做同样的事情;你应该总是使用'Comparable'来定义这两个，因为'equals'在逻辑上等同于'compareTo == 0'。 – chrylis 2015-01-09 23:19:45

为二叉树（通用）实现compareTo（可比较的<T>）

回答

相关问题