| 目次 | 索引 |
|---|---|
h2 木 toc-trees
h3 木とは toc-what-is-a-tree
次のようなイメージでデータが格納できるデータ構造を、
index 木構造 tree structure きこうそう
あるいは単に
index 木 tree き
と呼びます。
3
|
+-------+-------+
| | |
2 8 5
| |
+---+---+ +---+
| | |
6 9 1
|
+---+---+
| |
7 4
概念的には、木は
index 節点 node せつてん
と
index 枝 branch えた
の集まりです。
枝は、2 つの節点を結ぶものです。
節点や枝には、データが割り当てられることがあります。
上記の木では、節点に数値が割り当てられています。
木には、
index 根 root ね
と呼ばれる節点が 1 つ指定されています。
普通、根は一番上に書かれます。
上記の木では、節点 3 が根です。
根に結ばれた節点はその下に書かれ、
それらの節点に結ばれた節点はさらに下に書かれます。
もう下に書くものがない節点は、
index 葉 leaf は
と呼ばれます。
上記の木では、節点 4 や節点 6 が葉です。
枝で結ばれている一つ上の節点を、元の節点の
index 親 parent おや
と呼びます。
枝で結ばれている一つ下の節点を、元の節点の
index 子 child こ
と呼びます。
根は親を持たない節点であり、葉は子を持たない節点です。
上記の木では、節点 5 は節点 1 の親であり、
節点 1 は節点 5 の子です。
節点の
index レベル level れへる
とは、その節点から根に至るまでの枝の本数のことです。
上記の木では、節点 8 はレベル 1 であり、
節点 9 はレベル 2 です。
すべての節点の子が 2 個以下である木は、
index 二分木 binary tree にふんき
と呼ばれます。
葉は、子が 0 個と考えます。
二分木では、子は左と右で区別されます。
子が 1 つであっても、左か右に位置づけられます。
二分木の例を以下に示します。
6
|
+-------+-------+
| |
4 1
| |
+---+ +---+---+
| | |
7 5 8
| |
+---+---+ +---+
| | |
9 2 3
二分木で、すべての葉のレベルが等しいか、
レベルの一つ大きい葉があってもその葉が左に詰まっているものは、
index 完全二分木 complete binary tree かんせんにふんき
と呼ばれます。
以下は完全二分木の例です。
4
|
+-------+-------+
| |
6 1
| |
+---+---+ +---+---+
| | | |
5 2 3 7
h3 木の構成 toc-tree-construction
それでは、Java 言語で木を構成します。
節点にデータが割り当てられる二分木を作るために、
次のようなイメージのクラスを用意します。
ここで、左側の参照は左の子を指し、右側の参照は右の子を指します。
親を指す参照はありません。
+-----+-----+-----+
| | | |
+--+--* |data | *--+--+
| +-----+-----+-----+ |
| |
v v
クラスの定義は次の通りです。
class IntTree {
int node;
IntTree left, right;
IntTree (int node, IntTree left, IntTree right) {
this.node = node;
this.left = left;
this.right = right;
}
}
節点に割り当てられるデータは、フィールド node に格納されます。
左の子はフィールド left, 右の子はフィールド right です。
left も right も null ならば、その節点は葉だと分かります。
ここで、例として、次のような木を構成します。
1
|
+---+---+
| |
2 3
|
+---+---+
| |
4 5
参照のイメージは、以下のようになります。
+-----+-----+-----+
| | | |
|null |dummy| *--+--+
+-----+-----+-----+ |
|
v
+-----+-----+-----+
| | | |
+--+--* | 1 | *--+--+
| +-----+-----+-----+ |
| |
v v
+-----+-----+-----+ +-----+-----+-----+
| | | | | | | |
+--+--* | 2 | *--+--+ |null | 3 |null |
| +-----+-----+-----+ | +-----+-----+-----+
| |
v v
+-----+-----+-----+ +-----+-----+-----+
| | | | | | | |
|null | 4 |null | |null | 5 |null |
+-----+-----+-----+ +-----+-----+-----+
なお、根の上にあるのは、ダミーのインスタンスです。
ダミーを用意しますと、木の操作がやりやすくなります。
プログラムでは、次のようになります。
class TreeTest {
public static void main (String[] args) {
int DUMMY = 0;
IntTree tr = new IntTree(DUMMY, null, null);
tr.right = new IntTree(1, null, null);
tr.right.left = new IntTree(2, null, null);
tr.right.right = new IntTree(3, null, null);
tr.right.left.left = new IntTree(4, null, null);
tr.right.left.right = new IntTree(5, null, null);
System.out.println(tr.right.node);
System.out.println(tr.right.left.node);
System.out.println(tr.right.right.node);
System.out.println(tr.right.left.left.node);
System.out.println(tr.right.left.right.node);
}
}
b04a001@AsiaA1:~/comp3b% java TreeTest
1
2
3
4
5
b04a001@AsiaA1:~/comp3b%
h3 配列による木の構成 toc-array-tree-construction
もし、完全二分木だけを考えればよいのでしたら、
配列でも木が構成できます。
配列要素に以下のような親子関係を割り当てますと、
完全二分木が表現できます。
なお、a[0] は番人として使います。
a[1]
|
+-----+-----+
| |
a[2] a[3]
| |
+--+--+ +--+--+
| | | |
a[4] a[5] a[6] a[7]
|
+--+--+
| |
a[8] a[9] ...
節点 a[k] の親は a[k / 2] です。
節点 a[k] の左の子は a[2 * k], 右の子は a[2 * k + 1] です。
子が両方とも添字の範囲を越えていれば、
その節点は葉だと分かります。
例えば、次のような木を構成します。
10
|
+---+---+
| |
20 30
|
+---+---+
| |
40 50
プログラムは次のようになります。
class ArrayTreeTest {
public static void main (String[] args) {
int DUMMY = 0;
int[] a = new int[6];
a[0] = DUMMY;
a[1] = 10;
a[2] = 20;
a[3] = 30;
a[4] = 40;
a[5] = 50;
System.out.println(a[1]);
System.out.println(a[2]);
System.out.println(a[3]);
System.out.println(a[4]);
System.out.println(a[5]);
}
}
b04a001@AsiaA1:~/comp3b% java ArrayTreeTest
10
20
30
40
50
b04a001@AsiaA1:~/comp3b%
ここで、参照による木と配列による木を比較します。
・参照による木では、あらゆる二分木が作れますが、
配列による木では、完全二分木しか作れません。
・参照による木では、親はすぐには分かりませんが、
配列による木では、節点 a[k] の親は a[k /2] で得られます。
h3 木の走査 toc-tree-traverse
系統的な方法で、木のすべての節点を訪れることを、
index 木の走査 tree traversal きのそうさ
と言います。
例えば、まず根を訪れ、次にレベル 1 の節点を左から順に訪れ、
その次にレベル 2 の節点を左から順に訪れ、…としますと、
すべての節点に訪れることができます。
これを
index レベル順走査 level-order traversal れへるしゆんそうさ
と言います。
この走査以外にも、
・先行順走査
・中央順走査 (二分木のみ)
・後行順走査
があります。
ここでは、二分木の走査を考えることにし、次の木を例とします。
1
|
+-----+-----+
| |
2 3
| |
+--+--+ +--+--+
| | | |
4 5 6 7
|
+--+--+
| |
8 9
index 先行順走査 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
です。
木を根から反時計回りになぞり、
節点の左側を通過したときにその節点を取り出すことでも、
先行順走査が行えます。
index 中央順走査 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
です。
木を根から反時計回りになぞり、
節点の直下を通過したときにその節点を取り出すことでも、
中央順走査が行えます。
index 後行順走査 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
です。
木を根から反時計回りになぞり、
節点の右側を通過したときにその節点を取り出すことでも、
後行順走査が行えます。
プログラムでは、走査するメソッドを再帰を使って書きます。
class TreeTraverse {
public static void main (String[] args) {
int DUMMY = 0;
IntTree tr = new IntTree(DUMMY, null, null);
tr.right = new IntTree(1, null, null);
tr.right.left = new IntTree(2, null, null);
tr.right.right = new IntTree(3, null, null);
tr.right.left.left = new IntTree(4, null, null);
tr.right.left.right = new IntTree(5, null, null);
tr.right.right.left = new IntTree(6, null, null);
tr.right.right.right = new IntTree(7, null, null);
tr.right.left.left.left = new IntTree(8, null, null);
tr.right.left.left.right = new IntTree(9, null, null);
System.out.print("Preorder: ");
preorder(tr.right);
System.out.println();
System.out.print("Inorder: ");
inorder(tr.right);
System.out.println();
System.out.print("Postorder: ");
postorder(tr.right);
System.out.println();
}
static void preorder (IntTree tr) {
if (tr != null) {
System.out.print(" " + tr.node);
preorder(tr.left);
preorder(tr.right);
}
}
static void inorder (IntTree tr) {
if (tr != null) {
inorder(tr.left);
System.out.print(" " + tr.node);
inorder(tr.right);
}
}
static void postorder (IntTree tr) {
if (tr != null) {
postorder(tr.left);
postorder(tr.right);
System.out.print(" " + tr.node);
}
}
}
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%
h3 演習 8 toc-exercises
次の木を、先行順、中央順、
および後行順に走査するプログラムを作成してください。
10
|
+-----+-----+
| |
20 30
| |
+--+--+ +--+--+
| | | |
40 50 60 70
|
+--+--+
| |
80 90
木は配列で表現します。
プログラムは穴埋めとします。
次のプログラムのメソッド 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%
今日の演習8の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（11月19日）を明記してください。