Дано: конечное бинарное дерево.
Найти: показать, что в любом конечном бинарном дереве нечётное количество вершин.
Решение:
1. Пусть N - общее количество вершин в бинарном дереве. Каждая вершина имеет либо 0, 1, либо 2 дочерних вершин.
2. В каждом бинарном дереве количество листовых вершин (вершин без дочерних) всегда больше, чем количество внутренних вершин (вершин с дочерними).
3. Обозначим количество листовых вершин как L и количество внутренних вершин как I. Тогда:
N = L + I.
4. Каждая внутренняя вершина добавляет 1 к количеству дочерних вершин. В бинарном дереве каждая внутренняя вершина может иметь максимум 2 дочерние вершины. Поэтому:
L = I + 1.
5. Подставим L в уравнение:
N = (I + 1) + I = 2I + 1.
6. Из этого следует, что N = 2I + 1, что означает, что N всегда нечётное, так как 2I - четное, и при добавлении 1 результат становится нечётным.
Ответ: в любом конечном бинарном дереве нечётное количество вершин.