C言語 二分木探索

質問

今、int型の二分木にデータを追加する関数(引数は二分木へのポインタと追加する値、追加されたノードへのポインタを返す)をつくろうとしてます。
以前リストにデータを追加する関数をつくったのでそれを変更してつくろうとしているのですが途中までいってつまってしまいました。
つくりかたを教えてください。
よろしくお願いします！

struct BinaryTreeNode{

int data;
struct BinaryTreeNode *l_next;
struct BinaryTreeNode *r_next;
};

struct BinaryTree{

int node_num;
struct BinaryTreeNode *root;
};

BinaryTreeNode *BinaryTreeNodeAlloc(void)
{
BinaryTreeNode *node;
node = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
if (node == NULL) {
return (NULL);
}
node->l_next = NULL;
node->r_next = NULL;
return (node);
}

BinaryTreeNode *BinaryTreeDataAdd(BinaryTree *list, int x)
{
BinaryTreeNode *ptr;
BinaryTreeNode *prev;
BinaryTreeNode *new_node;

ptr = list->root;
prev = NULL;

while (ptr) { 　　　　　　←？？
if (ptr->data < x) {
prev = ptr;
ptr = ptr->next;
} else if (ptr->data == x) {
return (NULL);
} else {
new_node = BinaryTreeNodeAlloc();
if (new_node == NULL) {
exit (0); 　　　　　　　　　　　　　　　←？？
}
new_node->data = x;
new_node->next = ptr;
if (prev != NULL) {
prev->next = new_node;
} else {
list->head = new_node;
}
list->node_num++;
return (new_node);
}
}

new_node = BinaryTreeNodeAlloc();
if (new_node == NULL) {
exit (0);
}
new_node->data = x;
new_node->r_next = NULL;
new_node->l_next = NULL;
if (prev != NULL) {
prev->next = new_node;
} else {
list->head = new_node;
}
list->node_num++;
return (new_node);
}

回答No.4

hrsmmhr

BinaryTreeNode *BinaryTreeDataAdd(BinaryTreeNode *ptr, int x)
{
BinaryTreeNode **parent;
BinaryTreeNode *new_node;

while (ptr) {
if (ptr->data < x) {
if (ptr->l_next!=NULL) return(BinaryTreeDataAdd(ptr->l_next, x));
else parent = &(ptr->l_next);
}
else if (ptr->data > x) {
if (ptr->r_next!=NULL) return(BinaryTreeDataAdd(ptr->r_next, x));
else parent = &(ptr->r_next);
}
else if (ptr->data == x) return(NULL);

new_node = BinaryTreeNodeAlloc();
if (new_node == NULL) exit(0);
new_node->data = x;
(*parent)=new_node;
list->node_num++;
return (new_node);
}

でメインからBinaryTreeDataAdd(list->root, x);を呼んでください

回答No.3

Tacosan

そうですね, 図を使って「こういう二分木にこれを追加したらこうなってほしい」というのを明確にしてから「じゃあどうしようか」と考えるのは, 私もいいことだと思います＞#2. 少なくとも「どこがおかしいかはともかくどこかはおかしい」ということはわかりますしね.

しかし, 「二分木条件」ってなんだろう....

回答No.2

kmee

ダラダラとした説明じゃ、プログラムになんかできません。箇条書き程度に。
まずは、実際のプログラム用語なんか使わずにやり方を考えましょう。mallocだのポインタだのは、最後にCのプログラムにする段階で考えればよいことです。

混乱したら、いったんプログラムから離れることをお勧めします。
紙に図を書いてみるとか。
今回のだったら、ハンガーにハンガーひっかけて「二分木」を作って、新しいハンガーを適切な場所にひっかけるにはどうするのがいいか、実際にやってみるのも手です。
このとき、人間的な目線でやらないこと。例えば、全体を見て「ココ!」とかいうように。
どういう考えでどっちの枝を辿ったのか、ひっかけるときにどんな作業をするのか、事細かくメモしてみましょう。

プログラムなんてものは、上のような人間の言葉で書いたやりかたを、コンピュータの言葉に置き換えるだけのものです。

回答No.1

Tacosan

あなたは何を考えたのですか?

単にプログラムを載せるのではなく,
・どのような戦略でいこうとしているのか
・どこまでできて, どこで詰まっているのか
などを言葉できちんと書いてください.

あと, 人に見せるプログラムならそのことをちゃんと意識してほしい. コメントくらいつけられないの?

補足

１、格納要素、左ノード、右ノードへのポインタをメンバに持つ構造体とノード総数、ルートノードへのポインタをメンバに持つ構造体をそれぞれ宣言。
２、malloc関数を使ってノードの領域を確保する関数BinaryTreeNodeAllocを作る。

ここまでは大丈夫です。

３、データを追加する関数LinkedListDataAddをつくる。
まず注目するノードへのポインタptr、直前ノードへのポインタprevを宣言して終端ノードに到着するまでループし、最後に新しく追加したノードを終端ノードにするという流れでやっていこうとしてます。ただ線形探索とは違い、二分木条件やらが入ってきてわからなくなっています。

説明不足で申し訳ありません。

これでお答えしていただけますでしょうか？