python - Python - 平面列表树实现：给定孩子，得到父母？

Question

我正在为一棵树创建一个 python 类，其中每个节点都有许多由“order”给出的子节点（但每个子节点只有一个节点）。我有一个方法，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 和 list [45, 2, 123, 1, 8, 40, 456] 表示的示例树如下所示：

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

我知道可能有一种方法可以逆转我用于儿童（self，i）的方法，但我不确定如何。

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