Вопрос по бинарному дереву поиска

Question

Я смотрю на следующий код: http://netrsc.blogspot.com/2010/04/net-c-binary-tree.html

Правильно ли я думаю, что условие while (!Found) будет повторять дерево?

protected void Insert(T item)
{
    TreeNode<T> TempNode = Root;
    bool Found=false;
    while (!Found)
    {
        int ComparedValue = TempNode.Value.CompareTo(item);
        if(ComparedValue<0)
        {
            if(TempNode.Left==null)
            {
                TempNode.Left=new TreeNode<T>(item,TempNode);
                ++NumberOfNodes;
                return;
            }
            else
            {
                TempNode=TempNode.Left;
            }
        }
        else if(ComparedValue>0)
        {
            if(TempNode.Right==null)
            {
                TempNode.Right=new TreeNode<T>(item,TempNode);
                ++NumberOfNodes;
                return;
            }
            else
            {
                TempNode=TempNode.Right;
            }
        }
        else
        {
            TempNode=TempNode.Right;
        }
    }
}

Кроме того, для поискаи методы обхода, как они работают?Если из метода Traversal ничего не возвращается, кроме как из левой ветви, будет ли выполняться цикл Find снова?Как бы он узнал, чтобы выполнить вниз по правой ветви?

protected IEnumerable<TreeNode<T>> Traversal(TreeNode<T> Node)
{
    if (Node.Left != null)
    {
        foreach (TreeNode<T> LeftNode in Traversal(Node.Left))
            yield return LeftNode;
    }
    yield return Node;
    if (Node.Right != null)
    {
        foreach (TreeNode<T> RightNode in Traversal(Node.Right))
            yield return RightNode;
    }
}

Спасибо

Answer 1

Пример итерации дерева приведен в команде Find, которая вызывает функцию Traversal.

foreach (TreeNode<T> Item in Traversal(Root))

Функция Traversal будет итеративно возвращать элементы в дереве в порядке глубины, слева направо.Если вы посмотрите на код Traversal, он рекурсивно вызывает себя с левой стороны, а затем рекурсивно с правой стороны.

Traversal возвращает все дерево в итерируемом объекте, где элементы упорядочены по глубине, слева направо.Команда Find просто перебирает каждую из них, и когда она достигает совпадения, она выходит из цикла.По сути, Traversal возвращает упорядоченный повторяемый элемент, Find просматривает этот список в поисках совпадения.Find действительно даже не нужно знать, ищет ли он список, дерево или что-то еще.Просто нужно что-то перебрать, чтобы найти совпадение.

Answer 2

Не обязательно. Он будет перебирать только узлы на пути, куда должен быть добавлен вставленный узел. В этом цикле есть несколько операторов return, поэтому он по существу остановится, когда найдет правильное местоположение и добавит новый узел. Было бы более уместно (в коде) установить вместо переменной Found значение true.

Методы обхода возвращают узлы левого и правого поддеревьев. Следует отметить, что он использует yield return, а не просто return. Его использование создает перечислитель, в котором каждый возвращаемый элемент - это то, что возвращал бы числитель при его итерации. Думайте об этом как о приостановке выполнения, когда оно достигает оператора yield return. При переходе к следующему значению из вызывающего кода выполнение продолжается в этой точке, потенциально возвращая больше значений.

Find примет результаты обхода и вернет сохраненное значение, если будет найдено в одном из узлов.