[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

コンピュータIIIB(Javaアルゴリズム)第7回

目次
7.1 木(1)
7.1.1 木とは
7.1.2 木の構成
7.1.3 配列による木の構成
7.1.4 木の走査
7.2 演習7
7.3 レポート課題
7.4 参考文献
索引
    完全二分木     木構造   木の走査     後行順走査   節点   先行順走査   中央順走査   二分木       レベル   レベル順走査  

7.1 木(1)

7.1.1 木とは

次のようなイメージでデータが格納できるデータ構造を、 木構造tree structure ) あるいは単に tree ) と呼びます。

木のイメージ
図 7.1  木のイメージ

概念的には、木は 節点node ) と branch ) の集まりです。 枝は、2つの節点を結ぶものです。

節点や枝には、データが割り当てられることがあります。 上記の木では、節点に数値が割り当てられています。

木には、 root ) と呼ばれる節点が1つ指定されています。 普通、根は一番上に書かれます。 上記の木では、節点3が根です。

根に結ばれた節点はその下に書かれ、それらの節点に結ばれた節点はさらに下に書かれます。 もう下に書くものがない節点は、 leaf ) と呼ばれます。 上記の木では、節点4や節点6が葉です。

枝で結ばれている1つ上の節点を、元の節点の parent ) と呼びます。 枝で結ばれている1つ下の節点を、元の節点の child ) と呼びます。 根は親を持たない節点であり、葉は子を持たない節点です。 上記の木では、節点5は節点1の親であり、 節点1は節点5の子です。

節点の レベルlevel ) とは、その節点から根に至るまでの枝の本数のことです。 上記の木では、節点8はレベル1であり、節点9はレベル2です。

すべての節点の子が2個以下である木は、 二分木binary tree ) と呼ばれます。 葉は、子が0個と考えます。 二分木では、子は左と右で区別されます。 子が1つであっても、左か右に位置づけられます。 二分木の例を以下に示します。

二分木の例
図 7.2  二分木の例

二分木で、すべての葉のレベルが等しいか、レベルの1つ大きい葉があってもその葉が左に詰まっているものは、 完全二分木complete binary tree ) と呼ばれます。 以下は完全二分木の例です。

完全二分木の例
図 7.3  完全二分木の例

7.1.2 木の構成

それでは、Java言語で木を構成します。 節点にデータが割り当てられる二分木を作るために、次のようなイメージのクラスを用意します。 ここで、左側の参照は左の子を指し、右側の参照は右の子を指します。 親を指す参照はありません。

節点のイメージ
図 7.4  節点のイメージ

クラスの定義は次の通りです。

/*  1*/ class TreeNode {
/*  2*/     int data;
/*  3*/     TreeNode left;
/*  4*/     TreeNode right;
/*  5*/     TreeNode (int data, TreeNode left, TreeNode right) {
/*  6*/         this.data = data;
/*  7*/         this.left = left;
/*  8*/         this.right = right;
/*  9*/     }
/* 10*/ }

節点に割り当てられるデータは、フィールド data に格納されます。 左の子はフィールド left , 右の子はフィールド right です。 leftrightnull ならば、その節点は葉だと分かります。

ここで、例として、次のような木を構成します。

木の例
図 7.5  木の例

参照のイメージは、以下のようになります。

木における参照のイメージ
図 7.6  木における参照のイメージ

なお、根の上にあるのは、ダミー・データです。 リストの場合と同様に、ダミーを用意しますと木の操作がやりやすくなります。

プログラムでは、次のようになります。

/*  1*/ class TreeTest {
/*  2*/     public static void main (String[] args) {
/*  3*/         int DUMMY = 0;
/*  4*/         TreeNode tree = new TreeNode(DUMMY, null, null);
/*  5*/         tree.right = new TreeNode(1, null, null);
/*  6*/         tree.right.left = new TreeNode(2, null, null);
/*  7*/         tree.right.right = new TreeNode(3, null, null);
/*  8*/         tree.right.left.left = new TreeNode(4, null, null);
/*  9*/         tree.right.left.right = new TreeNode(5, null, null);
/* 10*/         System.out.println(tree.right.data);
/* 11*/         System.out.println(tree.right.left.data);
/* 12*/         System.out.println(tree.right.right.data);
/* 13*/         System.out.println(tree.right.left.left.data);
/* 14*/         System.out.println(tree.right.left.right.data);
/* 15*/     }
/* 16*/ }
b04a001@AsiaA1:~/comp3b% java TreeTest
1
2
3
4
5
b04a001@AsiaA1:~/comp3b%

7.1.3 配列による木の構成

