二分探索木のプログラム

質問

２分探索木のプログラムを作っているのですが、実行するとセグメテーション違反がでます。何が間違っているんでしょうか？

#include<stdlib.h>

struct node{
struct node *left,*right;
int datum;
};

struct bintree{
struct node *root;
};

/*空木を作成*/
void InitTree(struct bintree *p)
{
p->root=NULL;
}

/*木全体を削除*/
void ClearTree(struct bintree *p)
{
struct bintree *q,*r;

if(p->root!=NULL){
q->root=p->root->left;
ClearTree(q);
r->root=p->root->right;
ClearTree(r);
free(p->root);
}
}

/*第二引数で指定された値が木の節点のラベルに存在すれば、その節点へのポインタを返す。なければ、NULLを返す。*/
struct node *
SearchNode(struct bintree *p,int x)
{
struct bintree *q,*r;
struct node *a=p->root;
int cond=x-(a->datum);

if(a==NULL)
return NULL;
else if(cond==0)
return a;
else if(cond<0){
q->root=p->root->left;
SearchNode(q,x);
}
else{
r->root=p->root->right;
SearchNode(r,x);
}
}

/*第二引数で指定された値が木の節点のラベルに存在すれば、NULLを返す。なければ、追加して、新たに作成された節点へのポインタを返す。*/
struct node *
InsertNode(struct bintree *p,int x)
{
struct bintree *q,*r;
struct node *a=p->root;
int cond=x-(a->datum);

if(a==NULL){
a=(struct node *)malloc(sizeof(struct node));
a->datum=x;
a->left=a->right=NULL;
return a;
}
else if(cond==0)
return NULL;
else if(cond<0){
q->root=p->root->left;
a->left=InsertNode(q,x);
}
else{
r->root=p->root->right;
a->right=InsertNode(r,x);
}
}

int main()
{

struct bintree *p;
struct node *a;

InitTree(p);
a=InsertNode(p,5);
InsertNode(p,3);
InsertNode(p,0);
InsertNode(p,10);

SearchNode(p,5);
ClearTree(p);
return 0;
}

回答No.3

noname#119918

プログラム例です。参考までに。
ラクに書くために再帰を多用しています。
Search,Insert共に、ループで済ませることもできるので、考えてみてください。
前の方も書いておられましたが、SegmentationFault等のエラーは、
デバッガがあると格段に追い易くなります。
これからC言語と付き合っていくならば、
早い段階で使えるようになっておくと良いと思います。

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

typedef struct node{
struct node *left;
struct node *right;
int datum;
} snode; // 別名宣言

typedef struct bintree{
struct node *root;
} stree; // 別名宣言

// 節の領域を確保してポインタを返す
snode* CreateNode(void)
{
snode* n = (snode*)malloc(sizeof(snode));
n->left = NULL;
n->right = NULL;
n->datum = -1;
return n;
}

// 木の領域を確保してポインタを返す
stree* CreateTree(void)
{
stree* t = (stree*)malloc(sizeof(stree));
t->root = NULL;
return t;
}

// 再帰的に節を解放
void DeleteNode(snode* n)
{
if(n->left != NULL) // 左枝があればそれを解放
{
DeleteNode(n->left);
n->left = NULL;
}
if(n->right != NULL) // 右枝があればそれを解放
{
DeleteNode(n->right);
n->right = NULL;
}
free(n); // 自分自身を解放
}

// 木全体を解放
void DeleteTree(stree* t)
{
DeleteNode(t->root);
free(t);
}

// 節に値を挿入
void InsertToNode(snode* n , int x)
{
if(x >= n->datum)
{
if(n->right == NULL)
{
n->right = CreateNode();
n->right->datum = x;
}
else
{
InsertToNode(n->right , x);
}
}
else
{
if(n->left == NULL)
{
n->left = CreateNode();
n->left->datum = x;
}
else
{
InsertToNode(n->left , x);
}
}
}

// 木に値を挿入
void InsertToTree(stree* t , int x)
{
if(t->root == NULL)
{
t->root = CreateNode();
t->root->datum = x;
}
else
{
InsertToNode(t->root , x);
}
}

// 節から値を探索
// 発見できた場合1,できなかった場合0を返す
int SearchFromNode(snode* n , int x)
{
if(n == NULL)
{
return 0;
}
else if(x == n->datum)
{
return 1;
}
else if(x > n->datum)
{
return SearchFromNode(n->right , x);
}
else
{
return SearchFromNode(n->left , x);
}
}

// 木から値を探索
// 発見できた場合1,できなかった場合0を返す
int SearchFromTree(stree* t , int x)
{
if(t->root == NULL)
{
return 0;
}
else
{
return SearchFromNode(t->root , x);
}
}

// 節をたどり表示を行う
void DispNode(snode* n)
{
if(n == NULL)
{
return;
}
else
{
printf("%d " , n->datum);
if(n->left != NULL)
{
DispNode(n->left);
}
if(n->right != NULL)
{
DispNode(n->right);
}
}
}

// 木をたどり表示を行う
void DispTree(stree* t)
{
if(t->root != NULL)
{
DispNode(t->root);
}
printf("\n");
}

int main(void)
{
stree* t = CreateTree();
InsertToTree(t , 5);
InsertToTree(t , 3);
InsertToTree(t , 0);
InsertToTree(t , 10);
DispTree(t);
printf("%d\n" , SearchFromTree(t , 0));
printf("%d\n" , SearchFromTree(t , 10));
printf("%d\n" , SearchFromTree(t , 6));
DeleteTree(t);
return 0;
}

回答No.2

E-Yu

ポインタに関してまだ理解が足りないという印象を受けました。
とりあえず、

int main()
{
　　…
　　InitTree(p);
　　…
}

に渡すものが間違っています。まずはそこから考えて見ましょう。
結構バグが多そうなんで、完成まで時間がかかるかもしれませんが、ひとつずつ潰していけばなんとかなります。
頑張ってください。

回答No.1

sakusaker7

デバッガ使えばどこで落ちてるかはすぐわかるだろうし、
場所が特定できれば原因も推測できません?

とりあえずぱっとみたところ、

/*空木を作成*/
void InitTree(struct bintree *p)
{
p->root=NULL;
}

という関数に対して

struct bintree *p;
struct node *a;

InitTree(p);

という呼び出しをしちゃいけません。
#たぶん他の関数も同じ勘違いしてそう。