Математическая функция для поиска числа листовых узлов в двоичном дереве

Question

Существует несбалансированное двоичное дерево неизвестной глубины. Число узлов, имеющих два дочерних узла, обозначается T2. Узел, имеющий только один дочерний элемент, обозначается T1, а листовые узлы обозначаются L. Если задано, что T1 = m и T2 = n узлами, вы можете определить математическую функцию f(m, n), которая дает количество листовых узлов L?

Например, в приведенном ниже дереве всего T2 узлы m = 3, а общие T1 узлы n = 2. Количество листовых узлов L = f(m,n) = 4. Можете ли вы найти математическую функцию f(m,n), которая дает количество листовых узлов для всех деревьев?

Answer 1

Это довольно легко. В полностью бинарном дереве (то есть, каждый не-лист имеет 2 детей) из внутренних узлов m, есть ровно m+1 листовых узлов. Каждый узел, который имеет только один дочерний элемент, может быть удален, и у вас все еще есть двоичное дерево. Итак, количество листовых узлов в L - это просто m+1. Или, отвечая на вопрос: f(m, n) = m + 1.

Может быть полезно привести пример того, что я подразумеваю под «удалением T1 узлов». Рассмотрим ваш пример. В правом 5 есть только один ребенок. Если мы удалим 5 и положим 9 под 2, количество листьев не изменится.

Если мы сделаем то же самое для 9 (поместите 4 непосредственно под 2), у нас есть полное двоичное дерево, то есть все нелисты имеют 2 детей.

Просмотреть изображение для графического объяснения того, как удалить все узлы типа T1без изменения количества листовых узлов.

Все, что остается доказать, что в дереве m внутренних узлов, где каждый не-лист имеет ровно 2 детей, число листьев узлов m+1:

Доказательство по индукции. Гипотеза индукции: |L| = |T2|+1

Основание: дерево состоит из одного узла. Очевидно, |L|=1 и |T2|=0, поэтому он держится.

Шаг: Рассмотрим дерево с корнем, который не является листом. По предположению, у него есть двое детей, слева и справа. По предположению индукции: |Lleft|=|T2left| + 1 и |Lright| = |T2right| + 1. Для всего дерева мы имеем |T2| = |T2left| + |T2right| + 1 и |L| = |Lleft| + |Lright|. Поэтому |L| = |T2left| + 1 + |T2right| + 1 = |T2| + 1.

---

Альтернативное доказательство

Свойство также может быть доказана непосредственно, без handwaving аргумента удаления T1 узлов. Опять же, по индукции, с предположением индукции .

• Основание: дерево один узел, так и |L| = 1|T2| = 0.
• Шаг 1 случай: дерево имеет корень только с 1 ребенком, X, затем |L| = |LX| и |T2| = |T2X|, так по предположению индукции.
• Шаг корпуса 2: дерево имеет корень с двумя детьми, слева и справа. По предположению индукции: |Lleft|=|T2left| + 1 и |Lright| = |T2right| + 1. Для всего дерева мы имеем |T2| = |T2left| + |T2right| + 1 и |L| = |Lleft| + |Lright|. Поэтому |L| = |T2left| + 1 + |T2right| + 1 = |T2| + 1.

Следовательно, или другими словами f(m, n) = m + 1.