<c言語>二分木を実現したい

Question

一度入力された数字は受け付けず、昇順に出力する二分木を作りたい

現在のプログラムでは、一度入力された数字は受け付けないが、新たに要素を入力しようとするとコアダンプし
昇順に表示できないようになっています。
また、3種類以上の要素が入力できないようになっています。
これらを解決したいです、よろしくお願いいたします。

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

$ ./a
input = 3
[ 3 ]
input = 5
[ 3 5 ]
input = 5
[ 3 5 ]
input = 3
[ 3 5 ]
input = 4
Segmentation fault (コアダンプ)

$ ./a
input = 3
[ 3 ]
input = 4
[ 3 4 ]
input = 5
Segmentation fault (コアダンプ)

該当のソースコード

//変更してもよいコード
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include "tree.h"

static tree_node_t* create_node(int val);

int count = 0;

static tree_node_t* create_node(int val)
/* 値 val を保持する新しい節点を作成し, その節点へのポインタを返す */
{
  tree_node_t *new_node;
  new_node = (tree_node_t*) malloc(sizeof(tree_node_t));
  if (new_node == NULL) {
    fprintf(stderr, "節点の割当てに失敗しました\n");
    exit(1);
  }
  new_node->data = val;
  new_node->left = NULL;
  new_node->right = NULL;
	count++;
  return new_node;
}


tree_node_t* tree_insert_uniq(tree_node_t *n, int val)
/* n を根とする二分木に val (の節点) を挿入する */
{
  /* val と同じ値を持つ節点が存在すれば挿入しないようにせよ. */
	tree_node_t *p = n;
	int i = 0;

	while(i<log(count)/log(2))
	{
		
		if(p->data == val)
		{

			return n;
		}
		else if(p->data > val)
		{
			p = n->left;
		}
		else if(p->data < val)
		{
			p = n->right;
		}
		i++;
	}
  if (n==NULL) {
    n = create_node(val);
  }
  else if (val < n->data) {
    n->left = tree_insert_uniq(n->left, val);
  }
  else {
    n->right = tree_insert_uniq(n->right, val);
  }
  return n;
}



void tree_print(tree_node_t *n)
/* 二分木の内容を表示する */
{
  if (n!=NULL) {
    /* 値の昇順に表示されるようにせよ */
    printf(" %d", n->data);
    tree_print(n->left);
    tree_print(n->right);
  }
}



void tree_delete(tree_node_t *n)
/* 二分木のデータを解放する */
{
  if (n!=NULL) {
    tree_delete(n->left);
    tree_delete(n->right);
    free(n);
  }
}

//main関数
//変更が認められていないコード
#include <stdio.h>
#include "tree.h"

int main (void)
{
  tree_node_t *root = NULL;

  for (;;) {
    int data;
    fprintf(stderr, "input = ");
    if (scanf("%d", &data)==EOF) { break; }
    root = tree_insert_uniq(root, data);
    printf("[");
    tree_print(root);
    printf(" ]\n");
  }

  tree_delete(root); 
  return 0;
}

補足情報

このほかにもヘッダファイルtree.hが存在します。
ヘッダファイルとメイン関数の変更は認められていません。

Answer 1

terateil は課題やデバッグの依頼場所では無いと思います。せめてどこで止まっているかは調べられては如何でしょう…。

while ループは削除し、n->right = ～ の直前の else にも ( n->left = ～ の直前と同じように) if ～ を入れてはどうでしょうか。(不等号は勿論逆です。念のため。)

表示のほうもこれでは仕様通りには並ばないでしょう。

Answer 2

3、4、5 と 3つの数を入力すると Segmentation fault になるのなら、
3 を入力して各変数の値がどうなるのか、
4 を入力して各変数の値がどうなるのか、
5 を入力して各変数の値がどうなるのか、
を調べればすぐにわかるはずです。
なぜコードを追跡して、変数の値の変化を確認しないのですか？

while(i<log(count)/log(2)) について見てみましょう。
変数 count は、ノードが 1個生成される時に 1増えます。
3 を入力した時、count は　0 なので log(0) は -無限大。
i = 0 なので、whileループに入りません。
4 を入力した時、count は　1 なので log(1) は 0。
i = 0 なので、whileループに入りません。
5 を入力した時、count は　2 なので log(2)/log(2) は 1。
0 より大きいので、whileループに入ります。
p->data = 3、val = 5 なので、p = p->right; を実行します。
p->data = 4、val = 5 なので、p = p->right; を実行します。
.data が 4 のノードの .left も .right も NULL ですから
p は NULL になります。
p->data を参照して、 Segmentation fault になります。

while(i<log(count)/log(2))
この whileループは何のためにあるのでしょうか？
ループを回っても count の値は変わりませんから、無限ループです。
val は新しい値なので p->data と一致することもありません。

tree_insert_uniq は次のように書けばよいことが理解できますか？

tree_node_t* tree_insert_uniq(tree_node_t *n, int val)
{
	if (n == NULL)
		n = create_node(val);
	else if (val < n->data)
		n->left = tree_insert_uniq(n->left, val);
	else if (val > n->data)
		n->right = tree_insert_uniq(n->right, val);
	return n;
}

次に、tree_print です。
ノードの値を表示した後で、その値より小さい値を持つ p->left を表示して
昇順になるわけがありません。
なぜ p->left、p->data、p->right の順に表示していないのですか？

Answer 3

以下に、「再帰を用いる場合」と「再帰を用いない場合」を示します

#####「再帰を用いない場合」

tree_node_t* 
tree_insert_uniq(tree_node_t *n, int val)
{
tree_node_t *p = n;
int i = 0;

if(p==NULL)
return p;

while(1)
{
if(val < p->data) {

if(p->left == NULL) {
p->left = create_node(val);
} else {
p = p->left
}

} else if(val >p->data) {
if(p->right == NULL) {
p->right = create_node(val);
} else {
p = p->right;
}

} else {
printf(“すでに存在しています“);
return n;
}

}

#####「再帰を用いる場合」

tree_node_t* tree_insert_uniq(tree_node_t *n, int val)
{

if(n==NULL) {
n = create_node(val);
}
else if(val < n->data) {
n->left = tree_insert_uniq(n->left, val);
}
else if(val > n->data) {
n->right = tree_insert_uniq(n->right, val);
}

return n;
}

のように
p変数と、
while(i<log(count)/log(2)) { 
の部分が不必要かと思われます。

昇順に並べるのは、別の関数を容易し、その関数内でヒープソートを行えば実現できると思います。

Comments

[jimbe]

> nは常に木の根(root)を表すノードなので

再帰で left や right が渡されてますので n が root なのは最初だけではないでしょうか。

[Egg-Man]

確かに、おっしゃる通りです。

修正文を、回答欄に追記しました。

[jimbe]

>「再帰を用いない場合」

※コードをコピペするとコンパイルエラーになります。
main からの最初の tree_insert_uniq 呼び出しは root(=パラメータn) が NULL ですので、 if(val < p->data) { で止まりませんか？

>「再帰を用いる場合」

val == n->data の場合でも else が実行されませんか？

>昇順に並べるのは、 ～

並ぶように二分木を作っているものと思います。

[Egg-Man]

なるほどです！
修正を加えました。
有難うございます！

[jimbe]

質問者さんから反応が無いので方向が変わってしまいますが^^;

「再帰を用いない場合」は本当にそれで良いのでしょうか。
実際に動かしてみたほうが良いと思うのですが・・・。