Перейти к содержанию

7.7   Упражнения

7.7.1   Вопросы для самопроверки

1.   Полные, строгие и идеальные двоичные деревья

Два массива ниже представляют двоичные деревья в порядке обхода по уровням; None обозначает пустую позицию.

  • дерево A: [1, 2, 3, 4, 5, 6]
  • дерево B: [1, 2, 3, None, None, 6, 7]
  1. Какое из деревьев является полным?
  2. Какое из деревьев является строгим, то есть каждый его нелистовой узел имеет два дочерних узла?
  3. Есть ли среди них идеальное двоичное дерево? Объясните ответ для каждого дерева.
Ответ

  1. Дерево A полное. В нем не заполнен только последний уровень, причем узлы на нем расположены непрерывно слева направо. Дерево B не является полным: на последнем уровне слева уже есть пустые позиции, но справа от них еще находятся узлы.

  2. Дерево B строгое: узлы 1 и 3 имеют по два дочерних узла, а все остальные узлы являются листьями. Дерево A не является строгим, потому что у узла 3 есть только левый дочерний узел 6.

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

2.   Три порядка обхода одного дерева

Поместите массив [1, 2, 3, 4, 5, 6, 7] по уровням в полное двоичное дерево.

  1. Нарисуйте это дерево.
  2. Запишите последовательности прямого, симметричного и обратного обходов.
  3. Каким частям дерева соответствуют участки последовательности симметричного обхода слева и справа от корневого узла 1?
Ответ

  1. Получится дерево:

          1
    /   \
   2     3
  / \   / \
 4   5 6   7

  2. Прямой обход: 1, 2, 4, 5, 3, 6, 7; симметричный обход: 4, 2, 5, 1, 6, 3, 7; обратный обход: 4, 5, 2, 6, 7, 3, 1.

  3. Последовательность 4, 2, 5 слева от корневого узла 1 — симметричный обход левого поддерева, а 6, 3, 7 справа — симметричный обход правого поддерева.

3.   Сравнение двух двоичных деревьев поиска

Последовательно, слева направо, вставьте каждую из двух последовательностей в пустое двоичное дерево поиска:

  • последовательность A: [4, 2, 6, 1, 3, 5, 7]
  • последовательность B: [1, 2, 3, 4, 5, 6, 7]
  1. Запишите узлы, через которые проходит поиск числа 7 в каждом дереве.
  2. Если высота равна числу ребер на пути от корневого узла до самого удаленного листового узла, чему равна высота каждого дерева?
  3. Одинакова ли эффективность поиска числа 7 в двух деревьях? Объясните ответ, учитывая форму деревьев и пути поиска.
Ответ

  1. В дереве, построенном из последовательности A, путь поиска равен 4 → 6 → 7; в дереве из последовательности B — 1 → 2 → 3 → 4 → 5 → 6 → 7.

  2. Каждый уровень первого дерева заполнен, его высота равна 2. Второе дерево состоит только из правых дочерних узлов, его высота равна 6.

  3. Эффективность поиска 7 различается. Порядок вставки изменил форму и высоту двоичного дерева поиска. В первом дереве поиск 7 проходит только через 3 узла, а во втором — через все 7. Чем выше дерево, тем больше узлов в худшем случае приходится сравнивать вдоль пути.

7.7.2   Задачи по программированию

1.   Максимальная глубина двоичного дерева

Дан корневой узел root двоичного дерева. Каждый узел содержит целое значение и ссылки на левый и правый дочерние узлы.

Максимальной глубиной двоичного дерева назовем число узлов на пути от корневого узла до самого удаленного листового узла. Верните максимальную глубину дерева; глубина пустого дерева равна 0. Используйте рекурсию.

Подсказки
  1. В этой задаче глубина измеряется числом узлов: если в дереве есть только корневой узел, максимальная глубина равна 1
  2. Пусть рекурсивная функция возвращает максимальную глубину поддерева с корнем в текущем узле
  3. Для пустого узла верните 0, для непустого — max(depth(left), depth(right)) + 1

LeetCode

2.   Обход двоичного дерева по уровням

Дан корневой узел root двоичного дерева. С помощью очереди посетите все узлы уровень за уровнем сверху вниз, а внутри каждого уровня — слева направо.

Верните двумерный массив: первый вложенный массив хранит значения узлов на уровне корня, второй — значения следующего уровня и так далее. Для пустого дерева верните пустой массив.

Подсказки
  1. При обходе по уровням узлы нужно посещать в порядке их добавления, поэтому используйте очередь
  2. В начале каждой итерации в очереди находятся ровно узлы одного уровня
  3. Сначала запомните длину очереди, затем извлеките столько узлов и добавьте их дочерние узлы

LeetCode

3.   k-й наименьший элемент двоичного дерева поиска

Двоичное дерево поиска содержит n узлов с попарно различными значениями. Если расположить все значения по возрастанию, их позиции нумеруются начиная с 1.

Даны корневой узел root и целое число k, удовлетворяющее 1 <= k <= n. Верните значение узла на позиции k. Найдите ответ непосредственно во время симметричного обхода, не собирая предварительно значения всех узлов.

Подсказки
  1. Симметричный обход двоичного дерева поиска посещает значения узлов в порядке возрастания
  2. При симметричном обходе последовательно обрабатываются левое поддерево, текущий узел и правое поддерево; при посещении текущего узла увеличьте счетчик на 1
  3. Когда счетчик впервые станет равен k, значение текущего узла будет ответом и продолжать обход не потребуется

LeetCode

Оставляйте свои идеи, вопросы и предложения в комментариях