DiscreteMath`Tree`

このパッケージでは，ネストされたリストとして表される木を作成，検索，表示するための関数を示す．木はデータ保存・操作のための効率的で基本的なツールなので，ここで定義される関数は他のいくつかのパッケージでも使われている．

木は，コンピュータサイエンスやその他の分野で，情報を編成するために使用される標準データ構造である．木の情報は，ルートノードから始まり，葉と呼ばれるターミナルノードで終わる各ノードに保存される．ノードは枝を介して他のノードとつながっている．葉とは枝のないノードのことである．最も一般的なタイプの木はバイナリツリーで，各ノードの枝の数は0本か1本である．

このパッケージでは，各ノードはexpr, n, , という形式を取る．ここでexpr はノードに保存される情報，n はノードに割り当てられる続き番号， と はノードに関連する枝である．葉はexpr, n, , として表され，枝は空リストである．

木の生成と検索

パッケージをロードする．

In[1]:= <<DiscreteMath`Tree`

以下は3つのノードを持つ単純な木構造である．ノード番号2がルートノードで項目e2を含んでいる．最初の枝はノード{{e1, 1}, {}, {}}で2番目の枝はノード{{e3, 3}, {}, {}}である．このどちらのノードも葉である．

In[2]:= MakeTree[{e1, e2, e3}]

Out[2]=

以下はノードに実数値を持つ木構造である．ルートノードにはリストの中央値である値5.46が含まれている．他のノードには小さい順に番号が付いている．

In[3]:= tree = MakeTree[{9.05, 6.48, 8.40, 5.46,
2.43, 4.46, 2.03}]

Out[3]=

この結果はノード番号5に6.5以下の最大値が含まれていることを示している．つまり，元のリストのうち5要素は6.5より小さいということである．

In[4]:= TreeFind[tree, 6.5]

Out[4]=

すべてのノードが指定された値よりも大きい場合は，ノード番号0が返される．

In[5]:= TreeFind[tree, 1.0]

Out[5]=

木の視覚的表現

木の構造を理解するためには，視覚的な表現が役に立つ．TreePlot関数はMakeTreeによって生成された木をグラフィックスとして表現する．より一般的に言えば，ほとんどのMathematica 式は，式の頭部が各ノードで式の引数が枝となっている木と考えることができる．関数ExprPlotは木とみなされる式のグラフィックス表現を生成する．

以下は10個のノードを持つ木の視覚的表現である．

In[6]:= TreePlot[MakeTree[Range[10]]]

Out[6]=

以下は，ネストされた関数を含む式の類似したプロットである．

In[7]:= ExprPlot[f[g[x, y, z], g[x, y, h[x, y]],
g[x, y]]]

Out[7]=