Сколько неизоморфных c полных двоичных деревьев может сгенерировать n узлов?

Question

Изоморфизм означает, что произвольные поддеревья полного двоичного дерева, обменивающегося собой, могут быть идентичны другому.

Ответ определенно не каталонское число, потому что количество каталонского числа считает изоморфность c из них.

Answer 1

Я предполагаю, что под n узлами вы подразумеваете n внутренние узлы. Таким образом, у него будет 2n+1 вершин и 2n ребер.

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

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

Итак, предположим, что f(n) является число неизоморфных c бинарных деревьев с n узлами. Теперь мы можем go рекурсивно. Вот наши случаи:

1. n=0 есть один, пустое дерево.
2. n=1 есть один. Узел с 2 листьями.
3. n > 1. Давайте переберем m, число справа. Если 2m+1 < n, то есть f(m) максимальных деревьев справа, f(n-m-1) слева, и все они максимальны для f(m) * f(n-m-1). Если 2m+1 = n, то мы хотим, чтобы максимальное дерево справа было с m узлами, а максимальное дерево слева с m узлами, и то, которое справа, должно быть меньше или равно тому, которое на оставил. Но есть общеизвестная формула, сколько способов сделать это, f(m) * (f(m) + 1) / 2. И, наконец, у нас не может быть n < 2m+1, потому что в этом случае у нас нет максимального дерева.

Используя это, вы сможете написать рекурсивную функцию для вычисления ответа.

ОБНОВЛЕНИЕ Вот такая функция:

cache = {0: 1, 1:1}
def count_nonisomorphic_full_trees (n):
    if n not in cache:
        answer = 0
        for m in range(n):
            c = count_nonisomorphic_full_trees(m)
            if n < m+m+1:
                break
            elif n == m+m+1:
                answer = answer + c*(c+1)//2
            else:
                d = count_nonisomorphic_full_trees(n-m-1)
                answer = answer + c*d
        cache[n] = answer
    return cache[n]

Обратите внимание, что она начинается медленнее каталонских чисел, но все еще растет в геометрической прогрессии.