Python - реализация дерева плоских списков: данный дочерний элемент, получить родительский?

Question

Я создаю класс python для дерева, в котором у каждого узла есть количество дочерних элементов, заданных "порядком" (но у каждого дочернего элемента есть только один узел). У меня есть метод children(self,i), который возвращает дочерние элементы узла с индексом i. Мне нужно реализовать parent(self, i), который получит родителя ребенка по индексу i.

Вот что у меня так далеко:

class Tree:
  def __init__(self, order=2, l=[]):
    self._tree = l
    self._order = order

  def children(self, i):
    left = self._tree[(i+1)*self._order-1]
    right = self._tree[(i+1)*self._order]
    return [left, right]

  def parent(self, i):
    if i>len(self._tree):
        return ValueError
    elif i==0:
        return None
    else:
        #get parent of node i

Пример дерева, представленного order=2 и списком [45, 2, 123, 1, 8, 40, 456], будет выглядеть следующим образом:

      45
    /    \
  2       123
 / \     /   \
1   8   40   456   

Я знаю, что, вероятно, есть способ, которым я могу изменить метод, который я использовал для детей (себя, я), но я не уверен, как.

Answer 1

Вы бы сделали обратную операцию:

else:
    #get parent of node i
    return self._tree[(i-1)//self._order]

Обратите внимание, что ваша реализация работает только для двоичных деревьев (вы возвращаете двух детей, а не n). Исправьте это так:

def children(self, i):
    return self._tree[(i*self._order+1):((i+1)*self._order+1)]