もし、完全二分木だけを考えればよいのでしたら、配列でも木が構成できます。 配列要素に以下のような親子関係を割り当てますと、完全二分木が表現できます。 なお、 a [0] は番兵として使います。

配列要素の親子関係
図 7.7  配列要素の親子関係

節点 a [ k ] の親は a [ k / 2] です。 節点 a [ k ] の左の子は a [2 * k ], 右の子は a [2 * k + 1] です。 子が両方とも添字の範囲を越えていれば、その節点は葉だと分かります。

例えば、次のような木を構成します。

木の例
図 7.8  木の例

プログラムは次のようになります。

/*  1*/ class ArrayTreeTest {
/*  2*/     public static void main (String[] args) {
/*  3*/         int DUMMY = 0;
/*  4*/         int[] a = new int[6];
/*  5*/         a[0] = DUMMY;
/*  6*/         a[1] = 10;
/*  7*/         a[2] = 20;
/*  8*/         a[3] = 30;
/*  9*/         a[4] = 40;
/* 10*/         a[5] = 50;
/* 11*/         System.out.println(a[1]);
/* 12*/         System.out.println(a[2]);
/* 13*/         System.out.println(a[3]);
/* 14*/         System.out.println(a[4]);
/* 15*/         System.out.println(a[5]);
/* 16*/     }
/* 17*/ }
b04a001@AsiaA1:~/comp3b% java ArrayTreeTest
10
20
30
40
50
b04a001@AsiaA1:~/comp3b%

ここで、参照による木と配列による木を比較します。

表 7.1  参照による木と配列による木
操作 参照による木 配列による木
構成できる木 あらゆる二分木 完全二分木のみ
親へのアクセス 根からたどりなおしたら可能 節点 a[k] の親は a[k / 2]

7.1.4 木の走査

系統的な方法で、木のすべての節点を訪れることを、 木の走査tree traversal ) と言います。 例えば、まず根を訪れ、次にレベル1の節点を左から順に訪れ、その次にレベル2の節点を左から順に訪れ、…としますと、すべての節点に訪れることができます。 これを レベル順走査level-order traversal ) と言います。 この走査以外にも、

があります。 ここでは、二分木の走査を考えることにし、次の木を例とします。

木の例
図 7.9  木の例

先行順走査preorder traversal ) とは、まず根を訪れ、次に左の子を根と見なして先行順走査を行い、最後に右の子を根と見なして先行順走査を行うものです。 例では、

(1 の走査) = 1 (2 の走査) (3 の走査)
= 1 2 (4 の走査) (5 の走査) (3 の走査)
= 1 2 4 (8 の走査) (9 の走査) (5 の走査) (3 の走査)
= 1 2 4 8 (9 の走査) (5 の走査) (3 の走査)
= 1 2 4 8 9 (5 の走査) (3 の走査)
= 1 2 4 8 9 5 (3 の走査)
= 1 2 4 8 9 5 3 (6 の走査) (7 の走査)
= 1 2 4 8 9 5 3 6 (7 の走査)
= 1 2 4 8 9 5 3 6 7

です。 木を根から反時計回りになぞり、節点の左側を通過したときにその節点を取り出すことでも、先行順走査が行えます。

中央順走査inorder traversal ) とは、まず左の子を根と見なして中央順走査を行い、次に根を訪れ、最後に右の子を根と見なして中央順走査を行うものです。 例では、

(1 の走査) = (2 の走査) 1 (3 の走査)
= (4 の走査) 2 (5 の走査) 1 (3 の走査)
= (8 の走査) 4 (9 の走査) 2 (5 の走査) 1 (3 の走査)
= 8 4 (9 の走査) 2 (5 の走査) 1 (3 の走査)
= 8 4 9 2 (5 の走査) 1 (3 の走査)
= 8 4 9 2 5 1 (3 の走査)
= 8 4 9 2 5 1 (6 の走査) 3 (7 の走査)
= 8 4 9 2 5 1 6 3 (7 の走査)
= 8 4 9 2 5 1 6 3 7

です。 木を根から反時計回りになぞり、節点の直下を通過したときにその節点を取り出すことでも、中央順走査が行えます。

後行順走査postorder traversal ) とは、まず左の子を根と見なして後行順走査を行い、次に右の子を根と見なして後行順走査を行い、最後に根を訪れるものです。 例では、

(1 の走査) = (2 の走査) (3 の走査) 1
= (4 の走査) (5 の走査) 2 (3 の走査) 1
= (8 の走査) (9 の走査) 4 (5 の走査) 2 (3 の走査) 1
= 8 (9 の走査) 4 (5 の走査) 2 (3 の走査) 1
= 8 9 4 (5 の走査) 2 (3 の走査) 1
= 8 9 4 5 2 (3 の走査) 1
= 8 9 4 5 2 (6 の走査) (7 の走査) 3 1
= 8 9 4 5 2 6 (7 の走査) 3 1
= 8 9 4 5 2 6 7 3 1

