给定组件节点和运算符创建树

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

我能想到这个：

1- 打乱你的规则：例如['a','b','c','d'] -> ['c','a','b','d']（或者如果你可以重复并且 "missing" 规则只是随机生成一个 select 离子，例如具有所需长度的 ['c','d','b','b','d']）

2- 使列表中的每个规则成为 "singleton" 树（即只是一片叶子），例如'a' -> Tree('a', None, None)

3- 在 range(len(rules)-1)

中选择一个随机索引 i

4- 从 op 中选择一个随机运算符 oper （此处相同，要么随机播放 op 然后从列表中一个一个地取出元素，或者只是 select每次独立随机一个，取决于你想要什么......）

5- 用新的单个元素 Tree(oper, rules[i], rules[i+1])

替换 rules[i:i+2] 处的 2 个元素

6- 从第 3 步开始重复，直到 len(rules) == 1

7- 你现在有一棵随机树

Answer 2

这是我的解决方案。我决定将算法分成两部分。首先，我使用运算符生成了一个随机树结构。然后我通过并将终端添加到当前的叶节点。

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

给定组件节点和运算符创建树

Create Tree Given Component Nodes and Operators

python

algorithm

tree

binary-tree