TreeTraversalOrder

TreeTraversalOrder

TreeMapおよび関連関数のオプションで，部分木を訪れる順序を指定する．

詳細

  • 木の探索は木のスキャンとしても知られている．探索順はTreeMapやTreeScan等の関数で部分木を訪れる順序を指定する．
  • 探索順には，プレオーダー，インオーダー，ポストオーダー，深さ優先探索，幅優先探索を含むさまざまな種類や異形が存在する．
  • TreeTraversalOrderの一般的な設定は以下で与えられる．
  • Automaticデフォルトの探索順序を使う
    {tspec,vspec,hspec}基本順 tspec，垂直順 vspec，水平順 hspec
    spectspec，vspec，hspec の任意の部分集合（残りはデフォルト）
  • 次は，基本順序 tspec の設定である．
  • "DepthFirst"部分木全体を訪れ，次にその兄弟を訪れる
    "BreadthFirst","LevelOrder"根から始めレベルごとにノードを訪れる
    "LeavesFirst"葉から始めレベルごとにノードを訪れる
  • 次は，基本順序 tspec に関連する互いに素なノードの集合である．
  • 次は，垂直順序 vspec の設定である．
  • "TopDown","OuterInner","PreOrder"根から始めて子の前に親を訪れる
    "BottomUp","InnerOuter","PostOrder"葉から始めて親の前に子を訪れる
  • "DepthFirst" tspec の縦順 vspec の上記以外の設定には以下がある．
  • "InOrder"最初の子の後に親を訪ねる
  • 次は，水平順序 hspec の設定である．
  • "LeftRight"ノードを左から右に訪れる
    "RightLeft"ノードを右から左に訪れる
  • tspec が指定されていなければ"DepthFirst"が使われる．
  • vspec がAutomaticであるかあるいは指定されていない場合は，MapおよびScanの標準的な動作に従って"DepthFirst"には"BottomUp"が，tspec には"LeavesFirst"が使われる．"BreadthFirst" tspec には標準的な慣行に従って"TopDown"が使われる．
  • hspec が指定されていなければ"LeftRight"が使われる．

例題

すべて開くすべて閉じる

例  (3)

深さ優先探索で訪れられる順に木のノードに番号を振る：

幅優先探索を指定する：

基本探索のための垂直順を指定する：

スコープ  (18)

基本順  (14)

"DepthFirst"  (6)

深さ優先探索は，デフォルトで，左から右，下から上の順序でノードを訪れる：

プレオーダーで深さ優先探索を指定する：

インオーダーで深さ優先探索を指定する：

デフォルトでは，ポストオーダーで深さ優先探索が使われる：

最初の子の後に親を訪れる：

右から左の深さ優先探索を指定する：

デフォルトでは，左から右の深さ優先探索が使われる：

深さ優先探索の垂直と水平の順序を指定する：

深さ優先探索のすべての異形の格子を作る：

"BreadthFirst"  (4)

幅優先探索は根から始めてレベルごとにノードを訪れる：

"LevelOrder"に等しい：

下から上への幅優先探索を指定する：

デフォルトでは，上から下の順序が使われる：

幅優先探索の垂直と水平の順序を指定する：

幅優先探索のすべての異形の格子を作る：

"LeavesFirst"  (4)

葉優先探索は葉から始めてレベルごとにノードを訪れる：

上から下への葉優先探索を指定する：

デフォルトでは，下から上の順序が使われる：

葉優先探索の垂直と水平の順序を指定する：

葉優先探索のすべての異形の格子を作る：

垂直順  (2)

上から下への探索：

下から上への探索：

水平順  (2)

左から右への探索：

右から左への探索：

特性と関係  (5)

深さ優先，幅優先，葉優先の各探索の下から上への異体を比較する：

深さ優先，幅優先，葉優先の各探索の上から下への異体を比較する：

プレオーダーで深さ優先探索は位置の最も左で最も内側の順に相当する：

辞書順はまず位置を番号順に並べ，次に長さの降順に並べる：

幅優先探索は，位置の最も外側で最も左側の順に相当する：

正規順は，位置をまず長さ順にして次に番号順にする：

下から上へで左から右への探索は，上から下で右から下への探索の逆になる：

Wolfram Research (2021), TreeTraversalOrder, Wolfram言語関数， https://reference.wolfram.com/language/ref/TreeTraversalOrder.html （2024年に更新）.

テキスト

Wolfram Research (2021), TreeTraversalOrder, Wolfram言語関数， https://reference.wolfram.com/language/ref/TreeTraversalOrder.html （2024年に更新）.

CMS

Wolfram Language. 2021. "TreeTraversalOrder." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2024. https://reference.wolfram.com/language/ref/TreeTraversalOrder.html.

APA

Wolfram Language. (2021). TreeTraversalOrder. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/TreeTraversalOrder.html

BibTeX

@misc{reference.wolfram_2024_treetraversalorder, author="Wolfram Research", title="{TreeTraversalOrder}", year="2024", howpublished="\url{https://reference.wolfram.com/language/ref/TreeTraversalOrder.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_treetraversalorder, organization={Wolfram Research}, title={TreeTraversalOrder}, year={2024}, url={https://reference.wolfram.com/language/ref/TreeTraversalOrder.html}, note=[Accessed: 22-November-2024 ]}