糸付き2分木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/14 05:46 UTC 版)
「木構造 (データ構造)」の記事における「糸付き2分木」の解説
また、糸付き2分木（英語版） (英: threaded binary tree) を使う方法もある。Joseph M. Morris が1979年に発表した。糸付き2分木は、子ノードがない場合に間順の前と後ろをそれぞれ左の子ポインタと右の子ポインタに設定しておいた木構造である。この場合、子ノードの有無はポインタ以外のフィールドで示す必要がある。これを使うと、間順走査の効率が非常によくなるが、前順や後順は通常のスタックを使った実装の方がよい。 糸付き2分木を間順走査するコードは次のようになる。 Sub inorder(n∈node) Do While hasLeftChild(n) Let node ← node.left Loop Do visit(n) If hasRightChild(n) Then Let n ← n.right Do While hasLeftChild(n) Let n ← n.left Loop Else Let n ← n.right End If Loop While n ≠ NullEnd Sub
※この「糸付き2分木」の解説は、「木構造 (データ構造)」の解説の一部です。
「糸付き2分木」を含む「木構造 (データ構造)」の記事については、「木構造 (データ構造)」の概要を参照ください。
ウィキペディア小見出し辞書の「糸付き2分木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 糸付き2分木のページへのリンク
