從建立二叉樹給定的數據

我無法理解如何建立從給定的一組數字的binary tree ...從建立二叉樹給定的數據

30 
15 
4 
NULL 
NULL 
20 
18 
NULL 
19 
NULL 
NULL 
NULL 
35 
32 
NULL 
NULL 
38 
NULL 
NULL

我已經通過我的書不見了，筆記和不能似乎弄明白了。 NULL是什麼意思？如果你能給我看一個正確的建樹，它會是最有幫助的，我是一個非常有視覺的人。我已經從我的作業中更改了數值和NULL的順序，所以不要擔心我沒有從中學習！

來源

2015-11-11 Bob

我想你需要通過地板上建立自己的樹。在前兩個分支30和15的末尾;在30以下，有4個NULL和15以下的thera是NULL和20。你下降一層：在4下，有18和NULL（NULL和NULL以下），20以下有19和NULL等。意味着分支末尾沒有任何東西。 –

這不會是一棵二叉樹。 – tekan

如果你只在這裏考慮的數字是二叉樹應該什麼樣子：

   +--+ 
       |30| 
      +------------------+ 
      |     | 
     +--+     ++-+ 
     |15|     |35| 
    +------------+   +----------+ 
    |   |  +--+  +--+ 
+-+   +-++  |32|  |38| 
|4|   |20|  +--+  +--+ 
+-+   +--+ 
     +-----+ 
     |18| 
     +---+ 
      | 
      +----+ 
      |19| 
      +--+

現在，如果你去通過列表再次，你會看到NULL分別表示什麼時候停止。 30有一個孩子，15，15有一個孩子4，4沒有一個孩子（後跟兩個NULL S），打算一升上來，15有第二個孩子20，20有孩子：18。 18沒有留下子女（以NULL表示），但有一個正確的子女19。它沒有任何子女（兩個NULL s）。 20也沒有任何更多的孩子：NULL導致15的其他孩子：35等

來源

2015-11-11 23:18:29 tekan

這是正確的！ – lrleon

我會假設第一個節點顯示樹的根節點。

列表中的以下兩個節點是即時葉子。

我會假定NULL值表明列表中的前一個節點只有一個葉節點或沒有葉節點。

對於樹結構中的節點排序，對於它是二叉搜索樹，每對葉節點應該大於或小於父節點，並且通常較小的值應該是左手葉節點。這意味着您可以通過從根目錄開始並選擇較高或較低的葉節點來搜索樹，遍歷樹，直到找到所需的節點。

來源

2015-11-11 23:19:30 EkcenierK

很可能你的問題涉及Łukasiewicz代碼。

給定一個二叉樹，一個Łukasiewicz碼是完整的前序遍歷生成的序列，其中內部節點標記爲a，外部標記（NULL指針）標記爲b。「a / b」的使用是慣例的問題。你可以使用任何其他符號;比特。

例如，此樹

應與您問題相關的樹

，具有與盧卡西維茨代碼序列如下：

aaabbaababbbaabbabb

考慮繪製與外部節點相同的樹。一些諸如

在該圖中，每個外部節點繪製的水平條。每個外部節點都是一個NULL指針。

現在進行前序遍歷。當您找到外部節點（即空指針）時，您打印NULL和eol。當您找到內部節點（與NULL不同）時，您將輸出密鑰值加上eol。

您將獲得正是您所提供的序列。

因此，任務是從這種盧卡西維奇遍歷重建原始的樹。這樣的任務可以通過這樣的例程完成：

Node * to_tree(istream & input) 
{ 
    string val; 
    input >> val; 
    if (val == "NULL") 
    return nullptr; 

    Node * p = new Node; 
    p->get_key() = atoi(val.c_str()); 
    p->left = to_tree(input); 
    p->right = to_tree(input); 

    return p; 
}

如果序列正確生成，那麼你可以安全地調用這個函數沒有任何風險;它會結束。如果你有興趣驗證輸入，那麼你可以做一個預處理。你初始化一個計數器爲零。每次找到一個密鑰時，您加1，當您找到一個NULL時，您減1。正確的序列必須以-1結尾。因此，這是因爲n節點的所有二進制樹具有n + 1外部節點（或NULL指針）。最後訪問的節點是外部的，這是唯一的，最後一次計數器達到-1。瞧

./my-program < my-input

等：

你可以自己日常適應你樹的實現，寫一個程序：

int main(int, char **) 
{ 
    Node * root = to_tree(cin); 
    return 0; 
}

你編譯它，然後你執行！

來源

2015-11-12 19:47:49 lrleon

從建立二叉樹給定的數據

回答

相關問題