如何生成随机二叉树

Question

我得到了一个标签列表L，我希望递归地从[=]生成一个随机二叉树11=].

期望的行为是这样的：

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

您可以随机切片列表，然后递归应用树构造：

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')))

Answer 2

你离得太远了。您所需要的只是一个基本案例，并根据递归调用的结果构建生成的元组：

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]

如何生成随机二叉树

How to generate random binary tree

python

recursion

binary-tree

python-3.x