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