爲什麼它不終止？

-2

var m_root : Node = root 
    private def insert(key: Int, value: Int): Node = { 
     if(m_root == null) { 
      m_root = Node(key, value, null, null) 
     } 
     var t : Node = m_root 
     var flag : Int = 1 
     while (t != null && flag == 1) { 
      if(key == t.key) { 
       t 
      } 
      else if(key < t.key) { 
       if(t.left == null) { 
        t.left = Node(key, value, null, null) 
        flag = 0 
       } else { 
        t = t.left 
       } 

      } else { 
       if(t.right == null) { 
        t.right = Node(key, value, null, null) 
        flag = 0 
       } else { 
        t = t.right 
       } 
      } 
     } 
     t 
}

我寫了迭代版插入一個節點到二叉搜索樹。我想在創建節點時終止，但它不會停止，因爲我認爲我沒有分配終止條件。如何編輯我的代碼以便在節點插入時終止？爲什麼它不終止？

來源

2011-12-06 Silvester

「二叉搜索樹的侮辱」？不能同意更多。 –

@KimStebel對不起，輸入錯誤TT – Silvester

在樣式上：如果您將'flag'重命名爲'carryOn'，並且將其設置爲初始爲'true'但分配了'false'的布爾變量，則代碼會稍微清晰一些當你想要終止循環的時候。 – dave4420

我不確定你想要什麼行爲，但原因很明顯。

您的循環是while條件，該條件將循環直到t爲null。所以雖然t非空，循環將繼續。

您只會將t分配給非空值 - 實際上您是，特別是檢查空案例並通過創建新節點來停止它。

因此，無論您需要重新考慮您的環路條件，還是確保t在某些情況下確實會變爲空，具體取決於您的實際算法要求。

而且由於您在底部返回t，所以我建議一般情況是錯誤的;如果t在這一點上是空的，那麼這個可能終止的唯一可能的方式是，所以無論如何返回這個將是毫無意義的。

來源

2011-12-06 17:23:21

我編輯我的代碼cos，啓發您的評論，但它不能自行終止。 – Silvester

@Jaehyun（基於你的編輯） - 想一下在普通情況下，節點已經存在的情況。在第一個if區塊的終止情況下，你沒有正確地將'flag'設置爲零，所以在那個時候它將永遠繞着while循環旋轉。 –

另外我同意dave4420這應該是一個更好的名稱'布爾'標誌。另外，由於你現在有一個標誌確定是否繼續，所以沒有理由在你的'while'條件中包含't！= null'檢查。 –

你的「if」語句中的循環

if(key == t.key) { 
    t 
}

第一句......什麼都不做，如果比較結果爲真。它不會終止循環。聲明t在這裏與return t不同義。您可以在該點設置flag = 0來終止循環。

來源

2011-12-06 17:48:38 Nexus6

爲什麼它不終止？

回答

相關問題