Создание формулы на основе листьев бинарного дерева

Question

У меня есть список точек с длиной n (в приведенном ниже примере n = 6), после этого я сделал некоторые другие точки на основе этих точек по умолчанию, например, точка 7 сделана путем "anding" точки 5 и точки 4 и так далее, теперь мой вопрос на основе структуры данных, как я могу получить цепочку формул? например, для точки 10 (рекурсивной или нерекурсивной), как я могу сказать, откуда эта точка наступает?

Если я хочу знать, как создается пункт 10, он должен вернуть что-то вроде этого:

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

Answer 1

Вам нужно представление того, что у вас есть, прежде чем начать. Я предлагаю что-то вроде этого:

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