二叉搜索樹遞歸到迭代版本

-1

我目前有一個二進制搜索樹的插入方法的遞歸版本。我現在試圖得到相同的結果，但我希望它是一個迭代版本。我認爲我非常接近，如果有人能夠給我一些建議，我還需要做些什麼才能讓這個工作成爲現實，因爲我在這一點上很難受。二叉搜索樹遞歸到迭代版本

遞歸：

public void insert(E item) 
    { 
    root = insert(root, item, 0); 
    } 

    private BNode insert(BNode ptr, E item, int d) 
    { 
    if (ptr == null) { 
    ++Size; 
    return new BNode(item, null, null, d); 
    } 


    int diff = item.compareTo(ptr.data); 
    if (diff < 0) 
    ptr.left = insert(ptr.left, item, d+1); 
    else if (diff > 0) 
    ptr.right = insert(ptr.right, item, d+1); 
    else 
    ; // duplicates; 

    return ptr; 
}

我對迭代版本目前代碼：

public void insert(E item) 
{ 
    BNode ptr = root; 
    int d = 0; // set the initial depth 

    if(ptr == null) { 
    ++Size; 
    root = new BNode(item, null, null, d); 
    } 

    while(ptr != null) { 
     int diff = item.compareTo(ptr.data); 
     if(diff < 0) 
     ptr.left = new BNode(item, null, null, d+1); // *EDIT 
     else if (diff > 0){ 
     ptr.right = new BNode(item, null, null, d+1); //*EDIT 
     } 
     else 
     break; // no duplicates 

     } 
     ++Size; 
    } 
}

來源

2014-04-16 DaBulls33

究竟是什麼錯誤？ –

@CyberneticTwerkGuruOrc當我對它進行測試時，我的版本不會編譯。項目沒有被插入到樹中。我失去了什麼問題？ – DaBulls33

只是爲了幫助你更好地提出你的問題：在這樣的問題中，人們應該首先跟蹤你的代碼，自己面對錯誤或問題，然後嘗試解決它！所以這使得你的問題不那麼有吸引力，至少在合理的時間內你可能得不到你需要的答案。 – mok

@CyberneticTwerkGuruOrc當我在其上運行的測試我的版本將無法編譯。項目沒有被插入到樹中。我失去了到什麼問題是？

您發佈的是相矛盾的觀點。如果它不能編譯它，那麼你是如何運行它的？我假設你可以編譯它。

你從來沒有真正添加除根節點之外的新節點。你想改變你的while循環。一旦你找到一個空白點，那麼你應該把新節點放在那裏。然後打破循環。

while(ptr != null) { 
     int diff = item.compareTo(ptr.data); 
     if(diff < 0) 
     ptr = ptr.left; 
     else{ 
     ptr = ptr.right; 
     } 

     //update this code here 
     if(ptr == null){ 
      ptr = new BNode(item, null, null, d); 
      ++Size; 
      break; 
     } 
    }

來源

2014-04-16 20:13:00

對不起，我應該更好地改寫我的問題。當將新節點添加到空點時，我會做類似於這個「BNode節點=新的BNode（ptr.left，item，d + 1）;」？ – DaBulls33

是的。你想要做那樣的事情，但要做'ptr'對象。 –

我更新了上面的代碼..我現在得到了更好的輸出，但是我仍然沒有得到樹的大小以及一些深度的正確結果。我認爲這可能與我的其他陳述有關？任何建議將不勝感激。 – DaBulls33

二叉搜索樹遞歸到迭代版本

回答

相關問題