次のようなイメージでデータが格納できるデータ構造を、 木構造 （ tree structure ） あるいは単に 木 （ tree ） と呼びます。
概念的には、木は 節点 （ 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つであっても、左か右に位置づけられます。 二分木の例を以下に示します。
二分木で、すべての葉のレベルが等しいか、レベルの1つ大きい葉があってもその葉が左に詰まっているものは、 完全二分木 （ complete binary tree ） と呼ばれます。 以下は完全二分木の例です。
それでは、Java言語で木を構成します。 節点にデータが割り当てられる二分木を作るために、次のようなイメージのクラスを用意します。 ここで、左側の参照は左の子を指し、右側の参照は右の子を指します。 親を指す参照はありません。
クラスの定義は次の通りです。
/* 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
です。
left
も
right
も
null
ならば、その節点は葉だと分かります。
ここで、例として、次のような木を構成します。
参照のイメージは、以下のようになります。
なお、根の上にあるのは、ダミー・データです。 リストの場合と同様に、ダミーを用意しますと木の操作がやりやすくなります。
プログラムでは、次のようになります。
/* 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%
もし、完全二分木だけを考えればよいのでしたら、配列でも木が構成できます。 配列要素に以下のような親子関係を割り当てますと、完全二分木が表現できます。 なお、 a [0] は番兵として使います。
節点 a [ k ] の親は a [ k / 2] です。 節点 a [ k ] の左の子は a [2 * k ], 右の子は a [2 * k + 1] です。 子が両方とも添字の範囲を越えていれば、その節点は葉だと分かります。
例えば、次のような木を構成します。
プログラムは次のようになります。
/* 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%
ここで、参照による木と配列による木を比較します。
| 操作 | 参照による木 | 配列による木 |
|---|---|---|
| 構成できる木 | あらゆる二分木 | 完全二分木のみ |
| 親へのアクセス | 根からたどりなおしたら可能 | 節点 a[k] の親は a[k / 2] |
系統的な方法で、木のすべての節点を訪れることを、 木の走査 （ tree traversal ） と言います。 例えば、まず根を訪れ、次にレベル1の節点を左から順に訪れ、その次にレベル2の節点を左から順に訪れ、…としますと、すべての節点に訪れることができます。 これを レベル順走査 （ level-order traversal ） と言います。 この走査以外にも、
があります。 ここでは、二分木の走査を考えることにし、次の木を例とします。
先行順走査 （ 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%
次の木を、先行順、中央順、および後行順に走査するプログラムを作成してください。
木は配列で表現します。
プログラムは穴埋めとします。 次のプログラムのメソッド 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の答案（Javaプログラム）をメールで提出してください。 メールの差出人は学内のアドレス（b04a001@twcu.ac.jpなど）とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（11月24日）を明記してください。