Python - 扁平列表树实现：给定孩子，获得父母？

Question

我正在为一棵树创建一个python类，其中每个节点都有一些由“order”给出的孩子（但每个孩子只有一个节点）。我有一个方法，children（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 

通过顺序= 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] 

请注意，您的实现只工作了二叉树（你回两个孩子，不ñ）。像这样纠正它：

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