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

サイト情報

トリッキーなコード

7行プログラミング

物凄いコード集

アルゴリズム

データ構造

C/C++な話題

コードサンプル

ツール/環境構築

開発ノウハウ 等

ネタ/ジョーク集

おススメ書籍/サイト

サイトTOP >> データ構造 >> 二分探索木 - ノード追加/検索 (C言語)

二分探索木(Binary Search Tree) - ノード追加/検索

こちらの続きです。

次は、ツリーへノードを追加する関数を実装します。

・・・と、その前に、ツリー内ではどのようにノードが配置されるのかを説明しておきます ^^

プログラマーによっては独自のルールを決めている人もいますが、大抵の場合、
とあるノードが存在する場合、
左側にはそのノードよりも大きいノード、右側にはそのノードよりも小さいノード
を配置していくのが習慣です。
(ここでの「大きい」「小さい」は、ユニークなIDを比較して判断します。)


どういう事なのか具体例を挙げます。
ユニークIDが 500, 750, 250, 550, 100, 1000, 200, 150 の8つのノードがあり、これらを順に空のツリーへと追加していくものとします。

1.初期状態

二分探索木への追加 - 初期状態 まず、これがノード追加前の状態です。rootはNULLを指しています。

2.ノード[500]を追加

二分探索木への追加2 ユニークIDが500のノード(便宜上ノード[500])を追加した状態です。rootがノード[500]を指すようになります。

3.ノード[750]を追加

二分探索木への追加3 ノード[750]を追加した状態です。 rootのユニークID(500)と比較し、新規で追加したノードのユニークID(750)は大きいです。 その為、ノード[500]の左の子に、ノード[750]は配置されます。

4.ノード[250]を追加

二分探索木への追加4 ノード[250]を追加した状態です。 rootのユニークID(500)と比較し、新規で追加したノードのユニークID(250)は小さいです。 その為、ノード[500]の右側に、ノード[250]は配置されます。

5.ノード[550]を追加

二分探索木への追加5 ノード[550]を追加した状態です。 ・rootのユニークID(500)と比較し、新規で追加したノードのユニークID(550)は大きいです。  ⇒ その為、続けて右側のノードと比較します。 ・ノード[750]のユニークIDと比較し、新規で追加したノードのユニークID(550)は小さいです。  ⇒ その為、ノード[750]の右側に、ノード[550]は配置されます。 以下、同様の処理を続けます。

6.ノード[100]を追加

二分探索木への追加6

7.ノード[1000]を追加

二分探索木への追加7

8.ノード[200]を追加

二分探索木への追加8

9.ノード[150]を追加

二分探索木への追加9

新規ノードの追加

二分探索木のノード配置を理解したところで、そろそろお待ちかね(?)の、ノード追加関数を実装します。
 1 : /*
 2 :  * ツリーへノードを追加する
 3 :  *
 4 :  * [戻り] 成功時:0 / 失敗時(idの重複):1
 5 :  */
 6 : int addToTree(node * n)
 7 : {
 8 :     node * tmp;
 9 :
10 :     // ルートが空の場合は、ルートへ
11 :     if (! g_root) {
12 :         g_root = n;
13 :         return 0;
14 :     }
15 :
16 :
17 :     tmp = g_root;
18 :
19 :     while(1) {
20 :
21 :         if (tmp -> nId == n -> nId) {     // idの重複
22 :             return 1;
23 :         }
24 :         else if (tmp -> nId < n -> nId) { // 比較対象ノードのidよりも、挿入ノードのidの方が大きい場合 ⇒ 比較対象を左の子へと移行
25 :
26 :             if (tmp -> left) {
27 :                 tmp = tmp -> left;
28 :             }
29 :             else {
30 :                 tmp -> left = n;
31 :                 break;
32 :             }
33 :         }
34 :         else {                        // 比較対象ノードのidよりも、挿入ノードのidの方が小さい場合 ⇒ 比較対象を右の子へと移行
35 :
36 :             if (tmp -> right) {
37 :                 tmp = tmp -> right;
38 :             }
39 :             else {
40 :                 tmp -> right = n;
41 :                 break;
42 :             }
43 :         }
44 :     }
45 :
46 :     n -> parent = tmp;
47 :
48 :     return 0;
49 : }
図で説明した物をコードに書き出しただけです ^^ 10~14行目: ルートが空の場合は、新規ノードをルートにセットし、関数を終了します。 8行目: 現在比較対象のノードを、このポインタ(tmp)で指します。 17行目: ルートから順に辿り各ノードとの比較を行っていく為、まずはtmpにルートをセットします。 21~23行目: IDはユニークだという前提の為、追加ノードと、ツリー内既存ノードのIDが等しい場合には、エラーを返します。 24~33行目: 比較対象ノードのIDよりも、追加ノードのIDの方が大きい場合、比較対象を左の子へと移動させます。 ただし、もし比較対象ノードに左の子がいない(NULLがセットされている)場合は、 そこへ追加ノードをセットし、関数を正常終了します。 34~43行目: 比較対象ノードのIDよりも、追加ノードのIDの方が小さい場合、比較対象を右の子へと移動させます。 ただし、もし比較対象ノードに右の子がいない(NULLがセットされている)場合は、 そこへ追加ノードをセットし、関数を正常終了します。 ・・・と、まぁこんな感じ♪ 続いて、ノードを検索する関数を実装します。

ノード検索

/*
 * ノードを検索(idがsearchIdのノードを取得)する。
 *
 * [戻り] ノードポインタ:該当するノードを発見した場合 / NULL:該当するノードを発見できなかった場合
 */
node * searchNode(int searchId)
{
    node * tmp = g_root;

    while (tmp) {

        if (tmp -> nId == searchId) {      // 該当するノードを発見
            return tmp;
        }
        else if (tmp -> nId < searchId) {  // 比較対象ノードのidよりも、検索idの方が大きい場合 ⇒ 比較対象を左の子へと移行
            tmp = tmp -> left;
        }
        else {                             // 比較対象ノードのidよりも、検索idの方が小さい場合 ⇒ 比較対象を右の子へと移行
            tmp = tmp -> right;
        }

    }

    return NULL;
}
上のノード追加関数を理解していれば、特に説明は要らないはずです ^^ 二分探索木 - ノード削除 に続く
         このエントリーをはてなブックマークに追加   


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




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





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




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