グラフ理論では、閉路のない連結グラフを木といいます。

グラフは辺(edge)で連結された頂点(vertex)の集合です。 辺は頂点の組で表されます。 組になる頂点に順序があれば有向グラフ、なければ無向グラフといいます。 ある頂点から他の頂点にいたる辺の列をパスといいます。 自分自身に戻ってくるパスが閉路(loop)です。 グラフに含まれる任意の２頂点にパスが存在する場合、連結グラフといいます。

右の図では、2-4-5-6-2 という閉路がありますが、このどこかを切れば木になります。

コンピュータ・サイエンスにおける木は、階層をもった節 (節点、ノード node)の集まりです。

階層は、ノードの親子関係で表現されます。 木には根(root)と呼ばれる親のないノードが１つあります。それ以外のノードには親が１つあります。 各ノードには、子ノードがなくても、いくつあってもかまいません。 子のないノードを葉(leaf)と呼びます。

木を図示する場合、親ノードを上に、子ノードを下に書き、線（枝という）で結びます。 したがって根が上に、葉が下になります。

右の図では、オレンジ色のノードが根、空色のノードが葉です。

ノードから根までの段数（枝の数）をそのノードの深さといいます。 深さの最大値を木の高さといいます。 右の図の木の高さは３です。

木の形やノード間の制約によって様々に分類されます。

• ｎ進木、２進木、２分木
  ノードの持つ子の個数での分類です。 ノードが高々ｎ個の子を持つ木をｎ進木あるいはｎ分木（n-ary tree）といいます。
  特に２分木（binary tree）がよく使われます。
  
  
• 順序木
  ノード間に順序がある木を順序木（ordered tree）といいます。 よく使われるのは次の２つです。
  • ２分探索木 binary search tree
    各ノードに値を持ち、

    左の子の値 ＜ 自ノードの値 ≦ 右の子の値

    となっている２分木を２分探索木といいます。 ノードの左側にぶら下がる木を左部分木、右側を右部分木と呼びます。
  • ヒープ
    木の種類としてヒープという場合は、 ノードの値と子の値の間に大小関係が成立している２分木のことです。

    自ノードの値 ≦ 子の値　  の場合と
    自ノードの値 ≧ 子の値　  の場合があります。

    前者では根に最小値が、後者は最大値があります。
  
  
  
• バランス木（平衡木）
  ノードの深さに制約のある木をバランス木とか平衡木といいます。
  • 完全２分木 perfect binary tree / complete binary tree
    全てのノードに２つずつの子をもつ２分木。 complete binary tree には別の定義がされることがあり、 この場合は全ての葉の深さの差が１以下の２分木を指します。
  • ＡＶＬ木（平衡２分木）
    どのノードにおいても、左右の部分木の高さが高々１しか違わない２分木。 ３人の考案者(Adelson-Velskii-Landis)の頭文字からＡＶＬ木と呼ばれます。 挿入・削除によってバランスが崩れた場合、 ２つのノードあるいは３つのノードに注目して高々２回の ローテーション を行うことで左右のバランスを取り戻すことができます。 この操作は最悪、葉から根まで伝播して終わります。
  • ２−３−４木
    
  • 赤黒木（２色木）
    
  • Ｂ木
    

• 走査 traversal
  全ノードの数え上げる enumeration ことを、木の走査 traversal とか walk といいます。 全部のノードを順に１回ずつたどることです。深さ優先と幅優先があります。 深さ優先の走査は、ノードの処理のタイミングによって次の３種があります。
  • pre-order (前走査、行きがけ順)
  • in-order (中走査、通りがかり順)
  • post-order (後走査、帰りがけ順)
• 検索 search
  探索ともいいます。 特定の値をもったノードを探すことです。 数え上げと同様に２種の方法があります。 縦型探索が普通です。
  • 深さ優先探索 depth first search
    
  • 幅優先 breadth first search
• 挿入 insert 、追加 add
  指定されたノードを木の制約に従って、 しかるべき位置に追加します。
• 削除 delete
  特定のノードを木から取り除きます。 順序木など、木の構造に制約がある場合は木の変形を伴います。
• 刈り込み pruning
  部分木（あるノードから下全部）を取り除きます。 場合わけを木で表現してしらみつぶしに数え上げる（走査）するような場合、 探す必要のなくなった部分木をうまく「刈り込」めるような木にすることが重要です。
• ローテーション rotate
  ２分探索木のノードの順序を崩さずに、左右の部分木の高さを変更します。

• グラフ
  いままででてきた表示の例は、ノード(節)とアーク(線、矢印)を使った「グラフ」としての表示です。
  
• リスト
  ２分木の特殊な場合は、リストとして表現されます。
  

  グラフで表現すると右図のようになります。 カッコをつかって次のように表現する場合もあります。 (A  (B  C  D)  E  F  G)		あるいは
  			このビューは javax.swing.JTreeでサポートされます

• チャート
  
• 配列（表）
  
• ＸＭＬ