木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。木構造は、ノード（節点、頂点）とノード間を結ぶエッジ（枝、辺）あるいはリンクで表される。データ構造として使われる木は、ほとんどの場合、根となるノードが決められた根付き木で、ノード間の関係は家系図に見立てた用語で表現される。木構造内の各ノードは、0個以上の子ノード () を持ち、子ノードは木構造内では下方に存在する（木構造の成長方向は下とするのが一般的である）。子ノードを持つノードは、子ノードから見れば親ノード () である。あるノードから見て、同じ親を持つノードを兄弟ノード () という。あるノードから見て、その子ノードやそこから先の子ノード全てのいずれかを子孫ノード () と呼び、その親ノードやそこから先の親ノードの全てのいずれかを先祖ノード () と呼ぶ。ノードは高々1個の親ノードを持つ。根ノード () とは、親ノードを持たないノードのこと。根ノードは木構造の最上位にあるノードであり、1つの木構造に高々1つしか存在しない。根ノードからスタートして、親から子へ、またその子へ、とエッジを辿っていくと、あらゆるノードへ必ず到達でき、そのような（根から特定ノードまでの）経路は常に一意である。図で示す場合、根ノードが一番上に描かれるのが普通である。二分ヒープなどの木構造では、根ノードは特別な属性を持つ。木構造内の全てのノードは、そのノードを頂点とする部分木の根ノードと見なすことができる。葉ノード () とは、子ノードを持たないノードのこと。葉ノードは木構造の下位の末端にあるノードであり、ひとつの木に複数存在しうる。内部ノード (、) とは、子ノードを持つノード、すなわち葉ノード以外のノードのこと。高さ () とは、あるノードについて、そのノードからその子孫である葉ノードへのエッジ数の最大値のこと。根ノードの高さはその木構造の高さである。深さ () とは、逆に、あるノードについて、そのノードから根ノードまでのエッジ数のこと。根ノードの深さは 0 である。部分木 () は、木構造の一部であり、それ自身も完全な木構造となっている部分を指す。木構造 "T" の任意のノードは、その配下の全ノードと共に "T" の部分木を構成する。根ノードを頂点とする部分木は、その木構造全体と等しい。根ノード以外を頂点とする部分木は真部分木 () と呼ばれる（部分集合と真部分集合とのアナロジー）。森 () とは、木の集合のこと。グラフ理論では、森は閉路をもたない（連結とは限らない）グラフである。森が順序木の順序集合である場合、これを木の木と考えることで前順、間順、後順の走査法を再帰的に定義できる。木構造は2種類に分類される。順序性のない木と、順序性のある木である。順序性のない木は、構造的には木だが、あるノードの子ノード群には順序が存在しない。順序性のある木では、子ノードをリストに入れたり、各エッジ（枝）に異なる自然数を付与するなどして子ノード間に順序性をつける。これを順序木 () と呼ぶ。一般に実際に使われるデータ構造としては順序木の方が典型的である。2分探索木は順序木の一種である。コンピュータで利用する場合にはいくつかの実装方法がある。典型的な実装としては、動的メモリ確保でノードを表す構造体の領域を確保し、ポインタで親ノードや子ノードを参照できるようにする。他にも、配列を使った実装（ポインタではなく、インデックスによって親子関係が決定される）などがある（例えば、二分ヒープ）。グラフ理論では、木とは非環状（ループを持たない）グラフを意味する。根付き木は、根として選ばれたノードを持つグラフである。この場合、エッジでつながれた2つのノードには親子関係が成り立つ。木構造の走査 () とは、木構造にある全ノードを一回ずつ体系的に調査する処理である。連結リストや1次元の配列のような線形性のあるデータ構造では、走査は普通は前から順番に行われる（後ろからたどる方法などもある）。木構造の走査には下記の方法などがある。以下のアルゴリズムは二分木に関するものだが、多分木にも応用可能である。現在のノードを調査し、その子ノードに対して同じことを繰り返す。従って、再帰呼び出しで容易に表現できる（ループでも実装可能）。走査法は、ノードを調査する順序によって以下の3つに分類される（いずれの方法も、根から探索を開始する）。 前順(n)これらの実装では、木構造の高さのぶんだけコールスタック領域を必要とする。平衡が保たれていない木では、これが深刻な問題となる場合もある。各ノードの親ノードの位置を覚えておくことでスタックを使わないようにもできる。下記はレベル順の擬似コード。また、 () を使う方法もある。Joseph M. Morris が1979年に発表した。糸付き2分木は、子ノードがない場合に間順の前と後ろをそれぞれ左の子ポインタと右の子ポインタに設定しておいた木構造である。この場合、子ノードの有無はポインタ以外のフィールドで示す必要がある。これを使うと、間順走査の効率が非常によくなるが、前順や後順は通常のスタックを使った実装の方がよい。糸付き2分木を間順走査するコードは次のようになる。木構造は主に以下のような用途で使われる

出典:wikipedia