みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

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

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

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; }
}

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

投稿日時 - 2011-08-02 10:46:26

QNo.6915723

困ってます

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(2)

ANo.2

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

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

投稿日時 - 2011-08-02 11:43:44

お礼

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

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

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

投稿日時 - 2011-08-02 16:37:17

ANo.1

あるノードの「高さ」を求めるには、「左右の子ノードの高さ(の高い方)」に、自身のノード分の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 11:28:45

お礼

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

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

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

投稿日時 - 2011-08-02 16:35:13

あなたにオススメの質問