プロが教えるわが家の防犯対策術！

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

解決済

  • 質問者：kagari321
  • 質問日時：
  • 回答数：8件

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の条件を変えればいいのかと思い、いろいろ試してみたのですが、
左部分木には左側にしか葉がなく、右部分木には右にしか葉がないようなものしかできませんでした

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

通報する

この質問への回答は締め切られました。

質問の本文を隠す

A 回答 (8件)

No.7ベストアンサー

  • 回答者： hrsmmhr
  • 回答日時：

ゴミは解りません



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

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

そうですか…

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

通報する
お礼日時：2011/07/10 15:00

No.8

  • 回答者： hrsmmhr
  • 回答日時：

ゴミの件ですが、


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

ありがとうございます

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

通報する
お礼日時：2011/07/10 20:57

No.6

  • 回答者： hrsmmhr
  • 回答日時：

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



*->p->keyは見たことがないです
そこなら
&((*p)->left)
ではダメですか？
    • good
    • 0
    • 件
通報する
この回答へのお礼

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

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

通報する
お礼日時：2011/07/10 11:31

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;
}
    • good
    • 0
    • 件
通報する
この回答へのお礼

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

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

通報する
お礼日時：2011/07/10 09:54

No.4

  • 回答者： hrsmmhr
  • 回答日時：

No3さんの回答で気が点きましたが


私の
*p=x;
を
*p=createNode(x);
ではダメでしょうか？

その場合だとbtreeはループで毎回createNodeするべきではないです
    • good
    • 0
    • 件
通報する
この回答へのお礼

コンパイルがうまくできませんでした
一応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;
}

通報する
お礼日時：2011/07/10 01:49

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;
}
    • good
    • 0
    • 件
通報する
この回答へのお礼

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

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

通報する
お礼日時：2011/07/10 00:16

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;
}
    • good
    • 0
    • 件
通報する
この回答へのお礼

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

ありがとうございます

通報する
お礼日時：2011/07/10 00:14

No.1

  • 回答者： hrsmmhr
  • 回答日時：

プログラムよく判らないのですが


rootがまず必要なこと（btreeのようですが、ループで書き換える必要がないです）、
xをpのleftかrightにリンクする箇所がない気がします
InsertNodeで戻り値が必要なくて、引数にダブルポインタ**pを使って
*p==NULLのときに*p=x;とすれば
できるのかも…
    • good
    • 0
    • 件
通報する
この回答へのお礼

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

でもできませんでした…

通報する
お礼日時：2011/07/09 23:32

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう！

Q質問する（無料）

関連するカテゴリからQ&Aを探す

ページトップページトップ

Q質問する（無料）

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

おすすめ情報