プログラマ専用SNS ミクプラ

C言語/Linux/gcc
初心者です。

タイトル通り、再帰呼び出しの2分探索木を作ってまして、以下のようなところまで作ったのですが、「12 15 18 28 31」と入力しても実行結果が１つしか出ません。
おそらくaddtreeの戻り値がおかしいのかと思われますが、他にも違うところがあると思います。
なにをどのようにすればよいでしょうか。
教えてください。

コード:


#include<stdio.h>
#include<stdlib.h>

struct tnode{
  int value;
  struct tnode *left;
  struct tnode *right;
};

struct tnode *addtree(struct tnode *p, int d);
void treeprint(struct tnode *);
void freetree(struct tnode *p);

int main(void)
{
  struct tnode *root;
  int digit;

  scanf("%d", &digit);
  root = (struct tnode *) malloc(sizeof(struct tnode));
  root->value = digit;
  root->left = root->right = NULL;

  while (scanf("%d", &digit) != EOF)
   root =  addtree(root, digit);

  printf("中間順出力：n");
  treeprint(root);
  putchar('\n');
  freetree(root);

  return 0;
}

struct tnode *addtree(struct tnode *p, int d)
{
  struct tnode *pp;

  if(d != p->value){
    pp = (struct tnode *) malloc(sizeof(struct tnode));
    pp->value = d;
    pp->left = pp->right = NULL;
  }
  else if(d == p->value)
    return;
  else if(d < p->value)
    addtree(p->left, d);
  else
    addtree(p->right, d);

  return pp->value;
}

void treeprint(struct tnode *p)
{
  if ( p != NULL) {
    treeprint(p->left);
    printf("%4d", p->value);
    treeprint(p->right);
  }
}
void freetree(struct tnode *p)
{
  if(p != NULL){
    freetree(p->left);
    freetree(p->right);
    free(p);
  }
}

may さんが書きました:おそらくaddtreeの戻り値がおかしいのかと思われますが、他にも違うところがあると思います。

新しく作ったノードが連結されていないのではないでしょうか。
あと戻り値は要らないと思います。

addtreeが間違っているのは、あきらかですが、その前に、
すでに格納されているvalueと同じ値の時はどうしたいですか？
「何もしない」でよろしいですか？

non さんが書きました:addtreeが間違っているのは、あきらかですが、その前に、
すでに格納されているvalueと同じ値の時はどうしたいですか？
「何もしない」でよろしいですか？

なにもしないでいいです。

なるべく原型を壊さないようにしました。

コード:

struct tnode *addtree(struct tnode *p, int d)
{
	if(p==NULL){
		p = (struct tnode *) malloc(sizeof(struct tnode));
		p->value = d;
		p->left = p->right = NULL;
	}
	else if(d == p->value)
		;
	else if(d < p->value)
		p->left=addtree(p->left, d);
	else 
		p->right=addtree(p->right, d);
	return p;
}

freetreeも怪しいなぁ。

>freetreeも怪しいなぁ。

合ってそうですね。

may さんが書きました:

コード:

  if(d != p->value){
    pp = (struct tnode *) malloc(sizeof(struct tnode));
    pp->value = d;
    pp->left = pp->right = NULL;
  }
  else if(d == p->value)
    return;

ここまでで、すべてのケースを網羅していることはおわかりですか？というのは、
d と p->value とは、等しくないか等しいかのどちらかに決まっているからです。よって、

may さんが書きました:
コード:
  else if(d < p->value)
    addtree(p->left, d);
  else
    addtree(p->right, d);

ここは通過しません。

プログラマ専用SNS ミクプラ

再帰呼び出しの2分探索木

再帰呼び出しの2分探索木

Re: 再帰呼び出しの2分探索木

Re: 再帰呼び出しの2分探索木

Re: 再帰呼び出しの2分探索木

Re: 再帰呼び出しの2分探索木

Re: 再帰呼び出しの2分探索木

Re: 再帰呼び出しの2分探索木