TreeScan

TreeScan[f,tree]

evaluates f applied to the data of each subtree of tree in turn.

TreeScan[f,tree,levelspec]

applies f to the data of subtrees on levels of tree specified by levelspec.

TreeScan[f,tree,levelspecelems]

applies f to the elements elems of subtrees on levels specified by levelspec.

TreeScan[f]

represents an operator form of TreeScan that can be applied to a tree.

Details and Options

  • Scanning a tree is also known as tree traversal or tree search. The subtrees can be visited in many different orders, including depth-first and breadth-first traversals.
  • Scanning a tree is typically used to carry out an operation on subtrees where the operation has a "side effect", such as making an assignment.
  • TreeScan allows a function to be applied to elements of subtrees on any range of levels in a Tree object.
  • TreeScan[f,tree] discards the results of applying f to the data of tree. Unlike TreeMap, TreeScan does not build up a new tree to return.
  • You can use Throw to exit from TreeScan.
  • Structural elements elem for levelspecelem include:
  • "Data"the data of the subtree
    "Children"the children of the subtree
    "Subtree"the subtree itself
    "ChildrenData"the data of the children
  • Additional elements include:
  • "OriginalData"the original data of the subtree
    "OriginalChildren"the original children of the subtree
    "OriginalSubtree"the original subtree
    "OriginalChildrenData"the original data of the children
    "Position"the position of the subtree
    "Index"the index of the subtree in the list of siblings
    "LevelPair"the non-negative and negative levels of the subtree
    "Level"the non-negative level of the subtree from the root
    "NegativeLevel"the negative level of the subtree from the leaves
  • TreeScan uses standard level specifications as in TreeLevel:
  • nlevels 1 through n
    Infinitylevels 1 through Infinity
    {n}level n only
    {n1,n2}levels n1 through n2
    Alllevels 0 through Infinity
    "Leaves"levels -1 only
    "NonLeaves"levels 0 through -2
  • The default value for levelspec in TreeScan is {0,Infinity}.
  • TreeScan traverses subtrees in a left-to-right, depth-first order, with children visited before their parents.
  • TreeScan[…,TreeTraversalOrderorder] allows visiting subtrees in different orders, such as depth-first and breadth-first traversals.
  • TreeScan[f][tree] is equivalent to TreeScan[f,tree].

Examples

open allclose all

Basic Examples  (5)

Scan the data in a tree:

Scan data up to the first level:

Scan the subtrees:

Supply the position as an additional argument:

Use the operator form of TreeScan:

Scope  (12)

Level Specifications  (5)

Scan all levels (default):

Scan levels 1 through 2:

Scan only on level 2:

Scan levels 0 through 2:

Scan all levels, starting at level 1:

Scan also level 0:

Negative levels:

Positive and negative levels can be mixed:

Scan the leaves:

Scan the non-leaves:

Elements  (7)

Scan the data (default):

Scan the original data:

Scan the subtrees:

Scan the original subtrees:

Scan the children:

Scan the original children:

Scan the data of the children:

Scan the original data of the children:

Supply the position as an additional argument:

Supply the index rather than the position:

Supply the level specifications as an additional argument:

Supply the level rather than both level specifications:

Supply the negative level rather than both level specifications:

Supply a sequence of elements as arguments:

Generalizations & Extensions  (1)

Throw works inside TreeScan:

Options  (3)

TreeTraversalOrder  (3)

By default, subtrees are visited in a depth-first order, with parents visited after their children:

Specify a top-down, right-to-left variant:

Visit subtrees in a breadth-first order, with nodes on the same level from the root visited before the nodes on the next level:

Visit subtrees in a leaves-first order, with nodes on the same level from the leaves visited before the nodes on the next level:

Properties & Relations  (4)

Children are visited before their parents:

TreeScan does the same as TreeMap but without returning a result:

Construct a tree from the heads in an expression:

TreeScan scans the data of subtrees of a tree:

Scan can scan the heads and leaves directly:

Use Sow and Reap to collect results:

Possible Issues  (1)

TreeScan by default starts at level 1, so does not apply the function to the whole tree:

Wolfram Research (2021), TreeScan, Wolfram Language function, https://reference.wolfram.com/language/ref/TreeScan.html (updated 2022).

Text

Wolfram Research (2021), TreeScan, Wolfram Language function, https://reference.wolfram.com/language/ref/TreeScan.html (updated 2022).

CMS

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

APA

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

BibTeX

@misc{reference.wolfram_2023_treescan, author="Wolfram Research", title="{TreeScan}", year="2022", howpublished="\url{https://reference.wolfram.com/language/ref/TreeScan.html}", note=[Accessed: 19-April-2024 ]}

BibLaTeX

@online{reference.wolfram_2023_treescan, organization={Wolfram Research}, title={TreeScan}, year={2022}, url={https://reference.wolfram.com/language/ref/TreeScan.html}, note=[Accessed: 19-April-2024 ]}