です。 木を根から反時計回りになぞり、節点の右側を通過したときにその節点を取り出すことでも、後行順走査が行えます。

プログラムでは、走査するメソッドを再帰を使って書きます。

/*  1*/ class TreeTraverse {
/*  2*/     public static void main (String[] args) {
/*  3*/         int DUMMY = 0;
/*  4*/         TreeNode tree = new TreeNode(DUMMY, null, null);
/*  5*/         tree.right = new TreeNode(1, null, null);
/*  6*/         tree.right.left = new TreeNode(2, null, null);
/*  7*/         tree.right.right = new TreeNode(3, null, null);
/*  8*/         tree.right.left.left = new TreeNode(4, null, null);
/*  9*/         tree.right.left.right = new TreeNode(5, null, null);
/* 10*/         tree.right.right.left = new TreeNode(6, null, null);
/* 11*/         tree.right.right.right = new TreeNode(7, null, null);
/* 12*/         tree.right.left.left.left = new TreeNode(8, null, null);
/* 13*/         tree.right.left.left.right = new TreeNode(9, null, null);
/* 14*/         System.out.print("Preorder:  ");
/* 15*/         preorder(tree.right);
/* 16*/         System.out.println();
/* 17*/         System.out.print("Inorder:   ");
/* 18*/         inorder(tree.right);
/* 19*/         System.out.println();
/* 20*/         System.out.print("Postorder: ");
/* 21*/         postorder(tree.right);
/* 22*/         System.out.println();
/* 23*/     }
/* 24*/     static void preorder (TreeNode tree) {
/* 25*/         if (tree != null) {
/* 26*/             System.out.print(" " + tree.data);
/* 27*/             preorder(tree.left);
/* 28*/             preorder(tree.right);
/* 29*/         }
/* 30*/     }
/* 31*/     static void inorder (TreeNode tree) {
/* 32*/         if (tree != null) {
/* 33*/             inorder(tree.left);
/* 34*/             System.out.print(" " + tree.data);
/* 35*/             inorder(tree.right);
/* 36*/         }
/* 37*/     }
/* 38*/     static void postorder (TreeNode tree) {
/* 39*/         if (tree != null) {
/* 40*/             postorder(tree.left);
/* 41*/             postorder(tree.right);
/* 42*/             System.out.print(" " + tree.data);
/* 43*/         }
/* 44*/     }
/* 45*/ }
b04a001@AsiaA1:~/comp3b% java TreeTraverse
Preorder:   1 2 4 8 9 5 3 6 7
Inorder:    8 4 9 2 5 1 6 3 7
Postorder:  8 9 4 5 2 6 7 3 1
b04a001@AsiaA1:~/comp3b%

7.2 演習7

次の木を、先行順、中央順、および後行順に走査するプログラムを作成してください。

木の例
図 7.10  木の例

木は配列で表現します。

プログラムは穴埋めとします。 次のプログラムのメソッド preorder , inorder , および postorder を完成させてください。

class ArrayTreeTraverse {
    public static void main (String[] args) {
        int DUMMY = 0;
        int[] a = {DUMMY, 10, 20, 30, 40, 50, 60, 70, 80, 90};
        System.out.print("Preorder:  ");
        preorder(a, 1);
        System.out.println();
        System.out.print("Inorder:   ");
        inorder(a, 1);
        System.out.println();
        System.out.print("Postorder: ");
        postorder(a, 1);
        System.out.println();
    }
    static void preorder (int[] a, int k) {

        ???

    }
    static void inorder (int[] a, int k) {

        ???

    }
    static void postorder (int[] a, int k) {

        ???

    }
}
b04a001@AsiaA1:~/comp3b% java ArrayTreeTraverse
Preorder:   10 20 40 80 90 50 30 60 70
Inorder:    80 40 90 20 50 10 60 30 70
Postorder:  80 90 40 50 20 60 70 30 10
b04a001@AsiaA1:~/comp3b%

7.3 レポート課題

今日の演習7の答案(Javaプログラム)をメールで提出してください。 メールの差出人は学内のアドレス(b04a001@twcu.ac.jpなど)とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日(11月24日)を明記してください。


7.4 参考文献


[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

2006年11月24日更新
小西 善二郎 <konishi@twcu.ac.jp>
Copyright (C) 2006 Zenjiro Konishi. All rights reserved.