|
木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。 == 用語 == 木構造は、ノード（節点、頂点）とノード間を結ぶエッジ（枝、辺）あるいはリンクで表される。 データ構造として使われる木は、ほとんどの場合、根となるノードが決められた根付き木で、ノード間の関係は家系図に見立てた用語で表現される。木構造内の各ノードは、0個以上の子ノード () を持ち、子ノードは木構造内では下方に存在する（木構造の成長方向は下とするのが一般的である）。子ノードを持つノードは、子ノードから見れば親ノード () である。あるノードから見て、同じ親を持つノードを兄弟ノード () という。あるノードから見て、その子ノードやそこから先の子ノード全てのいずれかを子孫ノード () と呼び、その親ノードやそこから先の親ノードの全てのいずれかを先祖ノード () と呼ぶ。ノードは高々1個の親ノードを持つ。 根ノード () とは、親ノードを持たないノードのこと。根ノードは木構造の最上位にあるノードであり、1つの木構造に高々1つしか存在しない。根ノードからスタートして、親から子へ、またその子へ、とエッジを辿っていくと、あらゆるノードへ必ず到達でき、そのような（根から特定ノードまでの）経路は常に一意である。図で示す場合、根ノードが一番上に描かれるのが普通である。二分ヒープなどの木構造では、根ノードは特別な属性を持つ。木構造内の全てのノードは、そのノードを頂点とする部分木の根ノードと見なすことができる。 葉ノード () とは、子ノードを持たないノードのこと。葉ノードは木構造の下位の末端にあるノードであり、ひとつの木に複数存在しうる。 内部ノード (、) とは、子ノードを持つノード、すなわち葉ノード以外のノードのこと。 高さ () とは、あるノードについて、そのノードからその子孫である葉ノードへのエッジ数の最大値のこと。 根ノードの高さはその木構造の高さである。 深さ () とは、逆に、あるノードについて、そのノードから根ノードまでのエッジ数のこと。根ノードの深さは 0 である。 部分木 () は、木構造の一部であり、それ自身も完全な木構造となっている部分を指す。木構造 ''T'' の任意のノードは、その配下の全ノードと共に ''T'' の部分木を構成する。根ノードを頂点とする部分木は、その木構造全体と等しい。根ノード以外を頂点とする部分木は真部分木 () と呼ばれる（部分集合と真部分集合とのアナロジー）。 森 () とは、木の集合のこと。グラフ理論では、森は閉路をもたない（連結とは限らない）グラフである。 森が順序木の順序集合である場合、これを木の木と考えることで前順、間順、後順の走査法を再帰的に定義できる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「木構造 (データ構造)」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Tree traversal 」があります。 スポンサード リンク
|