Python - Implémentation d'une arborescence de liste plate: Étant donné un enfant, obtenir un parent?

Question

Je crée une classe python pour un arbre dans lequel chaque nœud a un nombre d'enfants donné par "order" (mais chaque enfant n'a qu'un seul nœud). J'ai une méthode, enfants (self, i), qui renvoie les enfants d'un noeud à l'index i. J'ai besoin d'implémenter parent (self, i) qui obtiendra le parent d'un enfant à l'index i.

Voici ce que j'ai jusqu'à présent:

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 

Un arbre exemple représenté par ordre = 2 et la liste [45, 2, 123, 1, 8, 40, 456] ressemblerait à ceci:

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

Je sais qu'il y a probablement un moyen de renverser la méthode que j'ai utilisée pour les enfants (self, je) mais je ne sais pas comment.

Answer 1

Vous feriez l'opération inverse:

else: 
    #get parent of node i 
    return self._tree[(i-1)//self._order] 

Notez que votre implémentation ne fonctionne que pour les arbres binaires (vous revenez deux enfants, pas n). Corrigez-le comme ceci:

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