如何在二叉搜索树中迭代添加元素
本文关键字:迭代 添加 元素 搜索树 | 更新日期: 2023-09-27 18:16:36
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相加方法。
好的,这是你的算法的迭代版本:
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;
}
}
你可以在wikipedia上找到一个Java实现,它与c#非常相似http://en.wikipedia.org/wiki/Binary_search_tree
我们从根开始:
Node root = m_root;
while (root != null) {
然后查看该值是否小于OS大于root。
if (data < root.getData()) {
现在我们知道是向左遍历还是向右遍历。左边和右边的逻辑是一样的。查看槽是否为空,如果为空,则将值放在该槽中。
if (root.getLeft() == null) {
root.setLeft(new TreeNode(data, null, null));
return;
}
如果槽位包含值,则将该槽位设置为根并继续此进程。
} else {
root = root.getLeft();
}
迭代方法是一种可以重复的方法。
迭代方法意味着它将被反复调用。递归意味着该方法将调用自己n次,其中n> 0。
搜索二叉搜索树的方法调用自己(递归),直到找到分支的末端。
要执行插入操作,将执行搜索以找到放置节点的正确位置。