Как сгенерировать случайное двоичное дерево

Question

Мне дан список меток L и я рекурсивно * * * * * * * * * * * * * * * * * * * * *1003* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 100 * * * * * * * * * * * * * * * * * * * * 100 * * * * * * * * * * * * * * * * * * * * * * * * 100; желаемое поведение выглядит следующим образом:

generate(['A', 'B', 'C', 'D', 'E', 'F'])

может дать:

((('A', ('B', 'C')), ('D', 'E')), 'F')

Обратите внимание, что список листовых меток слева направо должно равняться L.

Я сомневаюсь, как случайным образом построить дерево. Это то, что у меня есть (я разбил список меток по случайному индексу.

def generate_tree(L):
    split = randint(1, len(L)-1)
    left = L[:split]
    right = L[split:]

    # call generate(left) and generate(right) based on some conditions

Я застрял. Буду признателен за пару советов или помощь.

Answer 1

Вы были слишком далеко. Все, что вам было нужно, - это базовый случай и создание результирующего кортежа из результатов рекурсивных вызовов:

def generate_tree(L):
    # base case
    if len(L) == 1: 
        return L[0]
    split = randint(1, len(L)-1)
    left = L[:split]
    right = L[split:]
    # recursion
    return (generate_tree(left), generate_tree(right))

>>> generate_tree(['A', 'B', 'C', 'D', 'E', 'F'])
(('A', 'B'), (('C', 'D'), ('E', 'F')))
>>> generate_tree(['A', 'B', 'C', 'D', 'E', 'F'])
((('A', 'B'), 'C'), (('D', 'E'), 'F'))
>>> generate_tree(['A', 'B', 'C', 'D', 'E', 'F'])
('A', (('B', 'C'), (('D', 'E'), 'F')))

А если вы играете в гольф и ищете модный (только = = 3,8) однострочник:

def gt(L):
    return (gt(L[:(s:=randint(1, len(L)-1))]), gt(L[s:])) if len(L) > 1 else L[0]

Answer 2

Вы можете случайным образом нарезать список и затем рекурсивно применить конструкцию дерева:

import random
def r_tree(d):
   _l, _r = tuple(d[:(_n:=random.randint(0, len(d)-1))]), tuple(d[_n+1:])
   l, r = _l if len(_l) < 3 else r_tree(_l), _r if len(_r) < 3 else r_tree(_r)
   return (d[_n], n[0] if len(n:=tuple(filter(None, [l, r]))) == 1 else n)

print(r_tree(['A', 'B', 'C', 'D', 'E', 'F']))

Вывод:

('D', (('A', ('B', 'C')), ('E', 'F')))