Python convertit la liste en format de représentation d'arbre

Question

Moi et mon ami travaillons sur un simple projet Python. En fait, nous implémentons l'algorithme de la somme parallèle du préfixe à notre manière.

Nous sommes en train de créer et de traiter un arbre binaire avec un format vraiment bizarre. Nous souhaitons convertir ce format en un format accepté par les bibliothèques/logiciels d'impression Tree comme ete2.

Ainsi, tous les niveaux de l'arbre est poussé dans une liste de cette façon

[ [level0], [level1], ... [level i-1], [root] ] 

Dans notre format chaque liste interne (niveau de l'arbre) a même nombre de nœuds ou feuilles. Par exemple, disons que cette entrée est [1, 2, 3, 4, 5]. Cela produira la liste de sortie suivante: [[1, 2, 3, 4], [3, 7], [10, 5], [15]]

Le problème avec l'exemple de sortie ci-dessus est que parfois les feuilles ne sont pas au dernier niveau, mais elles sont incluses dans les listes de niveau supérieur. Cela rend difficile le traitement de la liste des listes et la distinction des noeuds des feuilles et leur disposition dans la bonne position.

Nous aimerions imaginer cela comme suit:

http://i.imgur.com/BKrqNZi.png

où un nombre compris entre parenthèses sont les nœuds et les autres feuilles ones. Pour produire cet arbre de sortie, nous aimerions utiliser une bibliothèque de dessin d'arbre. La plupart d'entre eux attendent ce type de format: [root, [left], [right]]

Ainsi, dans notre exemple, notre format devrait être quelque chose comme ceci:

[15, [10, [3, [1], [2]], [7, [3], [4]] ], [5] ] 

Parce que nous ne sommes pas en mesure, au moment de réécrire toute la logique de notre code, nous cherchons une façon intelligente de convertir notre format bizarre en celui-là.

Toutes les idées sont les bienvenues. Merci beaucoup d'avance.

Answer 1

Vous pouvez profiter du fait que pour l'élément dans la ligne r, col c de votre arbre, les éléments de l'enfant à gauche et à droite sont en position c*2 et c*2+1 de la ligne suivante, respectivement, si ces éléments existent (autrement ce noeud est une feuille). Il suffit de mettre cela dans un des algorithmes:

def normalize(tree, row=0, col=0): 
    try: 
     node = tree[row][col] 
     left = normalize(tree, row+1, col*2) 
     right = normalize(tree, row+1, col*2+1) 
     return [node, left, right] if left or right else [node] 
    except: 
     return None # child index does not exist 

Exemple:

>>> tree = [[1, 2, 3, 4], [3, 7], [10, 5], [15]] 
>>> print normalize(tree[::-1]) # reverse the list! 
[15, [10, [3, [1], [2]], [7, [3], [4]]], [5]]