Python - フラットなリストツリーの実装：与えられた子、親を得る？

Question

私は、各ノードが "order"によって与えられたいくつかの子を持っている（ただし、各子は1つのノードしか持たない）ツリー用のPythonクラスを作成しています。私は、インデックスiのノードの子を返すメソッドchildren（self、i）を持っています。私は、インデックスiで子の親を取得するparent（self、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] 

注意を（あなたは2人の子供、ないn個を返します）。これを修正する：

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