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