トリッキーコードネット トップへ戻る   C/C++, Java, Perl, PHP, JavaScript, アルゴリズム, ショートコーディング, IOCCCコードの解説, 等々

サイト情報

トリッキーなコード

7行プログラミング

物凄いコード集

アルゴリズム

データ構造

C/C++な話題

コードサンプル

ツール/環境構築

開発ノウハウ 等

ネタ/ジョーク集

おススメ書籍/サイト

サイトTOP >> データ構造 >> 二分探索木 - ノード定義 (C言語)

二分探索木(Binary Search Tree) - ノード定義

こちらの続きです。

まずは、ツリー構造を構築する為の、ノードの定義から ^^;)

typedef struct _tagDATA {

    char * pszName;

} data;


typedef struct _tagNODE {

    // ユニークなID
    int nId;

    // データ構造体
    data * data;

    struct _tagNODE * parent;
    struct _tagNODE * left;
    struct _tagNODE * right;

} node;
ノード内に、
  • ID (ユニークな識別子)
  • データ構造体へのポインタ
  • 親nodeを指すポインタ
  • 左の子nodeを指すポインタ
  • 右の子nodeを指すポインタ
を持ちます。 ここでは便宜上、扱うデータは pszName(氏名)だけですが、 扱うデータ数が多くなると、ノード内にそのままデータを入れるのではなく、 別途データを格納する構造体を定義し、そこへのポインタをノード内に保持する ようにした方が良いです。 (∵ 別関数へデータを渡す際に、コードが複雑化するのを避けられるメリットがあります。    また、扱うデータの種類が急に変更になった場合でも、コードの修正が少なくてすみます^^) 親を指すポインタをノード内に持たない方法もありますが、 先祖ノードを辿る際や、削除時に処理が楽になる為、ここでは親を指すポインタを入れる事にします。 さて、それではバリバリとコーディングを進めます。 まずはルートノードへのポインタを、グローバル変数に宣言します。
node * g_root;
ノードの追加、削除、検索、一覧表示、etc・・・、 全ての処理は、このルートノードへのポインタから各ノードを辿る事で実装します。 続いて、ノードを新規作成する関数です。
/*
 * ノードを作成する。
 *
 * [戻り] 関数成功時:nodeポインタ / 失敗時:NULL
 */
node * makeNode(int id, data * d)
{
    node * n;

    // ノード作成
    if (! (n = (node *)malloc(sizeof(node))) ) {
        return NULL;
    }

    // パラメータのid・データを、ノードにセット
    n -> nId  = id;
    n -> data = d;

    // ポインタを初期化
    n -> left = n -> right = n -> parent = NULL;

    return n;
}
ID 及び データ構造体をパラメータとして渡すと、それらを包み込んだノードを返します。 特に難解な点は無いかと思いますが、 左の子/右の子/親 を指すポインタをNULLで初期化するのを忘れないようにします。 (でないと、後々大変な目に・・・) おまけで、ノードを削除する関数も実装しておきます^^
// ノードを削除(メモリ上から解放)する。
void releaseNodeData(node * n)
{
    free(n -> data -> pszName);
    free(n -> data);
    free(n);
}
データ構造体中、動的にメモリを割当てるメンバが変更になった際は、この関数内にも修正を加えます。 二分探索木 - ノード追加/検索 に続く
         このエントリーをはてなブックマークに追加   


作業効率化・ライフハックのオススメ記事




コンピュータ・テクノロジーのオススメ記事





恋愛・人間関係のオススメ記事




※ 当サイトは、トップページからリンクで辿る事の出来るページに限り、リンクフリーです。
※ 当サイトの閲覧/利用によって生じた如何なる損害も、当サイト管理人は責任を負いません。
※ 当サイトの内容を転載される場合は、当サイトへのリンクをお願い致します。