如何迭代地在二进制搜索树中添加元素？

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

我写了一个方法来递归地在BST中添加元素，它检查要添加小于或大于的值并将其添加到适当的位置，但我想知道迭代方法是如何工作的？ 我需要为我的BST迭代添加方法。

Answer 1

您可以在维基百科上找到Java实现，非常相似C＃ http://en.wikipedia.org/wiki/Binary_search_tree

我们从root开始：

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

然后查看该值是否小于root的os。

 if (data < root.getData()) { 

现在我们知道我们是否需要向左或向右移动。 左右的逻辑是相同的。 我们查看插槽是否为空，如果是，我们将值放在该插槽中。

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

如果插槽包含值，则我们将该插槽设置为root并继续该过程。

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

Answer 2

好的，这是您的算法的迭代版本：

 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; } } 

Answer 3

迭代方法是重复的方法。

迭代方法意味着它将被重复调用。 递归意味着该方法将自己调用n次，其中n> 0。

搜索二进制搜索树是使用调用自身（递归）的方法完成的，直到找到分支的结尾。

要执行插入操作，将执行搜索以找到放置节点的正确位置。