掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.29570

二分探索木に新たなデータを挿入
投稿者---uno(2007/01/23 19:16:43)


二分探索木に新たな数値を挿入する課題で、以下のようにしてできました。ただ、この挿入する関数insert_btを繰り返し構文によって(再帰関数を用いずに)定義しなおしたいのですが、よくわかりません。どなたかわかる方がいらっしゃれば、教えていただけないでしょうか。
#include <stdio.h>
#include <stdlib.h>

typedef struct btree /*二分木構造体*/
{
    int data;
    struct btree *left;
    struct btree *right;
} BTREE;

BTREE *new_bt(int x, BTREE *y, BTREE *z); /*プロトタイプ宣言*/
BTREE *insert_bt (int x, BTREE *y);
void display_bt(BTREE *y);

void main() /*insert_btテスト用プログラム*/
{
    BTREE *root = NULL;
    root = insert_bt(35, root);display_bt(root);printf("\n");
    root = insert_bt(21, root);display_bt(root);printf("\n");
    root = insert_bt(46, root);display_bt(root);printf("\n");
    root = insert_bt(13, root);display_bt(root);printf("\n");
    root = insert_bt(40, root);display_bt(root);printf("\n");
    root = insert_bt(61, root);display_bt(root);printf("\n");
    root = insert_bt(69, root);display_bt(root);printf("\n");
}

BTREE *new_bt(int x, BTREE *y, BTREE *z) /*二分木の生成関数new_bt*/
{
    BTREE *w = (BTREE *)malloc(sizeof(BTREE));
    w->data = x;
    w->left = y;
    w->right = z;
    return w;
}

BTREE *insert_bt(int x, BTREE *y) /*挿入関数insert_bt*/ ←これ
{
    if(y==NULL) {
        return new_bt(x, NULL, NULL);
    }
    else if(x < y->data) {
        y->left = insert_bt(x, y->left);
        return y;
    }
    else if(x > y->data) {
        y->right = insert_bt(x, y->right);
        return y;
    }
    else return y;
}

void display_bt(BTREE *y) /*二分木の表示関数*/
{
    if (y==NULL) return;
    display_bt(y->left);
    printf("%i ", y->data);
    display_bt(y->right);
}

このプログラムの実行結果は
35
21 35
21 35 46
13 21 35 46
13 21 35 40 46
13 21 35 40 46 61
13 21 35 40 46 61 69
でした。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:二分探索木に新たなデータを挿入 29577 RiSK 2007/01/23 22:19:56


No.29577

Re:二分探索木に新たなデータを挿入
投稿者---RiSK(2007/01/23 22:19:56)


信じらんないぐらい汚い。おまけにバグあるかもしれない。
激しく書き直し推奨。
BTREE *insert_bt(int x, BTREE *y) /*挿入関数insert_bt*/
{
    BTREE*z = y;
    for (; y && x!=y->data; )
    {
        if (x < y->data)
        {
            if (!y->left)
            {
                y->left=new_bt(x,0,0);
                break;
            }
            else
            {
                y = y->left;
                continue;
            }
        }
        else if (x > y->data)
        {
            if (!y->right)
            {
                y->right=new_bt(x,0,0);
                break;
            }
            else
            {
                y = y->right;
                continue;
            }
        }
    }
    if (!y)
    {
        return new_bt(x, NULL, NULL);
    }
    else
    {
        return z;
    }
}



この投稿にコメントする

削除パスワード

No.29582

Re:二分探索木に新たなデータを挿入
投稿者---ルナレルナ(2007/01/23 23:18:15)
http://park6.wakwak.com/~nougaki/mini_program/


こんな感じじゃぁ駄目だろうか???

    while (y != NULL) {
        if (x == y->data)
            return y;
        if (x < y->data)
            y = y->left;
        else
            y = y->right;
    }
    return new_bt(x, NULL, NULL);



この投稿にコメントする

削除パスワード

No.29586

Re:二分探索木に新たなデータを挿入
投稿者---RiSK(2007/01/24 13:15:23)


>こんな感じじゃぁ駄目だろうか???

テストしました?
35
21
46
13
40
61
69
Press any key to continue
木が繋がってません。


この投稿にコメントする

削除パスワード

No.29588

Re:二分探索木に新たなデータを挿入
投稿者---かずま(2007/01/24 13:29:11)


> 激しく書き直し推奨。
BTREE *insert_bt(int x, BTREE *y)
{
    BTREE *p = y, **q = &y;
    while (p)
        p = x < p->data ? p->left ? p->left : (q = &p->left, NULL)
          : x > p->data ? p->right ? p->right : (q = &p->right, NULL)
          : NULL;
    *q = new_bt(x, NULL, NULL);
    return y;
}



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