無空作爲「空節點」的多態二進制搜索樹

我正在學校項目中，我們必須實現多態二進制搜索樹，而不是對樹的「空白」部分使用空引用，使用兩個類（ NonEmptyTree和EmptyTree），您應該使用多態性來確定何時應該發生某些操作。例如，如果我想在非多態二元搜索樹中插入一個特定的鍵值，通常您可以在您移動樹時遞歸地比較null，每當獲得compareTo值時都會堅持您的值爲0.然而在這種情況下，由於這個EmptyTree類的設計（只有它的一個實例），你基本上禁止主動比較「EmptyTree.getInstance（）」，這個「釋放」單個實例EmptyTree。（getInstance（）是一個靜態方法）。無空作爲「空節點」的多態二進制搜索樹

我用目前寫的代碼附加了兩個類的鏈接。我認爲Pastebin的語法突出顯示比在這裏插入我所有的代碼更容易閱讀，所以希望這是好的。

我不是在尋找解決方案或任何主要贈品，但我非常沮喪，因爲這樣實施樹似乎不合邏輯。（我已經實現了一個相當完整的具有空引用的BST，但似乎這個練習毫無意義，因爲我不知道如何前進）。此外，這種情況在下個星期天之前不會發生，所以我的憤怒並不是拖延的結果，而是因爲我個人的不足而感到挫折。

任何洞察力是讚賞。

的NonEmptyTree類： http://pastebin.com/

的EmptyTree類： http://pastebin.com/

正如你所看到的，我廣泛利用EmptyTree.getInstance（）方法，因爲它似乎是一個或多或少的效率方法來檢查我是否應該實例化一個新的NonEmptyList來堅持在那個地方。然而，教授在項目規範中的話特別聲明：「你需要使用多態性（和適當的異常處理）來處理空樹和非空樹之間的差異。否則會導致對你的負面調整很大項目等級「。但是，我覺得這些說明與上個學期的講座相矛盾，其中信息是「永遠不會使用」控制流「的異常處理，即濫用捕獲異常作爲控制代碼行爲的一種方式」。即使我使用try-catch塊返回Tree的單一方法也感覺像褻瀆神靈。

來源

2012-10-28 Arthur Collé

我理解你的無奈。但請記住，它可能很難寫，沒有它所有的Java語言的特定部分的問題感覺有點毫無意義。您是關於不使用異常來控制程序流程正確 - 我不知道如果這是教授真正需要的，或他的問題是否嚴重的措辭。也許澄清下次見面？你會得到加分的談論他的早期:-) –

嘿，我已經編碼了7個小時了講座。我全力以赴。基本上，正如塞繆爾說，整個演習的一點是要申報的大多數變量類型「樹」，然後因爲我們有兩個繼承的類（EmptyTree 和NonEmptyTree ），我們可以簡單地在類中的一個指定方法我們想要發生的行爲類型。因此，例如，我們可以遞歸調用「插入」的方法，並貫穿「NonEmptyList」的傳遞在整個時間，compareTo方法檢查鍵，以便把它貼在正確的位置，然後當的emptyList –

你可能會認爲這是一個「解決方案」或「重大贈品」，但...

我同意這似乎有點傻，至少在Java中。

的想法，不過，可能是有你的EmptyTree和NonEmptyTree類從某種PossiblyEmptyTree基類繼承，然後不同的覆蓋方式在各實現，而不調用者正確的行爲知道（或檢查），如果PossiblyEmptyTree是否爲空（，即多態性）。

一些代碼，可能會出現在您的解決方案：

public class EmptyTree ... { 
    ... 

    public V search(K key) { 
     /* definitely not here! */ 
     return null; 
    } 
}

來源

2012-10-28 04:10:32

無空作爲「空節點」的多態二進制搜索樹

回答

相關問題