２分探索木の高さを求めるプログラムの質問です。

２分探索木の高さを求めるプログラムを作成しているのですが、
下に書いたプログラムだと上手くいきません・・。

int compute_height(struct BST_Node *p){
int lh=0, rh=0, Max;
if(p==NULL){ return 0; }

lh=compute_height(p->left);
rh=compute_height(p->right);

if(lh > rh){ return Max=lh; }

else{ return Max=rh; }
}

どこがおかしいのでしょう。教えてください。
よろしくお願いします。

No.2 回答者： gerugugu84 回答日時： 2011/08/02 11:43

深さを加算していない。

ノードの終端は必ずNULLなので0が返り、
それをlh、rhに代入してるだけなので
いつまでたっても０のまま。

+1すればいけるとおもうよ。
lh=compute_height(p->left)+1;
rh=compute_height(p->right)+1;

この回答へのお礼

ご回答ありがとうございます！

考えが足りなかったようです（汗

無事お二人のおかげで上手くいけました。
親切に教えてくださってありがとうございます！！

お礼日時：2011/08/02 16:37

No.1 回答者： mtaka2 回答日時： 2011/08/02 11:28

あるノードの「高さ」を求めるには、「左右の子ノードの高さ(の高い方)」に、自身のノード分の1を足さないといけません。

あとは、変数Maxは使ってないので不要ですので、
---
if(lh > rh){ return Max=lh; }
else{ return Max=rh; }
---
この部分を
---
if(lh > rh){ return lh+1; }
else{ return rh+1; }
---
でいけるかと思います。

この回答へのお礼

ご回答ありがとうございます！

なるほど・・・言われてみれば（汗

Ｃ言語でいつもこういう感じなんです。
分かりやすいご回答ありがとうございました！

お礼日時：2011/08/02 16:35