N進木の二分木表現
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/29 13:54 UTC 版)
一般に順序のある木 (ordered tree) と二分木との間に一対一対応関係をつけることができる。これはLISP言語で特に用いられるものである。順序木の中の任意のノードNを二分木のノードnと対応させる。nの左の子はNの最初の子である。Nの次の子はnの右の子m、その次のNの子はmの左の子、そのまた次のNの子はmの右の子、といった様に、次々に右に木を生やしていけばいい。 別の見方をすれば、これは順序木の各ノードの兄弟を次々に「右」フィールドを用いて連結した一種の連結リスト構造に格納し、最初の要素を「左」フィールドに入れたのと同じである。 {B,C,D,E,F,G}の6つの子を持つA（左）を二分木（右）で表現した例である。 二分木はオリジナルの木を斜に傾けて表現したと考えることもできる。左の黒い辺が「最初の子」、右の青い辺が「次の兄弟」を表す。左の木にある葉はLISPでは (((M N) H I) C D ((O) (P)) F (L)) のように表現されるだろう。これは計算機の中では右のように実装されているはずである。
※この「N進木の二分木表現」の解説は、「二分木」の解説の一部です。
「N進木の二分木表現」を含む「二分木」の記事については、「二分木」の概要を参照ください。
ウィキペディア小見出し辞書の「N進木の二分木表現」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- N進木の二分木表現のページへのリンク
