如何迭代地在二叉搜索树中添加元素? [英] How to add elements in Binary search tree iteratively?

问题描述

   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的迭代添加方法.

I wrote method to add element in BST recursively, It checks for value to add less than or greater than and add it in its proper place, but I want to know how iterative method works? I need iterative add method for my BST.

推荐答案

您可以在Wikipedia中找到Java的实现，这与C#非常相似

You can find a implementation in Java at wikipedia, what is very similar C# http://en.wikipedia.org/wiki/Binary_search_tree

我们从根开始:

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

然后查看该值是否小于根大于os.

then look if the value is less os greater than root.

if (data < root.getData()) {

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

Now we know if we need to traverse at left or right. The logic at left and right are the same. We look if the slot is empty and if it is, we put the value at that slot.

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

如果该插槽包含一个值，那么我们将该插槽设置为root并继续该过程.

If the slot contains a value, then we set that slot as root and continue the process.

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

这篇关于如何迭代地在二叉搜索树中添加元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！