Бинарные деревья. Поиск узла с минимальным ключом. Вывод всех возможных путей в дереве, страница 3

Перейдем к рассмотрению класса Tree, который приводит в действие механизм бинарного дерева. Он содержит ссылку на корень дерева Node root и вспомогательную переменную Man search, которая должна упростить поиск объекта в дереве по полю, отличному от ключевого. Вы помните, что дерево упорядочено по полю id (ключевое поле). Если пользователь захочет найти объект по другому полю, например по имени, то статическая переменная search класса Man позволит сократить нагрузку на стек, которая неизбежна при работе с рекурсивными методами.

Дело в том, что при рекурсивном вызове в стек откладываются только локальные переменные и параметры, статические же переменные хранятся в единственном экземпляре и обслуживают все объекты класса. Вам необходимо дополнить код некоторых методов и свойств. Обратите внимание на то, что методы Insert и Print имеются в двух модификациях. Одна—для внешнего пользования (public), другая—для внутреннего (private). Последняя выполняет всю работу и скрывает манипуляции с корнем дерева, которые необходимы в рекурсивных процедурах.

public class Tree

{

private Node root;

  public static Man search = null;

  public Tree() { root = null; }

  public void Insert (Man m) { root = Insert (root, m); }

   private Node Insert (Node node, Man m) // Вставка нового узла со ссылкой на объект m класса Man

  {

             if (node == null)

      return new Node(m); //  Возвращаем ссылку на новый узел. Ее надо запомнить в каком либо узле

    else

    {

      if (/* ключ вставляемого узла меньше или равен ключу текщего узла */)

        // Вызовите Insert, подав на вход левую ветвь и присвойте результат node.Left

      else

        // Вызовите Insert, подав на вход правую ветвь и присвойте результат node.Left

      return node;

    }

  }

  public void Print () { Print (root); }

  private void Print (Node node)

  {

    if (node == null)

      return;

    //  Вызовите Print, подав на вход левую ветвь

    Console.WriteLine (node.ManRef.ToString());

    // Вызовите Print, подав на вход правую ветвь

  }

}

Рассмотрим алгоритм метода Insert. В нем следует найти место для включения в дерево узла, который ссылается на объект класса Man. Алгоритм поиска работает в соответствии с правилами формирования бинарного дерева.  Сравнивая значение ключевого поля id объекта, на который ссылается текущий узел дерева (node.ManRef.ID), со значением поля id нового, помещаемого в дерево объекта (m.ID), мы выбираем путь дальнейшего поиска в дереве.

Ссылка на текущий узел Node node делает шаг либо в левую ветвь (node.Left), либо в правую. Рекурсивная процедура поиска завершается в случае нахождения узла со свободой ветвью. Признаком этой ситуации является нулевое значение ссылки node. Включение узла в дерево подразумевает формирование нового узла со ссылкой на объект класса Man и коррекцию указателя последней ветви последнего пройденного узла. Нужную ветвь помнит переменная node передыдущего вызова рекурсивного метода Insert. Она автоматически выбирается из стека.

Так как включаемый узел может оказаться первым в дереве (если дерево было пусто), то в этом случае корректировать следует корень дерева. Напомним, что корнем называется указатель на начало дерева. Здесь помогает техника работы со ссылкой root. Она переписывается каждый раз. Это типичный трюк программиста, позволяющий заметно сократить нагрузку на стек, да и код, так как устраняет необходимость помнить состояние (первый узел или нет).

Проверьте работу дерева с помощью класса Test и статического метода Main. Для упрощения генерации дерева мы создаем массив ссылок на объекты класса Man, создаем пустое дерево, а далее в цикле надо вызвать его метод Insert, который заполнит дерево копиями ссылок на объекты класса Man. Вам надо написать код, реализующий сказанное. Создайте дерево (используйте конструктор) и в цикле вызывайте его метод Insert.