平成18年度秋季ソフトウェア開発午後問5

平成18年度秋季ソフトウェア開発技術者試験(SW)の午後問題5は、

に関する問題でした。2分探索木については、平成27年度秋季応用情報午後問3でも出題されており、その際はRubyで実行していますので、今回はC言語で作成してみました。

問題文中の図1に対して、25, 40, 80, 45, 52 を追加して実行してみます。

$ gcc h18a_sw_pm5.c && ./a.out > tree.dot && dot -Tjpeg tree.dot -o output.jpg

f:id:rahaema:20190416211305p:plain

main関数のdot_print関数呼び出しの前にノードの削除機能を持つdelete関数を追加して実行してみます。

  root = delete(64, root);      /* 子を持たないケース */
  root = delete(78, root);      /* 右の子のみ持つケース */
  root = delete(20, root);      /* 左右の子を持つケース */

削除したいノードが

のときは、単純ですが、左右の子を持つケースの場合は少し複雑になりますね。20を削除しようとすると、20の左部分木の中での最大値15を20の位置に持ってくる事になります。

f:id:rahaema:20190416214426p:plain

次にmain関数内のdot_print関数を

preorder_print_node(root);

と置き換えて実行してみます。preorder_print_node関数は2分探索木を行きがけ順でなぞりながらノードの値を出力するものです。ノードの値が昇順に出力されていることが分かります。

$ gcc h18a_sw_pm5.c && ./a.out
2
8
15
25
36
40
44
45
50
52
53
80

Mae向きなブログ