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

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'] (或者，如果您可以重复和“丢失”规则，只需随机选择所需长度的 ['c','d','b','b','d'] )

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

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

中选择一个随机索引 i

4- 从 op 中选择一个随机运算符 oper (这里也是一样，要么打乱 op 然后从列表中一个一个地取出元素，或者每次都独立地选择一个随机的，这取决于你想要什么......)

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

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

7- 你现在有一棵随机树