二分木探索プログラム
Posted: 2011年7月12日(火) 18:29
今、線形探索プログラムをつくる過程で、int型の二分木にデータを追加する関数(引数は二分木へのポインタと追加する値、追加されたノードへのポインタを返す)をつくろうとしてます。
以前リストにデータを追加する関数をつくったのでそれを変更してつくろうとしているのですが途中までいってつまってしまいました。
方針としては
１、格納要素、左ノード、右ノードへのポインタをメンバに持つ構造体とノード総数、ルートノードへのポインタをメンバに持つ構造体をそれぞれ宣言。
２、malloc関数を使ってノードの領域を確保する関数BinaryTreeNodeAllocを作る。
ここまでは大丈夫です。
３、データを追加する関数LinkedListDataAddをつくる。
まず注目するノードへのポインタptr、直前ノードへのポインタprevを宣言して終端ノードに到着するまでループし、最後に新しく追加したノードを終端ノードにするという流れでやっていこうとしてます。ただリストとかとは違い、二分木条件やらが入ってきてわからなくなっています。
是非アドバイスをください。よろしくお願いします！
以前リストにデータを追加する関数をつくったのでそれを変更してつくろうとしているのですが途中までいってつまってしまいました。
方針としては
１、格納要素、左ノード、右ノードへのポインタをメンバに持つ構造体とノード総数、ルートノードへのポインタをメンバに持つ構造体をそれぞれ宣言。
２、malloc関数を使ってノードの領域を確保する関数BinaryTreeNodeAllocを作る。
ここまでは大丈夫です。
３、データを追加する関数LinkedListDataAddをつくる。
まず注目するノードへのポインタptr、直前ノードへのポインタprevを宣言して終端ノードに到着するまでループし、最後に新しく追加したノードを終端ノードにするという流れでやっていこうとしてます。ただリストとかとは違い、二分木条件やらが入ってきてわからなくなっています。
是非アドバイスをください。よろしくお願いします！
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);
}