Rechts ein binärer Baum fädeln

Question

Ich habe eine verdammt lange Zeit versucht, dieses herauszufinden. Überall, wo ich hinsehe, scheint es mir nur zu erklären, wie man die Liste rekursiv durchquert (den Teil, den ich tatsächlich verstehe). Kann da jemand da raushauen, wie genau ich die Liste zunächst durchgehen kann und die tatsächlichen Vorgänger-/Nachfolgerknoten finde, damit ich sie in der Knotenklasse markieren kann? Ich muss in der Lage sein, einen einfachen binären Suchbaum zu erstellen und die Liste durchzugehen und die Nulllinks zum Vorgänger/Nachfolger umzuleiten. Ich habe etwas Glück mit einer Lösung etwa wie folgt hatte:

thread(node n, node p) { 
    if (n.left !=null) 
     thread (n.left, n); 
    if (n.right !=null) { 
     thread (n.right, p); 
    } 
    n.right = p; 
} 

Answer 1

Aus Ihrer Beschreibung, ich nehme an, Sie einen Knoten mit einer Struktur suchen so etwas wie:

Node { 
    left 
    right 
} 

... und dass Sie einen binären Baum haben, der links und rechts angeordnet ist, und dass Sie Werte links und rechts so neu zuweisen möchten, dass er eine doppelt verknüpfte Liste aus einer Tiefenüberquerung des Baums erstellt.

Das root (kein Wortspiel beabsichtigt) Problem mit dem, was Sie bisher haben, ist, dass der "Knoten p" (kurz für vorherige?), Die während der Durchquerung übergeben wird, unabhängig von wo in der Struktur Sie derzeit ist sind - es muss immer den zuvor besuchten Knoten enthalten. Um dies zu tun, muss jedes Mal, wenn ein Thread ausgeführt wird, dieselbe "vorherige" Variable referenzieren. Ich habe etwas Python-isch Pseudo-Code mit einem C-ism gemacht - wenn Sie nicht vertraut sind, bedeutet "&" "Bezug auf" (oder "Ref" in C#), und "*" bedeutet "Dereferenzierung und gib mir das Objekt, auf das es zeigt ".

Node lastVisited 
thread(root, &lastVisisted) 

function thread(node, lastVisitedRef) 
    if (node.left) 
    thread(node.left, lastVisitedRef) 
    if (node.right) 
    thread(node.right, lastVisitedRef) 

    // visit this node, reassigning left and right 
    if (*lastVisitedRef) 
    node.right = *lastVisitedRef 
    (*lastVisitedRef).left = node 
    // update reference lastVisited 
    lastVisitedRef = &node 

Wenn Sie dies in C implementieren würden, müssen Sie eigentlich einen Doppelzeiger die Referenz zu halten, aber die Idee ist das gleiche - Sie müssen die Lage des „zuletzt besuchten Knoten“ beharren während des gesamten Durchlaufs.