Wie man Baum zu threadartigem binärem Baum umwandelt

Question

Ich habe einen Code, um einen binären Baum und seine rekursive Ausgabe zu verursachen. Wie konvertiert man den Binärbaum in den Threaded Tree und druckt ihn iterativ?

type 
    PAvl = ^TAvl; 
    TAvl = record 
      key: integer; 
      left: PAvl; 
      right: PAvl; 
      isThreaded: boolean; 
     end; 

procedure create(var root: PAvl; digit: integer); 
begin 
    if root = nil then begin 
    New(root); 
    root^.key := digit; 
    root^.left := nil; 
    root^.right := nil; 
    end 
    else if root.key > digit then 
    create(root.left, digit) 
    else 
    create(root.right, digit); 
end; 

procedure Print(root: PNode; depth: integer = 0); 
var 
    i: integer; 
begin 
    if root <> nil then 
    begin 
    Print(root^.right, depth + 1); 
    for i:=1 to depth do 
     Write(#9); 
    Writeln(root^.data); 
    Print(root^.left, depth + 1); 
    end; 
end; 

Answer 1

Die Antwort ist so einfach und direkt wie Sie es machen. (Wortspiel beabsichtigt) Sie entscheiden vorher, welche Traversalmethode Sie bevorzugen. Kind zuerst oder selbst zuerst. Dann tun Sie das Traversal und richten die Links ein. Grundsätzlich haben Sie dann sowohl einen Baum als auch eine verkettete Liste implementiert.

Das härtere Problem besteht darin, das Biest im Gleichgewicht zu halten. Mit einer verketteten Liste und einer Anzahl von Knoten hilft das ziemlich viel. Tipp, ich würde eine rekursive Funktion verwenden, um die Mitte der Liste zu finden, mache den neuen Blattknoten (oder root, wenn keine Knoten vorhanden sind), trimme dann selbst aus einer temporären linken Kette und einer temporären rechten Kette. Rufen Sie die Funktion für jede temporäre Kette auf, um untergeordnete Knoten zu erhalten.

Bei den meisten Implementierungen, bei denen keine Suchoptimierung erforderlich ist, möchten Sie lieber auf Parent zeigen, statt Knoten auf Children zu zeigen. Dies ermöglicht eine beliebige Anzahl n Kinder für einen bestimmten Elternteil. Wenn Sie möchten, können Sie die untergeordnete Liste mit einem unregelmäßigen Array oder einer verknüpften Liste füllen. Am Ende werden Sie die Suchkette mit anderen Datenstrukturen kombinieren, um Ihre Ergebnisse zu erhalten.

Natürlich ist die andere Sache, sich zu fragen, ist der Umsetzungsbefehl, der alles im Gedächtnis behält. Oftmals ist es viel besser, wenn die Datenbank die Arbeit erledigt, wenn sie dort lebt.

Mit freundlichen Grüßen. Gute Frage.