今日の記録 2020/6/21

勉強した

みんなのデータ構造 - P125 問6-7

一昨日に実装できた深さ優先探索をベースに pre, in, post-order を実装する。まずは単純な深さ優先探索と同様である pre-order を実装する。

pre_order_number(Tree) ->
   pre_order_number_s([Tree], [], 0).

pre_order_number_s([], Visited, _) ->
   lists:reverse(Visited);

pre_order_number_s([ {ID, nil, nil} | Rest], Visited, Number) ->
   pre_order_number_s(Rest, [{ID, Number} | Visited], Number+1);
pre_order_number_s([ {ID, Left, nil} | Rest], Visited, Number ) ->
   pre_order_number_s([ Left | Rest], [ {ID, Number} | Visited], Number+1);
pre_order_number_s([ {ID, nil, Right} | Rest], Visited, Number ) ->
   pre_order_number_s([ Right | Rest], [ {ID, Number} | Visited], Number+1);
pre_order_number_s([ {ID, Left, Right} | Rest], Visited, Number ) ->
   pre_order_number_s([ Left, Right | Rest ], [ {ID, Number} | Visited ], Number+1).

pre_order_number_test() ->
   Tree1 = {id0, nil, nil},
   [{id0, 0}] = pre_order_number(Tree1),
   Tree2 = {id0, {id1, nil, nil}, {id2, nil, nil}},
   [{id0, 0}, {id1, 1}, {id2, 2}] = pre_order_number(Tree2),
   Tree3 = {id0,
               {id1,
                   {id2, nil, nil},
                   {id3,
                       {id4, nil, nil},
                       {id5, nil, nil}}},
               {id6,
                   {id7,
                       {id8, nil, nil},
                       nil},
                   {id9,
                       {id10, nil, nil},
                       {id11, nil, nil}}}},
   [{id0, 0}, {id1, 1}, {id2, 2}, {id3, 3}, {id4, 4}, {id5, 5},
    {id6, 6}, {id7, 7}, {id8, 8}, {id9, 9}, {id10, 10}, {id11, 11}] = pre_order_number(Tree3).

ツリーの各ノードが id を持っているということで、その id が何番目に探索されるかを最終的な結果のリストとして出力した。

以下には in-order と post-order の実装を載せる。これは、子の状態に応じてスタックへの追加方法を変更するだけで実装ができた。

in_order_number(Tree) ->
   in_order_number_s([Tree], [], 0).

in_order_number_s([], Visited, _) ->
   lists:reverse(Visited);


in_order_number_s([{ID, nil, nil} | Rest], Visited, Number) ->
   in_order_number_s(Rest, [{ID, Number} | Visited], Number+1);

in_order_number_s([ {ID, Left, nil} | Rest], Visited, Number ) ->
   in_order_number_s([ Left, {ID, nil, nil} | Rest], Visited, Number);
in_order_number_s([ {ID, nil, Right} | Rest], Visited, Number ) ->
   in_order_number_s([ Right | Rest], [ {ID, Number} | Visited], Number+1);
in_order_number_s([ {ID, Left, Right} | Rest], Visited, Number ) ->
   in_order_number_s([ Left, {ID, nil, nil}, Right | Rest ], Visited, Number).

in_order_number_test() ->
   Tree1 = {id0, nil, nil},
   [{id0, 0}] = in_order_number(Tree1),
   Tree2 = {id0, {id1, nil, nil}, {id2, nil, nil}},
   [{id1, 0}, {id0, 1}, {id2, 2}] = in_order_number(Tree2),
   Tree3 = {id5,
               {id1,
                   {id0, nil, nil},
                   {id3,
                       {id2, nil, nil},
                       {id4, nil, nil}}},
               {id8,
                   {id7,
                       {id6, nil, nil},
                       nil},
                   {id10,
                       {id9, nil, nil},
                       {id11, nil, nil}}}},
   [{id0, 0}, {id1, 1}, {id2, 2}, {id3, 3}, {id4, 4},   {id5, 5},
    {id6, 6}, {id7, 7}, {id8, 8}, {id9, 9}, {id10, 10}, {id11, 11}] = in_order_number(Tree3).


post_order_number(Tree) ->
   post_order_number_s([Tree], [], 0).

post_order_number_s([], Visited, _) ->
   lists:reverse(Visited);

post_order_number_s([{ID, nil, nil} | Rest], Visited, Number) ->
   post_order_number_s(Rest, [{ID, Number} | Visited], Number+1);
post_order_number_s([ {ID, Left, nil} | Rest], Visited, Number ) ->
   post_order_number_s([ Left, {ID, nil, nil} | Rest], Visited, Number);
post_order_number_s([ {ID, nil, Right} | Rest], Visited, Number ) ->
   post_order_number_s([ Right, {ID, nil, nil} | Rest], Visited, Number+1);
post_order_number_s([ {ID, Left, Right} | Rest], Visited, Number ) ->
   post_order_number_s([ Left, Right, {ID, nil, nil} | Rest ], Visited, Number).

post_order_number_test() ->
   Tree1 = {id0, nil, nil},
   [{id0, 0}] = post_order_number(Tree1),
   Tree2 = {id0, {id1, nil, nil}, {id2, nil, nil}},
   [{id1, 0}, {id2, 1}, {id0, 2}] = post_order_number(Tree2),
   Tree3 = {id11,
               {id4,
                   {id0, nil, nil},
                   {id3,
                       {id1, nil, nil},
                       {id2, nil, nil}}},
               {id10,
                   {id6, 
                       {id5, nil, nil},
                       nil},
                   {id9,
                       {id7, nil, nil},
                       {id8, nil, nil}}}},
   [{id0, 0}, {id1, 1}, {id2, 2}, {id3, 3}, {id4, 4},   {id5, 5},
    {id6, 6}, {id7, 7}, {id8, 8}, {id9, 9}, {id10, 10}, {id11, 11}] = post_order_number(Tree3).