Konvertieren eines Preorder-Traversalarrays in ein Traversalarray der Ebenenreihenfolge (oder umgekehrt), da der Binärbaum in Level-Reihenfolge gefüllt war

Question

Angenommen, Sie haben einen binären Baum, der in der Ebenenreihenfolge gefüllt wurde, dh jede Ebene ist vor jeder gefüllt die untergeordneten Elemente dieses Knotens. Solch ein Baum kann eindeutig durch sein Level-Order-Traversal definiert werden. Zum Beispiel {1,2,3,4,5,6} ist

1 
2  3 
4 5 6 

A Vorordnungsdurchquerung dieser das Array erzeugen würde {1,2,4,5,3,6}

Ist Gibt es eine Möglichkeit, eines dieser Arrays direkt in das andere zu konvertieren, das ist schneller als das Erzeugen des eigentlichen Baums und das Vorbereiten der tatsächlichen Traversierung darauf? (für Baum mit n Knoten)

Answer 1

Ja, beides ist in einem Durchgang möglich.

Zuerst Ebene vorbestellen, weil das ein bisschen einfacher ist. Da es sich um einen mit Ebenen gefüllten Baum handelt, ist die Formel für den Index des linken Unterbaumknotens für jeden Knoten im Array 2*i+1, für den rechten ist es 2*i+2. Also nennen wir sie rekursiv in Vorbestellung und fügen Wurzelknoten an die Rückseite unseres gewünschten Arrays an.

def level_to_pre(arr,ind,new_arr): 
    if ind>=len(arr): return new_arr #nodes at ind don't exist 
    new_arr.append(arr[ind]) #append to back of the array 
    new_arr = level_to_pre(arr,ind*2+1,new_arr) #recursive call to left 
    new_arr = level_to_pre(arr,ind*2+2,new_arr) #recursive call to right 
    return new_arr 

Und nennen Sie es so, hier wird das letzte leere Array gefüllt.

ans = level_to_pre([1,2,3,4,5,6],0,[]) 

Nun, bevor ich zum Level Teil der Pre gehen, denken Sie daran dfs Rekursion verwendet, die einen Stapel hinter der Szene verwendet. Wo als bfs Warteschlange verwendet. Und das Problem in unserer Hand, Array in Level-First-Reihenfolge zu füllen, ist im Grunde bfs. Anstelle von rekursivem Aufruf (d. H. Stapel) müssen wir daher explizit eine Warteschlange unterhalten, um diese rekursiven Aufrufe zu emulieren.

Was wir hier tun ist, gegeben Wurzel eines Teilbaums, wir fügen es zuerst Array zu beantworten. Im Gegensatz zum obigen Problem ist es jetzt schwierig, den Index der untergeordneten Knoten zu finden. Links ist einfach, es wird direkt nach der Wurzel sein. Um den richtigen Index zu finden, berechnen wir die Gesamtgröße des linken Teilbaums. Dies ist möglich, weil wir wissen, dass es gefüllt ist. Wir verwenden jetzt eine Hilfsfunktion left_tree_size(n), die die Größe des linken Teilbaums in Anbetracht der Größe des gesamten Baums zurückgibt. Abgesehen von dem Index der Wurzel würde der zweite Parameter, den wir im Falle einer Rekursion übergeben würden, die Größe dieses Unterbaums sein. Um dies zu berücksichtigen, setzen wir ein Tupel (root, size) in unsere Warteschlange.

from math import log2 
import queue 

def pre_to_level(arr): 
    que = queue.Queue() 
    que.put((0,len(arr))) 
    ans = [] #this will be answer 
    while not que.empty(): 
     iroot,size = que.get() #index of root and size of subtree 
     if iroot>=len(arr) or size==0: continue ##nodes at iroot don't exist 
     else : ans.append(arr[iroot]) #append to back of output array 
     sz_of_left = left_tree_size(size) 
     que.put((iroot+1,sz_of_left)) #insert left sub-tree info to que 
     que.put((iroot+1+sz_of_left,size-sz_of_left-1)) #right sub-tree info 

    return ans 

Und zuletzt, hier ist die Hilfsfunktion, folgen Sie ein paar Beispiele, um herauszufinden, warum es funktioniert.

def left_tree_size(n): 
    if n<=1: return 0 
    l = int(log2(n+1)) #l = no of completely filled levels 
    ans = 2**(l-1) 
    last_level_nodes = min(n-2**l+1,ans) 
    return ans + last_level_nodes -1