Рекурсивная функция для генерации двоичного дерева

Question

Я пытаюсь создать функцию «generate_tree (L)», которая принимает список букв и возвращает двоичное дерево. Где каждая буква это лист. например, со списком:

L = ['A', 'B', 'C']

функция должна случайным образом вернуть одно из этих деревьев:

['A',['B', 'C']] or [['A','B'], 'C'] 

Где первый пример представляет это дерево:

Ну, это не очень хорошо - у меня было решение, но оно также вернуло много пустых списков, и это было беспорядок. Это моя попытка:

from random import randint
def generate_tree(L):
    n = len(L)
    if not L: #base case yield empty
        yield L
        return
    randomSplit = randint(1,n-1)
    leftList = L[0:randomSplit]
    rightList = L[randomSplit:]

List = ['A','B','C']
list(generate_tree(L))

Моя попытка с помощью randomSplit состоит в том, чтобы разделить список на два списка в случайной непустой позиции:

['A','B','C'] --> leftList: ['A'], rightList: ['B','C']

Я знаю, что мне нужноотправлять leftList и rightList рекурсивно, но я не могу понять это правильно. Я хотел бы, чтобы вы взялись за этот вопрос

Answer 1

Это решение выбирает случайную точку разделения и делит список оттуда:

from random import randint

def tree(lst):
    if len(lst) == 1:
        return lst[0]
    elif len(lst) <= 2:
        return lst
    else:
        ix = randint(1, len(lst) - 1)
        retval = [tree(lst[:ix]) , tree(lst[ix:])]
        return retval

tree(['A','B','C']) производит только один из двух необходимых выходов.

Пример выходов из:

for _ in range(10):
    print(tree(['A','B','C','D']))

[['A', 'B'], ['C', 'D']]
[[['A', 'B'], 'C'], 'D']
['A', [['B', 'C'], 'D']]
[['A', 'B'], ['C', 'D']]
[['A', 'B'], ['C', 'D']]
['A', [['B', 'C'], 'D']]
[['A', ['B', 'C']], 'D']
[['A', ['B', 'C']], 'D']
[[['A', 'B'], 'C'], 'D']
['A', ['B', ['C', 'D']]]

Answer 2

Я думаю, что ваш базовый случай - это когда длина списка равна 2 (или меньше в особых случаях), поэтому вот идея, основанная на использовании random.randint:

from random import randint

def tree(lst):
    if len(lst) <= 2:
        return lst
    else:
        ix = randint(0, len(lst) - 1)
        retval = [lst[ix]]
        retval.append(tree(lst[:ix] + lst[ix+1:]))
        return retval

Это должно работать и для спискадлина больше 3 или длина 0 или 1.

---

РЕДАКТИРОВАТЬ:

Если первый элемент списка должен быть первым элементом (как предложеноваш пример), это должно сделать:

from random import randint

def tree(lst):
    if len(lst) == 1:
        return lst[0]
    if len(lst) <= 2: # this matters is lst == []
        return lst
    else:
        ix = randint(1, len(lst) - 1)
        retval = [lst[:ix]] if ix > 1 else lst[:ix]
        retval.append(tree(lst[ix:]))
        return retval