Content deleted Content added
m Added {{anchor|}} |
|||
Line 35:
:{{font color|red|F}}-{{font color|red|B}}-{{font color|red|A}}-{{font color|green|A}}-{{font color|#2A7FFF|A}}-{{font color|green|B}}-{{font color|red|D}}-{{font color|red|C}}-{{font color|green|C}}-{{font color|#2A7FFF|C}}-{{font color|green|D}}-{{font color|red|E}}-{{font color|green|E}}-{{font color|#2A7FFF|E}}-{{font color|#2A7FFF|D}}-{{font color|#2A7FFF|B}}-{{font color|green|F}}-{{font color|red|G}}-{{font color|green|G}}-{{font color|red| I}}-{{font color|red|H}}-{{font color|green|H}}-{{font color|#2A7FFF|H}}-{{font color|green| I}}-{{font color|#2A7FFF| I}}-{{font color|#2A7FFF|G}}-{{font color|#2A7FFF|F}}
===={{anchor|Preorder traversal|Pre-order traversal}}Pre-order, NLR====
# Visit the current node (in the figure: position red).
# Recursively traverse the current node's left subtree.
Line 42:
The pre-order traversal is a [[Topological sorting|topologically sorted]] one, because a parent node is processed before any of its child nodes is done.
===={{anchor|Postorder traversal|Post-order traversal}}Post-order, LRN====
# Recursively traverse the current node's left subtree.
# Recursively traverse the current node's right subtree.
Line 49:
Post-order traversal can be useful to get postfix expression of a [[binary expression tree]].
===={{anchor|Inorder traversal|In-order traversal}}In-order, LNR====
# Recursively traverse the current node's left subtree.
# Visit the current node (in the figure: position green).
Line 56:
In a [[binary search tree]] ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ''ascending'' sorted order.<ref>{{cite web |url=https://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf |website=[[UCLA]] Math |last=Wittman |first=Todd |access-date=January 2, 2016 |title=Tree Traversal |url-status=dead |archive-url=https://web.archive.org/web/20150213195803/http://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf |archive-date=February 13, 2015 }} </ref>
===={{anchor|Reverse preorder traversal|Reverse pre-order traversal}}Reverse pre-order, NRL====
# Visit the current node.
# Recursively traverse the current node's right subtree.
# Recursively traverse the current node's left subtree.
===={{anchor|Reverse postorder traversal|Reverse post-order traversal}}Reverse post-order, RLN====
# Recursively traverse the current node's right subtree.
# Recursively traverse the current node's left subtree.
# Visit the current node.
===={{anchor|Reverse inorder traversal|Reverse in-order traversal}}Reverse in-order, RNL====
# Recursively traverse the current node's right subtree.
# Visit the current node.
Line 103:
==Implementations==
{{unreferenced section|date=June 2013}}
===Depth-first search implementation===
{|
|- style="vertical-align:top;"
Line 131 ⟶ 132:
===={{anchor|Post-order traversal code|Post-order traversal code}}Post-order implementation====
{|
|- style="vertical-align:top"
Line 160 ⟶ 161:
|}
===={{anchor|Inorder traversal code|In-order traversal code}}In-order implementation====
▲{{anchor|Inorder traversal|In-order traversal}}
{|
|- style="vertical-align:top;"
Line 184 ⟶ 185:
|}
====
If the tree is represented by an array (first index is 0), it is possible to calculate the index of the next element:<ref>{{Cite web|title=constexpr tree structures|url=https://fekir.info/post/constexpr-tree/#_dfs_traversal|access-date=2021-08-15|website=Fekir's Blog|date=9 August 2021|language=en}}</ref>{{clarify|reason=Explicitly mention the restrictions on trees in order to be handled by this algorithm. Since there is no isLeaf() test, it seems that all leaves must be on maximal depth or one level above it, like in a [[heap (data structure)]].|date=November 2021}}
| |||