木構造とは : JavaA2Z

木構造

日本語	木構造
英語	tree structure
ふりがな	きこうぞう
フリガナ	キコウゾウ

木のような形の構造のこと。
「根」（ルート）を元に、枝葉のように各要素が継ながっている構造を「木構造」もしくは「ツリー構造」と呼ぶ。
　
たとえば、クラスはObject クラスをルートに持ち、各サブクラスが枝葉のように継承されている。クラスの継承関係が木構造となっている。
その他、ディレクトリやファイルといったファイルシステムや、XML、HashMap クラスの実装等、木構造はよく使用される構造である。
　
にも関わらず、J2SEには木構造を格納するクラスが存在しない。
基本的には「一次元配列の入れ子構造」で実装できる。そのため、ArrayListをただ継なげていけば実装できる。だが、思いの外複雑になりやすいため、バグが生まれやすいので注意。たとえば下記の使用例では、要素がループするとtoString ()メソッドが終了せず無限ループ化する。こういった問題をクラス側で回避するのか使用者側で回避するのか、といった設計上の問題もある。
　
構造上、「一番上にルートがあり、その下に各要素が広がっている」というイメージを頭に描きやすいが、一応「木構造」は「根本から枝葉が伸びる」構造であり、「根本から根が伸びる構造」ではない点に注意。

参考サイト

（参考サイトはありません）

(KAB-studioからのおしらせです)

// Sample.java
import java.util.ArrayList;
import java.util.Iterator;

public class Sample
{
    public static void main( String[] args )
    {
        // 木構造を作ってみます。
        // こんな感じの木構造。
/*
[root]
|-[folder01]
| |-値1
|-[folder02]
| |-値1
| |-値2
*/
        // ルート要素。
        TreeFolder root = new TreeFolder( "root" );

        TreeFolder folder01 = new TreeFolder( "folder01" );
        folder01.add( new TreeValue( "値1" ) );
        root.add( folder01 );

        TreeFolder folder02 = new TreeFolder( "folder02" );
        folder02.add( new TreeValue( "値1" ) );
        folder02.add( new TreeValue( "値2" ) );
        root.add( folder02 );

        System.out.println( root.toString() );
        // [root]([folder01](値1),[folder02](値1,値2))
    }
}

/**
*   要素、つまり「フォルダ」と「値」の両方の元となるabstractクラス。
*   インスタンスを作れないようにabstractにしています。
*/
abstract class TreeElement
{
    /** 要素の「名前」。 */
    protected String name;

    /**
    *   コンストラクタ。
    */
    public TreeElement( String name )
    {
        this.name = name;
    }
}

/**
*   「フォルダ」要素クラス。
*   他の「フォルダ」もしくは「値」を格納します。
*/
class TreeFolder extends TreeElement
{
    /**
    *   子要素を格納するArrayListクラス。
    */
    private ArrayList children = new ArrayList();

    /**
    *   コンストラクタ。
    */
    public TreeFolder( String name )
    {
        super( name );
    }

    /**
    *   要素、つまり「フォルダ」もしくは「値」を追加します。
    */
    public void add( TreeElement element )
    {
        children.add( element );
    }

    /**
    *   持っている要素も含めて文字列化します。
    */
    public String toString()
    {
        StringBuffer strbuf = new StringBuffer();
        strbuf.append( "[" );
        strbuf.append( name );
        strbuf.append( "](" );

        for( Iterator iter = children.iterator(); iter.hasNext(); )
        {
            Object object = iter.next();
            strbuf.append( object.toString() );
            if( iter.hasNext() == true )
            {
                strbuf.append( "," );
            }
        }
        strbuf.append( ")" );

        return strbuf.toString();
    }
}

/**
*   「値」要素クラス。
*   「値」を格納します。
*/
class TreeValue extends TreeElement
{
    /**
    *   コンストラクタ。
    */
    public TreeValue( String value )
    {
        super( value );
    }

    /**
    *   文字列化します。
    */
    public String toString()
    {
        return name;
    }
}

// Sample.java
import java.util.ArrayList;
import java.util.Iterator;

public class Sample
{
    public static void main( String[] args )
    {
        // 木構造を作ってみます。
        // こんな感じの木構造。
/*
[root]
|-[folder01]
| |-値1
|-[folder02]
| |-値1
| |-値2
*/
        // ルート要素。
        TreeFolder root = new TreeFolder( "root" );

        TreeFolder folder01 = new TreeFolder( "folder01" );
        folder01.add( new TreeValue( "値1" ) );
        root.add( folder01 );

        TreeFolder folder02 = new TreeFolder( "folder02" );
        folder02.add( new TreeValue( "値1" ) );
        folder02.add( new TreeValue( "値2" ) );
        root.add( folder02 );

        System.out.println( root.toString() );
        // [root]([folder01](値1),[folder02](値1,値2))
    }
}

/**
*   要素、つまり「フォルダ」と「値」の両方の元となるabstractクラス。
*   インスタンスを作れないようにabstractにしています。
*/
abstract class TreeElement
{
    /** 要素の「名前」。 */
    protected String name;

    /**
    *   コンストラクタ。
    */
    public TreeElement( String name )
    {
        this.name = name;
    }
}

/**
*   「フォルダ」要素クラス。
*   他の「フォルダ」もしくは「値」を格納します。
*/
class TreeFolder extends TreeElement
{
    /**
    *   子要素を格納するArrayListクラス。
    */
    private ArrayList children = new ArrayList();
    
    /**
    *   コンストラクタ。
    */
    public TreeFolder( String name )
    {
        super( name );
    }

    /**
    *   要素、つまり「フォルダ」もしくは「値」を追加します。
    */
    public void add( TreeElement element )
    {
        children.add( element );
    }

    /**
    *   持っている要素も含めて文字列化します。
    */
    public String toString()
    {
        StringBuffer strbuf = new StringBuffer();
        strbuf.append( "[" );
        strbuf.append( name );
        strbuf.append( "](" );

        for( Iterator iter = children.iterator(); iter.hasNext(); )
        {
            Object object = iter.next();
            strbuf.append( object.toString() );
            if( iter.hasNext() == true )
            {
                strbuf.append( "," );
            }
        }
        strbuf.append( ")" );

        return strbuf.toString();
    }
}

/**
*   「値」要素クラス。
*   「値」を格納します。
*/
class TreeValue extends TreeElement
{
    /**
    *   コンストラクタ。
    */
    public TreeValue( String value )
    {
        super( value );
    }

    /**
    *   文字列化します。
    */
    public String toString()
    {
        return name;
    }
}

「みだし」に含まれているページ

「解説」に含まれているページ

「サンプルプログラムとか」に含まれているページ

users

update:2005/12/13

このページは、Javaプログラミング言語についての用語を網羅した辞書「JavaA2Z」の一ページです。
詳しくは「JavaA2Z」表紙の説明をご覧ください。