- 木構造...親子関係のあるデータ構造
- ノード...節点、データを持つ位置
- ルート...根、最上位のノード
- 葉...再開のノード
- エッジ...枝、ノード間をつなぐ線
- 幅優先探索...同じ深さのノードを優先的に探索する
- 深さ優先探索...先行順、後行順、中間順
↳先行順...あるノードが子を持つとき優先して子を探索する
↳後行順...あるノードを探索し、次にそのノードの子を探索する
↳中間順...あるノードが子を持つとき、優先して一つ目の子を探索し、次に親を探索する、その後に残りの子を探索する - 2分木...子の数が二つ以下である木
↳完全2分木...子の数が二つであり、すべての葉の深さが等しい
↳2分探索木...あるノードの子とそこから葉までのすべてのノードは、左が親よりも小さいもの、右が親よりも大きいものとなる
↳ヒープ...二分探索木において、子が親より常に小さい
木構造を作成する
※実力不足で一部作れませんでした、模索中です。
まずはjavaで木構造ノードを組む
以下はint変数と任意の子を持つノードである
package tree;
import java.util.ArrayList;
public class node {
private int data;
private ArrayList<node> children = new ArrayList<node>();
node getchildren(int n) {
return this.children.get(n);
}
void born(node child){
this.children.add(child);
}
int countchildren() {
return this.children.size();
}
int getdata() {
return this.data;
}
node(int data){
this.data = data;
}
}
実体を構成して参照を行う
package tree;
public class main {
public static void main(String[] args) {
node master = new node(10);
master.born(new node(11));
master.born(new node(12));
master.born(new node(5));
master.getchildren(0).born(new node(15));
master.getchildren(1).born(new node(8));
master.getchildren(1).born(new node(3));
master.getchildren(1).born(new node(19));
master.getchildren(2).born(new node(15));
master.getchildren(2).born(new node(1));
//表示
System.out.println(master.getdata());
System.out.println(master.getchildren(1).getdata());
System.out.println(master.getchildren(1).getchildren(2).getdata());
}
}
出力
10
12
19
深さ優先探索を行う
package tree;
import java.util.ArrayList;
public class search {
public static void search(node X,int value) {
switch(value){
case 0: traildepthsearch(X);System.out.println();break;
case 1: advancedepthsearch(X);System.out.println();break;
}
}
//先行順
private static void traildepthsearch(node X) {
System.out.print(X.getdata()+" ");
if(X.countchildren()>0) {
for(int i=0;i<X.countchildren();i++) {
traildepthsearch(X.getchildren(i));
}
}else{
}
}
//後行順
private static void advancedepthsearch(node X) {
if(X.countchildren()>0) {
for(int i=0;i<X.countchildren();i++) {
advancedepthsearch(X.getchildren(i));
}
System.out.print(X.getdata()+" ");
}else{
System.out.print(X.getdata()+" ");
}
}
}
main
package tree;
public class main {
public static void main(String[] args) {
node master = new node(10);
master.born(new node(11));
master.born(new node(12));
master.born(new node(5));
master.getchildren(0).born(new node(15));
master.getchildren(1).born(new node(8));
master.getchildren(1).born(new node(3));
master.getchildren(1).born(new node(19));
master.getchildren(2).born(new node(15));
master.getchildren(2).born(new node(1));
search.search(master,0);
search.search(master,1);
}
}
出力
参照した順番に出力していて、それぞれ正しく参照できている
10 11 15 12 8 3 19 5 15 1
15 11 8 3 19 12 15 1 5 10
幅優先探索を行う。上記のノード構造では幅優先探索は行えないため別のノードを定義する
模索中
二分探索木を生成する
二分探索木は子の数が2で固定のため、固定長配列で宣言している
package tree;
public class node {
private int data;
private node[] children = new node[2];
public void set(node[] children) {
}
node(int data) {
this.data = data;
}
}
中身を構成する
模索中