二分探索木のheight(高さ?)を見つけるアルゴリズム

Binary Search Tree(=二分探索木)のheight(高さ?)を見つけるメソッドを作りたいのですが、
そのアルゴリズムが頭にうまく浮かびません。

まず思いついたのは一つ一つのNode(=ノード)をそれぞれのLeaf(=リーフ、葉?)まで辿っていって
それらのheightを全部記憶させておいて後で比較するという…最も原始的な方法です。
しかし、Treeの大きさも未知なので用意する変数の数も未知になって
どう考えても不適当でしょう(当たり前か(^^ゞ)。
Recursion(=再帰)を使えばいいのでしょうか?
そうだとしてもどうすればいいのか…。
アルゴリズムがパッと浮かぶ方、どうか教えて下さい。

No.2 ベストアンサー 回答者： ranx 回答日時： 2003/11/20 10:39

再帰を使うとすれば、二分木ですから、直下の二つだけ比較すれば良いです。

大きい方を採って、自分自身の分１をプラスして上に返したら、上は上で判断してくれます。

この回答へのお礼

出来ました!
どのくらいの出来なのか自分でもよく分かりませんが一応動くのでよしとします。
問題は組んだ本人がいまいち動作を理解してないことですね(^_^.)
ありがとうございました!

public int height() {
return height(root, 0);
}
public int height(IntBSTNode p, int h) {
if (p != null && p.right != null && p.left != null) {
if (p.left.key < p.right.key)
return height(p.right, h+1);
else
return height(p.left, h+1);
}
return h;
}

お礼日時：2003/11/20 16:50

No.1 回答者： liar_adan 回答日時： 2003/11/20 08:06

全部のheightを記憶しなくても、

最大の一個だけ記憶しておいて、
それより大きいのが見つかったときだけ書き換えたらいいじゃないですか。

「現在の高さ(深さ)」が調べにくければ、
treeを操作するとき、rootの0から始まって、
葉の方に行けば+1、根の方に戻れば-1とすればいいでしょう。

この回答へのお礼

そうですね、最大の一個だけ記憶しておけばよかったのですね。
それでPreorder Traversalメソッドを修正して組んでみました。
…すみません、完結できませんでした。
葉の方に行けば+1、は出来たのですが、
根の方に戻れば-1、は戻るタイミングが分かりませんでした。
Stackを使っているのでPopのすぐ後だと思ったのですが…。
BreadthFirstとか使えばよかったのかも…すみません、脳が足りませんでした。

public int iterativePreorderHeight() {
int max = 0, h = 0;
IntBSTNode p = root;
Stack travStack = new Stack();
if (p != null) {
travStack.push(p);
while (!travStack.isEmpty()) {
p = (IntBSTNode) travStack.pop();
// h--; この位置だとhが1以上の値になりません
p.visit();
if (p.right != null) {
travStack.push(p.right);
h++;
}
if (p.left != null) { // left child pushed after right
travStack.push(p.left); // to be on the top of the stack;
h++;
}
if (h > max)
max = h;
}
}
return max;
}

それと前回、回答して頂いた二項係数の再帰的計算メソッドを一応載せておきますね
(お礼を差し上げた10分後に完成しました)。

//biRec() method: computes the binomial coeffient recursively
public int biRec(int n, int k) {
if (k == 0 || k == n)
return 1;
else
return biRec(n-1,k-1) + biRec(n-1,k);
}

もっともっと勉強します(特に数学)。
重ね重ね、ありがとうございました!

お礼日時：2003/11/20 16:49