tree traversal

木の全てのノードを１回ずつ取り上げる処理を、全ノードの数え上げ enumeration とか 木の走査 traversal あるいは walk といいます。全部のノードのデータを順に１回ずつ処理することです。深さ優先と幅優先があります。

深さ優先 depth-first
右図のように、根から葉に向かって順にすすみ、葉に届いたら親に戻って隣の子へ、終わったら、親、その親と戻りその子へとたどります。
各ノードは、下に下りる時、隣の子に行く時、上に戻る時の計３回通るのですが、いつそのノードのデータを処理するかで次の３種があります。
- 行きがけ順 pre-order
  最初にノードを訪問した際にそのノードの処理を行います。
  右図の例で、ＡＢＤＨＥＩＪＣＦＧの順に処理することをいいます。
- 通りがかり順 in-order
  左部分木の処理が終わり、右部分木の処理をする前に自ノードの処理を行います。
  ＨＤＢＩＥＪＡＦＣＧの順になります。
- 帰りがけ順 post-order
  子どもの処理が終わり親に戻る直前に、自ノードの処理をします。
  ＨＤＩＪＥＢＦＧＣＡの順です。
幅優先 breadth first
根に近いノードから順にたどる方法です。
右図でいえば、ＡＢＣＤＥＦＧＨＩＪＫの順にノードの処理をします。

２分木を深さ優先で走査するアルゴリズムは次のようになります。

２分探索木を通りがかり順に歩くと、ノードの値を昇順に取り出すことができます。