締切済み

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

  • 困ってます
  • 質問No.6915723
  • 閲覧数3097
  • ありがとう数2
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 81% (54/66)

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

どこがおかしいのでしょう。教えてください。
よろしくお願いします。
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全2件)

  • 回答No.2

ベストアンサー率 37% (29/78)

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

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

お礼率 81% (54/66)

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

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

無事お二人のおかげで上手くいけました。
親切に教えてくださってありがとうございます!!
投稿日時 - 2011-08-02 16:37:17
OKWAVE 20th Be MORE ありがとうをカタチに
  • 回答No.1

ベストアンサー率 73% (867/1179)

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

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

お礼率 81% (54/66)

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

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

C言語でいつもこういう感じなんです。
分かりやすいご回答ありがとうございました!
投稿日時 - 2011-08-02 16:35:13
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する

特集


より良い社会へ。感謝経済プロジェクト始動

ピックアップ

ページ先頭へ