質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

3回答

913閲覧

二分探索木の深さを出す

sk001016

総合スコア0

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2021/01/20 10:23

前提・実現したいこと

二分探索の深さを導くメソッドで深さが0になってしまいます。

発生している問題・エラーメッセージ

以下のプログラムのDepthメソッドを変更し、二分探索木の深さを出したいが、 深さが0と返されてしまう。

該当のソースコード

C言語

1+++++*+++++tree.c+++++*+++++ 2#include <stdio.h> 3#include <stdlib.h> 4#include <string.h> 5 6#define MAX_LEN 128 7typedef enum { 8 Term,Insert,Search,Print 9} Menu; 10 11typedef struct _bnode { 12 char name[MAX_LEN]; 13 struct _bnode *left; 14 struct _bnode *right; 15 int count; 16} BinNode; 17 18BinNode *AllocNode(void) 19{ 20 BinNode *tmp; 21 22 tmp = (BinNode *)calloc(1,sizeof(BinNode)); 23 tmp->count = 1; 24 return(tmp); 25} 26 27BinNode *ApndNode(BinNode *p, BinNode *w) 28{ 29 int cond; 30 if (p == NULL) { 31 p = AllocNode(); 32 strcpy(p->name,w->name); 33 p->left = p->right = NULL; 34 } 35 else if((cond = strcmp(w->name,p->name))==0) { 36 p->count++; 37 } 38 else if (cond < 0) p->left = ApndNode(p->left,w); 39 else p->right = ApndNode(p->right,w); 40 return p; 41} 42 43void SrchNode(BinNode *p, BinNode *w) 44{ 45 int cond; 46 if (p == NULL) 47 printf("%s is not registered\n",w->name); 48 else if((cond = strcmp(w->name,p->name))==0) 49 printf("%s is registered\n",w->name); 50 else if (cond < 0) 51 SrchNode(p->left,w); 52 else 53 SrchNode(p->right,w); 54} 55 56void PrintTree(BinNode *p) 57{ 58 if (p != NULL) { 59 PrintTree(p->right); 60 printf("%s(%d)\n",p->name,p->count); 61 PrintTree(p->left); 62 } 63} 64 65void FreeTree(BinNode *p) 66{ 67 if (p != NULL) { 68 FreeTree(p->left); 69 FreeTree(p->right); 70 free(p); 71 } 72} 73 74BinNode Read(char *message) 75{ 76 BinNode temp; 77 printf("Please Input name for %s:",message); 78 scanf("%s",temp.name); 79 return (temp); 80} 81 82Menu SelectMenu(void) 83{ 84 int ch; 85 do { 86 printf("(1)Insert (2)Search (3) Print (0)Quit:"); 87 scanf("%d",&ch); 88 } while(ch < Term||ch > Print); 89 return ((Menu)ch); 90} 91 92int Depth(BinNode *p, int depth) 93{ 94// 95 96if(p != NULL) { 97int depthL; 98int depthR; 99depthL = Depth(p->left, depth++); 100depthR = Depth(p->right, depth++); 101 102return (depthL>=depthR) ? depthL : depthR; 103} 104 105 106 107 108} 109 110int main(void) 111{ 112 Menu menu; 113 BinNode *root; 114 115 int depth; 116 117 // ルートノードを深さ0とするため 118 depth = -1; 119 120 root = NULL; 121 122 do { 123 BinNode x; 124 switch (menu = SelectMenu()) { 125 case Insert :x = Read("Insert"); 126 root = ApndNode(root,&x);break; 127 case Search: x = Read("Search"); 128 SrchNode(root,&x); break; 129 case Print: puts("----------------"); 130 PrintTree(root); 131 } 132 } while (menu != Term); 133 printf("max_depth=%d\n",Depth(root,depth)); 134 FreeTree(root); 135 return(0); 136} 137//

試したこと

Depthメソッドを次のように変更したりもしました。(以下に記載)
int Depth(BinNode *p, int depth)
{
//

if(p != NULL) {
int depthL;
int depthR;
depthL = Depth(p->left, depth);
depthR = Depth(p->right, depth);

return (depthL>=depthR) ? depthL : depthR;
}

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

++ はいけません。
left の Depth は引数の depth の値で呼び出し、
right の Depth は 1つ増えた depth の値で呼び出しています。
+1 を使いましょう。

C

1int Depth(BinNode *p, int depth) 2{ 3 if (p == NULL) return depth; 4 int depthL = Depth(p->left, depth + 1); 5 int depthR = Depth(p->right, depth + 1); 6 return depthL >= depthR ? depthL : depthR; 7}

投稿2021/01/20 15:45

kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

int Depth(BinNode *p) :

  • p が null なら 0 を返す
  • p が null でないなら Depth(右)とDepth(左)の大きい方 + 1 を返す

こんだけ↑でよくね?

C

1int Depth(BinNode *p) { 2 if (p == NULL) { 3 return 0; 4 } 5 int depthL = Depth(p->left); 6 int depthR = Depth(p->right); 7 return ( depthL >= depthR ) ? depthL+1 : depthR+1; 8}

[追記] 別解

int Depth(BinNode *p, int depth)という部分は指定されており、そのように作ることができません。

だったらコレ↓で:

C

1int Depth(BinNode *p, int depth) { 2 if ( p == NULL ) { 3 return depth; 4 } 5 int depthL; 6 int depthR; 7 depthL = Depth(p->left, depth); 8 depthR = Depth(p->right, depth); 9 return (depthL>=depthR) ? depthL+1 : depthR+1; 10}

投稿2021/01/20 10:49

編集2021/01/20 15:06
episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

sk001016

2021/01/20 14:17

回答ありがとうございます。 ネットで調べたりしてそのような解法も見つけましたが、 int Depth(BinNode *p, int depth)という部分は指定されており、そのように作ることができません。
guest

0

関数 Depth に,引数pがNULLである場合のreturnが存在していないように見えます.

投稿2021/01/20 10:46

fana

総合スコア11632

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

sk001016

2021/01/20 14:18

回答ありがとうございます。 p==NULLの時のreturnも用意しましたが、うまくいきませんでした。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問