ツリーをスレッドバイナリツリーに変換する方法

Question

バイナリツリーを作成するためのコードと再帰的な出力があります。どのようにバイナリツリーをスレッドツリーに変換し、それを繰り返し印刷するのですか？

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

答えは、あなたが作成するのと同じくらい簡単で簡単です。 （馬鹿を意図した）好きな探索方法を手前で決める。子供は最初に、または自己初めに。それから、リンクを設定して、そのトラバーサルを行います。基本的には、ツリーとリンクされたリストの両方が実装されています。

難しい問題は、獣のバランスを保つことです。リンクされたリストとノード数があれば、これはかなり役に立ちます。ヒント、私は再帰関数を使用してリストの真ん中を見つけ、新しいリーフノード（またはノードが存在しない場合はルート）を作成し、一時的な左鎖と一時的な右鎖から自分自身を削除します。子ノードを取得するには、各一時チェーンの関数を呼び出します。あなたが親を指すようにするつもりはなく、ノードが子供を指し抱えている検索の最適化が関与しないほとんどの実装については

。これは、与えられた親に対してn個の子を許可する。必要に応じて、子ノードを不揃いの配列またはリンクリストにすることができます。したがって、最終的に検索チェーンを他のデータ構造と組み合わせて結果を得ることになります。もちろん

自問する他の事はあるメモリ内のすべてを維持する実装令状を行います。あなたがそれが生きる場所ならば、データベースが仕事をすることを、あなたがはるかに良くしています。

最高の願い。良い質問。