如何從文本文件構造無序二叉樹

Question

親愛的朋友我是一箇中級Java用戶。我陷入了下面的問題。我想從一個多行（假設有40行）文本文件構造一個無序的二叉樹[或最多有兩個節點的一般樹]。文本文件然後被分成兩半;讓說20:20行。然後爲每個半數計算一個特定的值（比如哈希值）並存儲在根節點中。所以每個節點都包含四個元素。兩個指向兩個孩子（左側和右側）和兩個原始文件兩半的哈希的指針。接下來的每一半（20行）重複這個過程，直到每一頁我們都有一行文本。讓節點有

public class BinaryTree { 

    private BinaryTreeNode leftNode, rightNode; 

    private String leftHash,rightHash; 

} 

我需要編寫樹結構和搜索功能的幫助。通過輸入一行來執行搜索。然後爲此查詢行創建哈希碼，並將其與每個節點上保存的兩個哈希進行比較。如果查詢行的散列值接近leftHas，則訪問leftNode，如果查詢行的散列值接近rightHash，則訪問rightNode。該過程一直持續到找到一個精確的散列。 我只需要樹的構建和搜索技巧。散列比較等不是問題

Answer 1

您需要先將文件讀入字符串。

字符串中的第一個字符可以用作根。根+ 1將是左邊，根+ 2將是正確的

考慮根節點（根+ 1），你也可以認爲這是根+ N.這意味着正確的節點將是根+ N + 1.

您現在可以遞歸解決這個問題，方法是確定您當前正在使用哪個節點，然後分別設置左側和右側。

所以讓我們想想，

已建立的根節點，左節點，右節點。在這一點上，你已經使用了3個字母/數字（它真的無關緊要，如果它是無序的）。下一步是向下移動一層並開始填充左邊，你有根，你需要左右節點。然後移動到正確的節點，執行此操作的左右節點，依此類推。

想一想，看看你在哪裏。

乾杯，

邁克

編輯：

要搜索，

搜索二叉樹也是遞歸的主題。 （我以爲你以前說過這棵樹是無序的，這可能會改變樹的佈局方式，如果它假設是有序的）。

如果是無序的，你可以簡單地遞歸樹在這樣

A.）檢查根節點 B.）選中左節點 C.）繼續檢查左節點的方式，直到有一個匹配或不再有左節點檢查 D.）遞歸回1，檢查右節點 E.）檢查左節點， F.）迴避，檢查正確的節點

這個主題將繼續，直到最終檢查了所有左節點，然後右節點。對此的關鍵是在任何時候你有一個根節點，首先左移，然後右移。 （我忘記了這是什麼遍歷類型，但如果你希望通過它實現它們，還有其他的，我個人認爲這是最容易記住的）。

然後，您將重複根節點的權利孩子。

如果在任何時候你得到一個匹配，退出。

記住這是遞歸的，所以要確保你一步一步想想自己的方式。根據定義，它是遞歸的，因爲您將始終爲樹的每個部分執行步驟x，y，z。

爲了擊敗死馬，讓我們看看只有3個節點開始。 （簡體）

首先根，

if(root == (what your looking for)) 
{ 
    return root 
} 
else if(root.leftNode == (what your looking for)) 
{ 
    return root.leftNode 
} 
else if(root.rightNode == (what your looking for)) 
{ 
    return root.rightNode 
} 
else 
{ 
    System.out.println("Value not found") 
} 

如果你有5個節點，這將是根將有左，右，以及root.leftNode將有一個左右...你也可以在root.leftNode上重複以上步驟，然後搜索root.rightNode

如果你有7個節點，你將搜索所有的root.leftNode，然後遞歸回去搜索root.leftNode。

我希望這有助於

圖片說起穿越樹木當工作在我看來好得多。

也許看看這裏的一個更好的視覺 http://www.newthinktank.com/2013/03/binary-tree-in-java/