Wie eine flache Liste in einen binären Baum konvertieren

Question

Lassen Sie uns sagen, ich habe eine Liste wie folgt:

flat_list = [None, 10, 5, 15, None, None, 11, 22] 

Ich weiß, dass der Algorithmus einen Baum aus einer nestled Liste für die Erstellung geht so:

def create_tree_from_nested_list(node_list): 
    if not node_list: 
     return node_list 
    d, l, r = node_list 
    tree = BinaryTree(d) 
    tree.set_left(create_tree_from_nested_list(l)) 
    tree.set_right(create_tree_from_nested_list(r)) 
    return tree 

der Ausgang für den angezeigten Code wäre:

10 
(l) 5 
(r) 15 
(l)  11 
(r)  22 

Wie würde ich mich über eine Funktion flache Listen in Bäume, so dass die linke diejenigen, die Schaffung werden an der Indexposition 2*i gespeichert und die richtigen werden an der Indexposition 2 * i + 1 gespeichert und die Ausgabe ist die gleiche wie die Ausgabe für die verschachtelte Liste. Jede Hilfe wird geschätzt.

Answer 1

Sie können Ihren geschachtelten Listencode so ändern, dass er in einer flachen Liste funktioniert. Da es keine einfache Möglichkeit gibt, die Unterbaumlisten aufzuteilen, schlage ich vor, den Index des Knotens, der als Argument erstellt werden soll, zusammen mit der ganzen flachen Liste zu übergeben. Der Index wird eine Standard von 1 (so müssen Sie es nicht für den Wurzelknoten passieren):

def create_tree_from_flat_list(node_list, index=1): 
    if index >= len(node_list) or node_list[index] is None: 
     return None 
    d = node_list[index] 
    l = index * 2 
    r = l + 1 
    tree = BinaryTree(d) 
    tree.set_left(create_tree_from_flat_list(node_list, l)) 
    tree.set_right(create_tree_from_flat_list(node_list, r)) 
    return tree 

Es ist durchaus nicht wesentlich separates d, in dieser Funktion l und r Variablen haben (sie könnte jeder genau dort berechnet werden, wo sie benutzt werden). Ich habe es so gemacht, um die Funktion deutlicher parallel zur geschachtelten Listenversion zu machen. l und r sind die Indizes der Wurzeln der linken und rechten Teilbäume.

Beispiel Ausgabe:

> print(create_tree_from_flat_list([None, 10, 5, 15, None, None, 11, 22])) 
10 
(l) 5 
(r) 15 
(l)  11 
(r)  22