c言語で2分探索木のを2分木に変えたい

質問

2分木のプログラムを書いているのですが、ある数列を2分木にしたいのです。
2分探索木のプログラムを参考に書いていて、その一部が

typedef int BSTREE_K_TYPE;
typedef int BSTREE_V_TYPE;

struct bsnode {
BSTREE_K_TYPE key;
BSTREE_V_TYPE value;
struct bsnode *left;
struct bsnode *right;
};
typedef struct bsnode BSTREE_NODE;

int gShortFormat = 1;

void error(char *msg){
fflush(stdout);
fprintf(stderr, "%s\n", msg);
exit(1);
}

BSTREE_NODE *createNode(BSTREE_K_TYPE x){
BSTREE_NODE *new;

new = malloc(sizeof(BSTREE_NODE));
if(new == NULL)
error("createNode:　メモがありません");
new->key = x;
new->value = 0;
new->left = NULL;
new->right = NULL;
return new;
}
BSTREE_NODE *insertNode(BSTREE_NODE *p, BSTREE_K_TYPE x){
if (p == NULL){
} else if (p->key == x){
error("insertNode: 指定キーのノードが含まれています");
} else if (p->key > x){
p->left = insertNode(p->left, x);
} else {
p->right = insertNode(p->right, x);
}
return p;
}

BSTREE_NODE *inputBSTree(BSTREE_NODE *btree, char *str[], int len, int *end){
BSTREE_K_TYPE x;
int i, n = 0;

for(i = 0; i < len; i++){
if(!strcmp(str[i], "--")) break;
x = atoi(str[i]);
if(btree == NULL)
btree = createNode(x);
else
btree = insertNode(btree, x);
n++;
}
*end = n;
return btree;
}

このinsertNodeのifの条件を変えればいいのかと思い、いろいろ試してみたのですが、
左部分木には左側にしか葉がなく、右部分木には右にしか葉がないようなものしかできませんでした

もう何時間も悩んだのですが自分の知識では手づまりです
どうかよろしくお願いします。

回答No.7

hrsmmhr · ベストアンサー

ゴミは解りません

木は、入力が昇順ならそうなって正解です。

つまり入力によらない一意の結果はでません
一意の結果にするには
例えば、上位ビットから0/1で分けるとかすればできるでしょう
ただ枝と葉を分けないといけないでしょう

お礼

そうですか…

ありがとうございました！

回答No.8

hrsmmhr

ゴミの件ですが、
携帯で見ていたので気が付きませんでしたが
btreeをcreateNodeするときに使うxが初期化されていないですのでゴミが入ります
xを初期化するか、btree->keyは意味がないので表示しないようにするかだと思います

お礼

ありがとうございます

ゴミはうまく消すことができました

回答No.6

hrsmmhr

どこのどういうエラーでしょうか？

*->p->keyは見たことがないです
そこなら
&((*p)->left)
ではダメですか？

お礼

そのように変えたところコンパイルはうまくいきました。

しかし実行すると
a.exe 1 2 3 5 6 7
入力データ　[ 4235448 [ 1 _ [ 2 _ [ 3 _ [ 5 _ [ 6 _ 7 ] ] ] ] ] _ ]
と最初に関係ない値が入り、さらに右側にしか葉がない木になってしまったようです。

回答No.5

hrsmmhr

二つの関数を書き換えてみました。参考にしてみてください。

void insertNode(BSTREE_NODE **p, BSTREE_K_TYPE x){
if (*p == NULL) *p=createNode(x);
else if (*p->key == x) error("insertNode: 指定キーのノードが含まれています");
else if (*p->key > x) insertNode(&(*p->left), x);
else insertNode(&(*p->right), x);}
}

BSTREE_NODE *inputBSTree(BSTREE_NODE *btree, char *str[], int len, int *end){
BSTREE_K_TYPE x;
int i;

if(btree == NULL) btree = createNode(x);
for(i = 0; i < len; i++){
if(!strcmp(str[i], "--")) break;
x = atoi(str[i]);
insertNode(&btree, x);
}
*end = i;
return btree;
}

お礼

insertNodeでコンパイルエラーがでたので

void insertNode(BSTREE_NODE **p, BSTREE_K_TYPE x){
if (*p == NULL) {*p=createNode(x);
}else if (*->p->key == x) {error("insertNode: 指定キーのノードが含まれています");
}else if (*->p->key > x) {insertNode(&(*->p->left), x);
}else {insertNode(&(*->p->right), x);
}
}

と書き換えたのですが、まだエラーが出てしまいます…

回答No.4

hrsmmhr

No3さんの回答で気が点きましたが
私の
*p=x;
を
*p=createNode(x);
ではダメでしょうか？

その場合だとbtreeはループで毎回createNodeするべきではないです

お礼

コンパイルがうまくできませんでした
一応2分探索木のプログラムとしては下のような形です。
これだと2分探索木なので、ただの2分木を作りたいのです。
例えば 1 2 3 4 5 6 のとき
　　　　1
　　　／　＼
　　2　　　　　3
　／　＼　　／
4　　　　5　6

としたいです。

