なぜ通りがけをすると昇順に整列されるのか？

2分探索木で通りがけをすると中身が昇順に整列されて出てくる、それは覚えたのですが、なぜそうなるかがわかりません。
試験に「整列されて出ることを帰納法で証明せよ」という問題が出ることを予告されているのですが、なぜかが理論的に理解できていないので出来る気がしません。
どなたか理論をお教えください。

No.1 回答者： asuncion 回答日時： 2008/02/16 23:42

二分木のある節と、その節に付随する左部分木、右部分木のデータの間には、

左部分木のデータ＜節のデータ＜右部分木のデータ
という大小関係があります。

また、二分木を通りがけに探索する順序は、
左部分木→節→右部分木です。

これらの情報を使えば、くだんの証明ができるのではないかと思います。

この回答へのお礼

ありがとうございました。頑張ってみます。

お礼日時：2008/02/17 18:09

No.2 ベストアンサー 回答者： kabaokaba 回答日時： 2008/02/17 10:02

とにかく，実際に二分木を紙にかいて

「自分で手を使って」通りがけを実行してください．
そうすれば仕組みが体得できます．

理論的な証明は・・・トリッキーといえばそうですが
大して難しくありませんが，数学的帰納法の「本質」を
理解していないと厳しいかもしれません
受験数学の公式的な理解だとつらいかも．

証明の手順こんな感じ．
ここで，i番目に得られる値をA(i)と表記します．

STEP 1
A(1)は最小の値である
STEP 2
A(i)<A(i+1)

STEP 2まで示されれば
実際は「昇順」になる，すなわち
A(i)<A(k)<A(i+1)となるようなノードがないことも
自動的に示されます．

なお，細かいことは自分で考えてください．
二分木といっても微妙な定義はそれぞれ違うことがありますので．
厳密なことをいえば
「通りがけ」で「すべてのノードを辿れる」ことも
証明すべきことですが，
まあこれはスルーしてもいいか，。証明済みとしてもよいのでしょう．

この回答へのお礼

ありがとうございました。参考に頑張ってみます。

お礼日時：2008/02/17 18:12