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

Теперь рассмотрим алгоритм поиска узла, в котором есть ссылка на объект, имя которого равно заданному (поиск по имени—полю name класса Man). Так как траектория просмотра узлов не известна, то следует искать везде. Вы уже имеете метод, который проходит по всем узлам дерева. Это—метод Print. Используя аналогию, разработайте код пары методов FindByName. Здесь вам понадобится переменная search класса Man, которую мы вставили в класс Tree в самом начале разработки. В нее следует записать ссылку на найденный объект. В начале поиска мы ее обнулим. Наличие этой (статической) переменной позволяет обойтись без параметра, который неоправданно загрузил бы стек. Мы упоминали, что во время рекурсии все параметры промежуточных вызовов временно хранятся в стеке.

public Man FindByName (string name)

{

  search = null;

  FindByName (root, name);

  return search;

}

private void FindByName (Node node, string name)

{

  if (node == null || search != null)

    return;

  if (/* искомое имя равно текущему */)

      // Запоминаем ссылку

  // Здесь код, аналогичный тому, что использовался в методе Print. Мы не знаем, где искать.

  // В худшем случае придется обойти все узлы дерева. Именно это мы и делали в Print.

}

Добавьте код проверки результата и добейтесь оного. Путем анализа или пошагового выполнения ответьте на вопрос. Сколько шагов рекурсии понадобится для того, чтобы найти узел с именем Paul (его индекс равен 31).

Рассмотрим метод, который позволяет определить размер дерева (количество его узлов). Его код выглядит очень просто, но прокрутить в сознании ход его выполнения не так просто. Попробуйте ответить на вопрос. Каким будет ответ, если в возвращаемом выражении убрать единицу.

public int Size() { return Size(root); }

private int Size (Node node)  // Количество узлов дерева

{

  if (node == null)

   return 0;

  else

    return Size (node.Left) + Size(node.Right) + 1;

}

Добавьте код вызова метода Size и убедитесь, что он дает верный результат. Используя те же идеи, разработайте код пары методов, которые возвращают высоту дерева, то есть длину максимального пути от корня до одного из листьев. Листом дерева называется узел, обе ссылки (left и right) которой равны нулю.

public int Depth () { return Depth (root); }

private int Depth (Node node)

{

  if (/* узел не существует */)

    // верните ноль

  int left = // Вычислите глубину левого поддерева (рекурсивный вызов)

  // Вычислите глубину правого поддерева (рекурсивный вызов)

  return (left > right ? left : right) // Здесь надо что-то добавить

}

Поиск узла с минимальным ключом

Вы уже привыкли к рекурсии, но вот метод, который ее не использует. Где мы ищем минимальный узел? Почему при выходе из метода не портится корень дерева, несмотря на присвоения вида node = node.Left;? Создайте пару симметричных методов с именем MaxValue.

public Man MinValue() { return MinValue (root); }

private Man MinValue (Node node)

{

  if (node == null || node.ManRef == null)

    throw new ArgumentException ("MinValue: Null parameter");

  while (node.Left != null)

    node = node.Left;

  return node.ManRef;

}

Проверьте работу последнего метода. Используйте такой вызов.

Console.WriteLine ("\nLooking for a man with the biggest id:\n");

Man man = tree.MaxValue();

Console.WriteLine ((man != null ? man.ToString() : "The tree is empty"));

Ответ должен выглядеть так.

Looking for a man with the biggest id:

31.     Paul           ; Age: 37

Вывод всех возможных путей в дереве

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

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