JavaA2Z

KAB-studio > プログラミング > JavaA2Z > 木構造とは

木構造

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

解説

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

参考サイト

  • (参考サイトはありません)

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

サンプルプログラム(とか)サンプルを別ウィンドウで表示サンプルをクリップボードへコピー(WindowsでIEの場合のみ)

// 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;
    }
}

この単語を含むページ

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

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

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

はてなブックマーク 詳細を表示 はてなブックマーク ブックマーク数
livedoorクリップ 詳細を表示 livedoorクリップ ブックマーク数
Yahoo!ブックマーク 詳細を表示 users
del.icio.us 登録する RSSに登録
サンプルを別ウィンドウで表示
サンプルをクリップボードへコピー(WindowsでIEの場合のみ)
update:2005/12/13
このページは、Javaプログラミング言語についての用語を網羅した辞書「JavaA2Z」の一ページです。
詳しくは「JavaA2Z」表紙の説明をご覧ください。