Создание дерева с заданными компонентами узлов и операторов

Question

Совершенно новый для древовидной структуры данных.Мне дают 2 переменные rules и operators.Каждый из них представляет собой список строк.Например:

op = ['&',"|","&"]
rules = ['a','b','c','d']

len(op) должно всегда равняться len(rules)-1, потому что op всегда соединяет правила или другой op.

Итак, в приведенном выше примере возможное дерево:

     "|"
   /      \
"&"        "&"
 |  \      |   \
 "a" "b"  "c"  "d"

Другое возможное дерево

         "&"
       /     \
     "|"      "d"
   /      \
"&"        "c"
 |  \     
 "a" "b"  

Недопустимое дерево:

"c"
 |   \
"|"  "d"

Приведенное выше дерево недопустимо, потому что другой оператор над оператором не может быть правилом.

Теперь, когда количество правил и операторов увеличится, будут бесконечные комбинации деревьев.У меня вопрос, возможно ли генерировать вышеупомянутые деревья случайным образом?Есть ли алгоритм для этого?В частности, есть ли способ случайного создания двоичных деревьев, если вы знаете, какими должны быть узлы и листья?

Спасибо

Answer 1

Вот моя трещина в решении.Я решил разбить алгоритм на две части.Сначала я сгенерировал случайную древовидную структуру с помощью операторов.Затем я прошел и добавил терминалы к текущим конечным узлам.

op = ['&',"|","+"]
terminals = ['a','b','c','d']

shuffle(op)
shuffle(terminals)



class tree:
    def __init__(self, l, r, v):
        self.left = l
        self.right = r
        self.value = v


root = tree(None, None, op[0])
op.pop(0)
def createNonTerminals(root):
    if len(op) == 0:
        return
    choice = randint(0,1)
    if choice == 0: #binary
        root.left = tree(None, None, op[0])
        op.pop(0)
        if len(op) > 0:
            root.right = tree(None, None, op[0])
            op.pop(0)
            createNonTerminals(root.right)
            createNonTerminals(root.left)

        else:
            createNonTerminals(root.left)
    else:
        choice = randint(0, 1)
        if choice == 1:
            root.right = tree(None, None, op[0])
            op.pop(0)
            createNonTerminals(root.right)
        else:
            root.left = tree(None, None, op[0])
            op.pop(0)
            createNonTerminals(root.left)

def addNonTerminals(root):
    if root.left == None:
        root.left = tree(None, None, terminals[0])
        terminals.pop(0)
    else:
        addNonTerminals(root.left)
    if root.right == None:
        root.right = tree(None, None, terminals[0])
        terminals.pop(0)
    else:
        addNonTerminals(root.right)  

Вот несколько примеров выходных данных

['+']
['&', 'd']
['~', 'f']
['a', '-']
['e', '|']
['b', 'c']

['|']
['&', '~']
['+', '-', 'b', 'a']
['d', 'f', 'e', 'c']

Answer 2

Я могу подумать об этом:

1 - перемешать ваши правила: например, ['a','b','c','d'] -> ['c','a','b','d'] (или, если вы можете повторить и «пропущенные» правила, просто сделайте случайный выбор, например ['c','d','b','b','d'] с нужной длиной)

2 - сделать каждое правило в списке "одиночным" деревом (т.е. просто листом), например, 'a' -> Tree('a', None, None)

3- пикслучайный индекс i в range(len(rules)-1)

4 - выберите случайный оператор oper из op (то же самое здесь, либо перемешайте op, затем возьмите элементы один за другим из списка, либо простокаждый раз выбирайте случайное число независимо, в зависимости от того, что вы хотите ...)

5 - замените 2 элемента в rules[i:i+2] новым единственным элементом Tree(oper, rules[i], rules[i+1])

6 - повторитес шага 3 до len(rules) == 1

7 - теперь у вас есть случайное дерево