第8回 ツリー(階層化)構造

ワンポイントの更新が火曜日に変わりました。 今回はツリー構造についてです。
パソコンではフォルダ(ディレクトリ)操作等でよく利用しますね。
ツリー構造をデータ化する場合、データに階層のレベルや子データをもたせたりといった ことをよく目にしますが、実際には親のみを持たせるだけで片付きます。

また、以下に出てくるコードにもありますが、 再帰処理はツリー構造を処理する上で非常に有用です。
但し、一歩間違えばマシンごと動きを止めるような致命的なバグに結びつく 非常に危険な技術でもあります。
しっかりマスターしておきましょう。
以下、データの追加と表示を行うプログラムです。
長いですが、要所要所をしっかり確認しましょう。
また、メインを除いてデータクラス1つで作っているのも ポイントの一つです。

 //**************************************************
 // メインクラス
 //**************************************************
 public class Tree {

     public static void main(String[] args) {
         
         // データの追加
        Data.put(new Data("水"));
         Data.put(new Data("肉"));
         Data.put(new Data("肉", "牛肉"));
         Data.put(new Data("肉", "豚肉"));
         Data.put(new Data("豚肉","豚足"));
         Data.put(new Data("野菜"));
         Data.put(new Data("野菜", "根菜"));
         Data.put(new Data("根菜", "大根"));
         Data.put(new Data("大根", "カイワレ大根"));
         
         // ツリー表示
        System.out.println(Data.getPrintString());
     }

 }

 //**************************************************
 // データクラス
 //**************************************************
 class Data {

     private static TreeMap list = new TreeMap();

     private String key    = null;
     private Data   parent = null;
     
     // データ追加
    public static void put(Data data) {
         list.put(data.getKey(), data);
     }
     
     // データ取得
    public static Data get(String key) {
         return (Data)list.get(key);
     }
     
     // ルート(親がnull)のデータ取得
    public static TreeMap getRoot() {
         TreeMap children = new TreeMap();
         for (Iterator i = list.keySet().iterator(); i.hasNext();) {
             Data data = (Data)list.get(i.next());
             if (data.getParent() == null) {
                 children.put(data.getKey(), data);
             }
         }
         return children;
     }
     
     // コンストラクタ
    public Data(String key) {
         this((Data)null, key);
     }
     public Data(String parentKey, String key) {
         this(Data.get(parentKey), key);
     }
     public Data(Data parent, String key) {
         this.parent = parent;
         this.key = key;
     }
     
     // キー
    public String getKey() { return key; }
     public void setKey(String key) { this.key = key; }
     
     // 親データ
    public Data getParent() { return parent; }
     public void setParent(Data parent) { this.parent = parent; }

     // 子データ取得
    public TreeMap getChildren() {
         TreeMap children = new TreeMap();
         for (Iterator i = list.keySet().iterator(); i.hasNext();) {
             Data data = (Data)list.get(i.next());
             if (data.getParent() == this) {
                 children.put(data.getKey(), data);
             }
         }
         return children;
     }
     
     // ツリー文字列取得
    public static String getPrintString() {
         StringBuffer sb = new StringBuffer();
         
         setPrintString(sb, null, new Integer(0));
         
         return sb.toString();
     }

     // ツリー文字列生成
    private static void setPrintString(StringBuffer sb, Data parent, Integer rank) {
         TreeMap children = (parent == null?Data.getRoot():parent.getChildren());
         
         if (children.size() == 0) {
             return;
         }
         
         int index = 0;
         for (Iterator i = children.keySet().iterator(); i.hasNext();) {
             String space = "";
             index++;
             
             
             for (int j = 0; j < rank.intValue(); j++) {
                 space += "  ";
             }
             
             Data child = (Data)list.get(i.next());
             sb.append(space
                     + child.getKey()
                     + System.getProperty("line.separator"));
             rank = new Integer(rank.intValue() + 1);
             setPrintString(sb, child, rank);
             rank = new Integer(rank.intValue() - 1);
         }
     }
 }

お腹の肉も階層化!!

2007年7月3日 | カテゴリー：Javaワンポイント