ニ分木はどのように組みますか？

Program 提案 DKUT

http://d.hatena.ne.jp/bake_3572/20051216/p1
より。
木についての話題があった。いわいるiteration処理をどうするかについてであった。
http://d.hatena.ne.jp/tailliar/20051216#p1
にてその改善方法が語られていた。
なるほど。
私も木の処理には悩んだたちです。
ちなみにgoogle:dkutil_cのなるたけ最新版に入っているdkc2Tree.cという奴です。
確か、バグを出さないために一部で面倒事を避けるために再帰処理を使っていますが、個人的に再帰処理は嫌いなのです。*1
なぜなら･･･STACK OVERFLOWが怖いからです。
まぁ、滅多な事ではならないんですが、絶対にエラーのない安全なプログラムを美徳とする私は非再帰の方が好きなんです。
なのでmallocして取得した擬似スタックを使ったりしてiteration処理するのですが、これでもやっぱり木が深くなるほどメモリを使います。
なので、なるたけ深くならないような木が欲しい訳なのですよ。普通のニ分木の場合は最悪線型リストと同じ構造になってしまいますし･･･。
で、ムカーし昔？（いつごろだっけ？ワスレタ）に目を付けたのがAVL木でした。
AVL木とは？

すべての節において、左部分木と右部分木の高さの差が1以内に収まらなければならない。

とあります。なーる。
続く･･･。

*1:なので書き直したいです。