爲二叉樹（通用）實現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>）

回答

相關問題