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

public class Test

{

  public static void Main()

  {

    Man[] men =

    {

      new Man(16, "Alex", 20), new Man(8, "Tim", 10), new Man(24, "Eddy", 15),

      new Man(4, "Peter", 22), new Man(12, "Kim", 11), new Man(20, "Teddy", 16),

      new Man(28, "John", 23), new Man(2, "Sim", 12), new Man(6, "Andy", 17),

      new Man(10, "Jane", 24), new Man(14, "Ham", 13), new Man(18, "Sandy", 18),

      new Man(22, "George", 25), new Man(26, "Dan", 14), new Man(30, "Benny", 19),

      new Man(1, "James", 26), new Man(3, "Van", 15), new Man(5, "Lenny", 20),

      new Man(7, "Juanita", 27), new Man(9, "Juan", 16), new Man(11, "Vanda", 21),

      new Man(13, "Brigit", 28), new Man(15, "Ken", 17), new Man(17, "Melissa", 22),

      new Man(19, "Chris", 29), new Man(21, "Tom", 18), new Man(23, "Larissa", 23),

      new Man(25, "Ringo", 30), new Man(27, "Dan", 19), new Man(29, "Belinda", 24),

      new Man(31, "Paul", 37)

    };

    Tree tree = /* Создайте дерево */

    foreach (/* Для каждого объекта из массива men */)

      /* Вызывайте метод Insert */

    Console.WriteLine ("\nPrinting all the men in the Tree\n");

    tree.Print();

    Console.WriteLine ("\n");

  }

}

Отладьте приложение так, чтобы все узлы дерева были выведены в консольное окно. Несмотря на хаотичную последовательность ввода элементов дерева, вывод содержимого дерева будет упорядоченной последовательностью, благодаря рекурсивному алгоритму метода Print, а также внутренним свойствам бинарного дерева.

Алгоритм уничтожения узла с искомым ключом несколько сложнее, так как при исключении узла возникает проблема, связанная с коррекцией ветвей дерева после удаления. Попробуйте реализовать метод удаления самостоятельно.

Рассмотрим задачу поиска в дереве. Cледует различать поиск узла по ключу (полю ID) и поиск по любому другому полю. Разница состоит в том, что дерево построено с учетом ключей, и его структура никак не связана с другими полями. В любом узле дерева мы всегда точно знаем, куда повернуть для того, чтобы отыскать заданный ключ, но мы не знаем этого, если ищем не ключ, а другое поле. Рассмотрим алгоритм поиска узла с заданным ключем. Добавьте в класс Tree пару методов, которые его реализуют.

public Man LookUp (int id) { return LookUp (root, id); }

private Man LookUp (Node node, int id)

{

  if (node == null)    // Не нашли

   return null;

  if (id == node.ManRef.ID)  // Нашли

    return node.ManRef;

  else

  {

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

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

    else

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

  }

}

Добавьте код вызова public-версии метода LookUp и добейтесь результата. Путем анализа или пошагового выполнения ответьте на вопрос. Сколько шагов рекурсии понадобится для того, чтобы найти узел с нечетным ключом. Код вызова метода может иметь такой вид.

int id = 5;

Console.WriteLine ("\nLooking for a man with id: {0}\n", id);

Man man = tree.LookUp (id);

Console.WriteLine ((man != null ? man.ToString() : "The tree has no man with this id"));