二分探索木の深さを出す

Question

前提・実現したいこと

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

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

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

該当のソースコード

+++++*+++++tree.c+++++*+++++
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 128
typedef enum {
	Term,Insert,Search,Print
} Menu;

typedef struct _bnode {
	char name[MAX_LEN];
	struct _bnode *left;
	struct _bnode *right;
	int count;
} BinNode;

BinNode *AllocNode(void)
{
	BinNode *tmp;

	tmp = (BinNode *)calloc(1,sizeof(BinNode));
	tmp->count = 1;
	return(tmp);
}

BinNode *ApndNode(BinNode *p, BinNode *w)
{
	int cond;
	if (p == NULL) {
		p = AllocNode();
		strcpy(p->name,w->name);
		p->left = p->right = NULL;
	} 
	else if((cond = strcmp(w->name,p->name))==0) {
		p->count++;
	}
	else if (cond < 0) p->left = ApndNode(p->left,w);
	else p->right = ApndNode(p->right,w);
	return p;
}

void SrchNode(BinNode *p, BinNode *w)
{
	int cond;
	if (p == NULL) 
		printf("%s is not registered\n",w->name);
	else if((cond = strcmp(w->name,p->name))==0) 
		printf("%s is registered\n",w->name);
	else if (cond < 0)
		SrchNode(p->left,w);
	else
		SrchNode(p->right,w);
}

void PrintTree(BinNode *p)
{
	if (p != NULL) {
		PrintTree(p->right);
		printf("%s(%d)\n",p->name,p->count);
		PrintTree(p->left);
	}
}

void FreeTree(BinNode *p) 
{
	if (p != NULL) {
		FreeTree(p->left);
		FreeTree(p->right);
		free(p);
	}
}

BinNode Read(char *message)
{
	BinNode temp;
	printf("Please Input name for %s:",message);
	scanf("%s",temp.name);
	return (temp);
}

Menu SelectMenu(void)
{
	int ch;
	do {
		printf("(1)Insert (2)Search (3) Print (0)Quit:");
		scanf("%d",&ch);
	} while(ch < Term||ch > Print);
	return ((Menu)ch);
}

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




}

int main(void)
{
	Menu menu;
	BinNode *root;

	int depth;

	// ルートノードを深さ0とするため
	depth = -1;

	root = NULL;
	
	do {
		BinNode x;
		switch (menu = SelectMenu()) {
			case Insert :x = Read("Insert");
				root = ApndNode(root,&x);break;
			case Search: x = Read("Search");
				SrchNode(root,&x); break;
			case Print: puts("----------------");
				PrintTree(root);
		}
	} while (menu != Term);
	printf("max_depth=%d\n",Depth(root,depth));
	FreeTree(root);
	return(0);
}
//

試したこと

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/ツールのバージョンなど）

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

Answer 1

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

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

Answer 2

int Depth(BinNode *p) :

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

こんだけ↑でよくね?

int Depth(BinNode *p) {
  if (p == NULL) {
    return 0;
  }
  int depthL = Depth(p->left);
  int depthR = Depth(p->right);
  return ( depthL >= depthR ) ? depthL+1 : depthR+1;
}

[追記] 別解

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

だったらコレ↓で:

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

Comments

[sk001016]

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

Answer 3

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

Comments

[sk001016]

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