Как добавлять элементы в дерево бинарного поиска итеративно?

Question

   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.

Answer 1

Хорошо, вот итерационная версия вашего алгоритма:

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 2

Вы можете найти реализацию на Java в википедии, что очень похоже на C # http://en.wikipedia.org/wiki/Binary_search_tree

Мы начинаем с корня:

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

, затем посмотрим, будет ли значение меньше или большечем корень.

if (data < root.getData()) {

Теперь мы знаем, нужно ли нам проходить слева или справа.Логика слева и справа одинакова.Мы смотрим, если слот пуст, и если это так, мы помещаем значение в этот слот.

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

Если слот содержит значение, то мы устанавливаем этот слот как корневой и продолжаем процесс.

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

Answer 3

Итерационный метод - это тот, который будет повторяться.

Итерационный метод подразумевает, что он будет вызываться повторно.Рекурсия подразумевает, что метод будет вызывать себя n раз, где n> 0.

Поиск в бинарном дереве поиска выполняется с помощью метода, который вызывает себя (рекурсивно), пока не найдет конец ветви.

Чтобы выполнить вставку, выполняется поиск, чтобы найти правильное место для размещения узла.