#include <stdio.h>
#include <stdlib.h>
typedef int BSTREE_K_TYPE;
typedef int BSTREE_V_TYPE;

struct bsnode {
BSTREE_K_TYPE key;
BSTREE_V_TYPE value;
struct bsnode *left;
struct bsnode *right;
};
typedef struct bsnode BSTREE_NODE;

void error(char *msg);
void destroyBSTree(BSTREE_NODE *p);
BSTREE_NODE *insertNode(BSTREE_NODE *p,BSTREE_K_TYPE x);
int isLeafNode(BSTREE_NODE *p);
void printBSTree(BSTREE_NODE *p, int tabs, int brief);
BSTREE_NODE *inputBSTree(BSTREE_NODE *btree, char *str[], int len, int *end);

int main(int argc, char *argv[]){
BSTREE_NODE *bstree = NULL;
BSTREE_NODE *result;
BSTREE_K_TYPE x;
int n1;

bstree = inputBSTree(bstree, &argv[1], argc -1, &n1);
printf("入力データ　"); printBSTree(bstree, 0, 1);

destroyBSTree(bstree);
return 0;
}

int gShortFormat = 1;

void error(char *msg){
fflush(stdout);
fprintf(stderr, "%s\n", msg);
exit(1);
}

BSTREE_NODE *createNode(BSTREE_K_TYPE x){
BSTREE_NODE *new;

new = malloc(sizeof(BSTREE_NODE));
if(new == NULL)
error("createNode:　メモがありません");
new->key = x;
new->value = 0;
new->left = NULL;
new->right = NULL;
return new;
}

void destroyNode(BSTREE_NODE *del){
memset(del, 0, sizeof(BSTREE_NODE));
free(del);
}

void destroyBSTree(BSTREE_NODE *p){
if(p == NULL)
return;

destroyBSTree(p->left);
destroyBSTree(p->right);
destroyNode(p);
}

BSTREE_NODE *insertNode(BSTREE_NODE *p, BSTREE_K_TYPE x){
if (p == NULL){
p = createNode(x);
} else if (p->key == x){
error("insertNode: 指定キーのノードが含まれています");
} else if (p->key > x){
p->left = insertNode(p->left, x);
} else {
p->right = insertNode(p->right, x);
}
return p;
}

int isLeafNode(BSTREE_NODE *p){
return(p->left == NULL) && (p->right == NULL);
}

void printSubBSTree(BSTREE_NODE *p){
if(p == NULL){
printf("_");
return;
}
if(gShortFormat !=0 && isLeafNode(p)){
printf("%d", p->key);
}else{
printf("[ ");
printf("%d ", p->key);
printSubBSTree(p->left);
printf(" ");
printSubBSTree(p->right);
printf(" ]");
}
}

void printBSTree(BSTREE_NODE *p, int tabs, int brief){
int i;

gShortFormat = brief;
for(i = 0; i < tabs; i++)
printf("\t");
printSubBSTree(p);
printf("\n"); fflush(stdout);
}

BSTREE_NODE *inputBSTree(BSTREE_NODE *btree, char *str[], int len, int *end){
BSTREE_K_TYPE x;
int i, n = 0;

for(i = 0; i < len; i++){
if(!strcmp(str[i], "--")) break;
x = atoi(str[i]);
if(btree == NULL)
btree = createNode(x);
else
btree = insertNode(btree, x);
n++;
}
*end = n;
return btree;
}

回答No.3

KAZUMI2003

No.2の方の回答に、さらに、次の部分も、こうしないとだめじゃないかな？
BSTREE_NODE *inputBSTree(BSTREE_NODE *btree, char *str[], int len, int *end){
BSTREE_K_TYPE x;
int i, n = 0;

for(i = 0; i < len; i++){
if(!strcmp(str[i], "--")) break;
x = atoi(str[i]);
if(btree == NULL)
btree = createNode(x);
else
/*btree =*/ insertNode(btree, x); //←ここね。
n++;
}
*end = n;
return btree;
}

お礼

回答ありがとうございます

それで試してみましたが、2分木ではなくやはり2分探索木になってしまいました…

回答No.2

jjon-com

手元にCコンパイラがないのでざっと目視でコードを追ってみただけなのですが，
insertNode 内の最初のif分岐の中身の１行が抜けていますよね。

BSTREE_NODE *insertNode(BSTREE_NODE *p, BSTREE_K_TYPE x){
if (p == NULL){
p = createNode(x);
} else if (p->key == x){
error("insertNode: 指定キーのノードが含まれています");
} else if (p->key > x){
p->left = insertNode(p->left, x);
} else {
p->right = insertNode(p->right, x);
}
return p;
}

お礼

投稿するときに間違えて消してしまったようです

ありがとうございます

回答No.1

hrsmmhr

プログラムよく判らないのですが
rootがまず必要なこと（btreeのようですが、ループで書き換える必要がないです）、
xをpのleftかrightにリンクする箇所がない気がします
InsertNodeで戻り値が必要なくて、引数にダブルポインタ**pを使って
*p==NULLのときに*p=x;とすれば
できるのかも…

お礼

回答ありがとうございます

でもできませんでした…