如何在二叉搜索樹中迭代添加元素？

public void Insert(int value) 
    { 
     if (value < Data) 
     { 
      if (LeftNode == null) 
      { 
       LeftNode = new TreeNode(value); 
      } 
      else 
      { 
       LeftNode.Insert(value); 
      } 
     } 
     else if (value > Data) 
     { 
      if (RightNode == null) 
      { 
       RightNode = new TreeNode(value); 
      } 
      else 
      { 
       RightNode.Insert(value); 
      } 
     } 
    }

我寫了一個方法在BST中遞增添加元素，它檢查添加的值小於或大於，並將其添加到適當的位置，但我想知道迭代方法的工作原理？我需要爲我的BST迭代添加方法。如何在二叉搜索樹中迭代添加元素？

來源

2011-12-05 Desire

是，非遞歸的方法，其實我是從含有約10000字，當我將它們添加到BST一個文本文件中讀取數據，它給了我STACKOVERFLOW EXCEPTION。我認爲遞歸方法是問題。 – Desire

他試過了什麼？他已經放下了他的方法... – Russell

@Aki：輸入文件是否已排序？如果是這樣，你正在建立一個鏈表而不是二叉樹。每個元素都會被添加到右側。 –

您可以在維基百科在Java中實現，這也非常類似C＃http://en.wikipedia.org/wiki/Binary_search_tree

我們開始在根：

Node root = m_root; 
    while (root != null) {

再看看，如果值小於OS比根大。

if (data < root.getData()) {

現在我們知道是否需要左右移動。左側和右側的邏輯是相同的。我們看看插槽是否爲空，如果是，我們將該值放在該插槽中。

if (root.getLeft() == null) { 
    root.setLeft(new TreeNode(data, null, null)); 
    return; 
}

如果插槽包含一個值，那麼我們將該插槽設置爲root並繼續該過程。

} else { 
    root = root.getLeft(); 
}

來源

2011-12-05 10:43:14

問題是關於它是如何工作的，而不是要求實現。 – Russell

的代碼是非常簡單的，說明很可能解釋每一行做的，但我可以爲你做 –

感謝花花公子「Fujiy」 – Desire

迭代方法是一個會重複的方法。

迭代方法意味着它會被重複調用。遞歸意味着該方法將自己調用n次，其中n> 0.

搜索二叉搜索樹是使用一種方法完成的，該方法調用自身（遞歸），直到找到分支的末尾。

執行插入操作，執行，找到正確的位置來放置節點的搜索。

來源

2011-12-05 10:52:40 Russell

羅素，我的理解是一個迭代方法使用一個循環，而不是自稱的。任何使用遞歸的方法，理論上都可以使用循環來完成，但遞歸更容易。最好兩個世界的是尾遞歸 –

@Fujiy的方法內部的循環是在一個方法中的迭代表達。迭代方法是循環本身的一部分。 – Russell

好吧，這裏是你的算法的迭代版本：

public void Insert(int value) 
{ 
    TreeNode current = this; 
    while (current != null) 
    { 
     if(current.Data < value) 
      if(current.LeftNode == null) 
      { current.LeftNode = new TreeNode(value); break; } 
      else current = current.LeftNode; 
     else 
      if(current.RightNode == null) 
      { current.RightNode = new TreeNode(value); break; } 
      else current = current.RightNode; 
    } 
}

來源

2011-12-05 11:07:19 Tudor

我認爲這是值得一提的：一般BST一個節點應該在其左子樹下鍵，而在右高。但是，這個算法反過來工作。 – toderik

如何在二叉搜索樹中迭代添加元素？

回答

相關問題