今日の記録 2020/6/25

勉強した

みんなのデータ構造 - P125 問6.8 の準備

渡されたノードの ID を使ってツリーを探索するためには、これまでの実装だと不可能であるので別な表現をする必要がありそうなので考えた。とりあえず思い付いた中で良さそうなのは以下のようなものになった。

% 例えば { id0, 
%           { id1, { id2, nil, nil }, {id3, nil, nil} } }
%           { id4, { id5, nil, nil }, {id6, nil, nil} }
% というようなツリーがあった時に、nextPreOrder() などで辿るため、各ノードとの繋りを表現したい
% そこで以下のような、各ノードの子とその親の ID をまとめる。
% これは、リストの n 番目が idn のノードについての情報が入るようにする。

%           {NodeID, LeftChildID, RightChildID, ParentID}
TreeLink = [{id0, id1, id2, nil}, {id1, id2, id3, id0}, {id2, nil, nil, id1}, {id3, nil, nil, id1},
           {id4, id5, id6, id0}, {id5, nil, nil, id4}, {id6, nil, nil, id4}].

これを使えば実装できそうだと分かるまで結構時間を使ってしまった。明日以降に nextPre, nextIn, nextPostOrder 関数を実装してみる。