プログラミングⅡ　第14回

木（ツリー）

線形リストは，Top（あるいは First）から矢印をたどっていくと，一本の線のようにつながっている．
今度は，木のように根（Root）から始まってときどき枝分かれしてつながっている．
一般には３つ以上枝分かれすることもある木を考えるが，ここでは枝分かれは２つしかしないものとする． すなわち二分木（Binary Tree）である．

下記のプログラムをよく読んで，理解しましょう． 
       program Tree1;
               (* ～　～ *)
               (* ｏＹｏ *)
               (* 　Ａ　 *)
       {$APPTYPE CONSOLE}
       uses SysUtils;

       type
         PTree = ^TTree;                      // 木を指すポインタ
         TTree = record
                   Upper : PTree;             // 上の枝(部分木)を指す
                   Point : Integer;           // 点数
                   Lower : PTree;             // 下の枝(部分木)を指す
                 end;

       var
         Root : PTree;                        // 根(木全体を指す)

       procedure TreeWoKaku(P : PTree; Eda : String);
                 {木を書く}

         procedure EdaWoKaku(Eda : String);
                   {枝を書く}
           var
             Depth : Integer;
             K : Integer;
           begin
             Depth := Length(Eda);
             for K := 2 to Depth do
               if Eda[K-1] = Eda[K]
                 then Write('　　')
                 else Write('　│');
             case Eda[Depth] of
               'U' : Write('　┌');
               'L' : Write('　└');
             end;
           end; {EdaWoKaku}

         begin
           if P = Nil                                // 枝の先端か？
             then begin                              //   yes
                    {
                    EdaWoKaku(Eda);                  //     途中の枝を書く
                    WriteLn;                         //
                    }
                  end
             else begin                              //   yes
                    TreeWoKaku(P^.Upper,Eda+'U');    //     上の部分木を書く
                    EdaWoKaku(Eda);                  //     途中の枝を書く
                    Write(P^.Point);                 //     点数を書く
                    WriteLn('┤');                   //
                    TreeWoKaku(P^.Lower,Eda+'L');    //     下の部分木を書く
                  end;
         end; {TreeWoKaku}

       procedure TensuuWoYondeTreeWoTsukuru;
                 {点数を読んで木を作る}
         var
           PNew   : PTree;                            // 新しい節を指す

         procedure TreeNiTsuika(var P : PTree);
                   {P が指す部分木に PNew が指している新しい節を追加する}
           begin
             if P = Nil                               // 枝の先端か？
               then begin                             //   yes
                      P := PNew;                      //     そこにつなげる
                    end
               else begin                             //   no
                      if PNew^.Point > P^.Point       //     その点数より上か？
                        then TreeNiTsuika(P^.Upper)   //   yes 上の部分木に追加
                        else TreeNiTsuika(P^.Lower)   //   no  下の部分木に追加
                    end;
           end; {TreeNiTsuika}

         var
           Tensuu : Integer;

         begin
           WriteLn('２桁の数を入れてください');
           WriteLn('それ以外の数を入れると終わります');
           Root := Nil;                               // 何も指さない（空ツリー）
           Write('点数 ? ');                          // 最初のデータを読む
           ReadLn(Tensuu);
           while Tensuu in [10..99] do                // 点数が２桁の数なら繰り返す
             begin
               New(PNew);                             // 新しい節を作る
               PNew.Upper := Nil;                     // 上の枝はまだない
               PNew.Point := Tensuu;
               PNew.Lower := Nil;                     // 下の枝もまだない
               TreeNiTsuika(Root);                    // 木に追加する
               WriteLn;
               TreeWoKaku(Root,'L');                  // 木を書く
               WriteLn;
               Write('点数 ? ');                      // 次のデータを読む
               ReadLn(Tensuu);
             end;
         end; {TensuuWoYondeTreeWoTsukuru}

       begin
         TensuuWoYondeTreeWoTsukuru;
       end.