如何遞歸地將列表轉換爲BSTree？

我試圖列表從3 {1 {2 {，}}，5 {4 {，}，6 {，}}} 到二叉樹這樣如何遞歸地將列表轉換爲BSTree？

   3 
      1  5 
      2 4 6

我想將其轉換會更容易使用遞歸，但我卡住了。

public void ListToTree (ArrayList al) { 
    Iterator it = al.iterator(); 
    // n is the Tree's root 
    BSTnode n = new BSTnode(it.next()); 
    recurse(al,it,n); 

} 

void recurse (ArrayList al, Iterator it, BSTnode n) { 
    if(!it.hasNext()) return; 
    Object element = it.next(); 
    if(element=="{"){ 
      recurse(al,it,n.left()); 
      return; 
    } else if (element==",") { 
      recurse(al,it,n.right()); 
      return; 
    } else if (element =="}") { 

    } 

}

我不知道如何繼續，並想知道它是否是正確的軌道。請給我一些提示如何解決它。而且，我意識到我經常被困在遞歸問題上。是因爲我總是想把它分解嗎？我是否應該自上而下並仔細檢查它是否正確？提前致謝！

來源

2012-01-20 Audrey

首先：你是否受限於可怕的列表表示？您可以使用此代碼輕鬆構建基於BST規則的BST：

void insert(Node n, int value) { 
    if(n == null) { 
      n = new Node(value); 
    } else if(value < n.value) { 
      if(n.left == null) { 
       n.left = new Node(value); 
       return; 
      } 
      insert(n.left, value); 
    } else if(value > n.value) { 
      if(n.right == null) { 
       n.right = new Node(value); 
       return; 
      } 
      insert(n.right, value); 
    } 
}

您確實不必傳遞迭代器。只需使用列表中的值即可。此外，通常不會在方法簽名中使用實現類型。（即ArrayList - > List）。
這裏的另一個大錯誤是，您不使用==進行值比較，這是參考比較。使用等於替代，而是一個instanceof測試例如爲：

if(element instanceof String) { 
    String seperator = (String)element; 
    if("{".equals(separator)) 
     //do sth...

順便說一句，你是從代碼中缺少的東西是實際插入和向後導航後，你應該向下轉換的對象。
通過使用{-s和，-s導航找到正確的子樹後，檢查元素是否爲整數，然後將其設置爲當前節點的值。向後導航應該在}分支中，通過從recusion和一些技巧中返回一個級別或者在實際節點的父級上調用方法。
但我不建議你遵循這個方向，只要使用列表中的值和簡單的插入方法就容易多了。

來源

2012-01-20 11:03:03 zeller

謝謝你的建議。最初的問題是試圖記住一個樹的結構輸出（我選擇它到一個列表，singnature是我在那裏呈現的父母{leftchild {}，rightchild {}}這就是爲什麼我想要它的場景。 – Audrey

不幸的是，我並不真正理解你的第二句話...所以你選擇了列表和結構？（你可以很容易地把二叉樹放入一個數組，其中[0]是根，[2k + 1]是左邊和a [2k + 2]是右邊的孩子，k是表示父節點索引的正整數），所以即使你使用{}表示，你仍然不應該傳遞迭代器。你需要一個FSM解析器，詢問你是否需要更多的幫助 – zeller

是的，我完全忘記了數組表示形式!!謝謝你的提示。 – Audrey

如何遞歸地將列表轉換爲BSTree？

回答

相關問題