Skip to main content
 首页 » 编程设计

python之基于二叉树叶子创建公式

2024年11月01日15mfryf

我有长度为 n 的点列表(在下面的示例中 n = 6)之后我根据这些默认点做了一些其他点,例如点 7 是由“anding”点 5 和点 4 等等现在我的问题是基于我拥有的数据结构,如何检索公式链?例如,对于第 10 点(递归或非递归),我怎么能说这一点来自哪里?

如果我想知道第 10 点是如何产生的,它必须返回如下内容:

(((5 & 4) | 3) | 2) & (5 & 4) 

请您参考如下方法:

在开始之前,您需要展示您所拥有的内容。我建议这样:

points = [ None,  # dummy value to fill index 0 (we want to start at 1) 
           None, None, None, None, None, None,  # for the first six atoms 
           (5, 4, '&'),  # for point 7 
           (7, 3, '|'),  # for point 8 
           (8, 2, '|'),  # for point 9 
           (9, 7, '&') ]  # for point 10 

然后将公式创建为字符串只是递归的:

def formula(points, n): 
  if points[n] is None: 
    return str(n) 
  a, b, operator = points[n] 
  return '(%s %s %s)' % (formula(points, a), operator, formula(points, b)) 
 
print formula(points, 10) 

这将打印

((((5 & 4) | 3) | 2) & (5 & 4)) 

要将公式中使用的所有点作为一个集合,只需使用:

def used(points, n): 
  if points[n] is None: 
    return { n } 
  a, b, operator = points[n] 
  return used(points, a) | used(points, b) 
 
print used(points, 10) 

将打印:

set([2, 3, 4, 5])