Content deleted Content added
Dirty-kebab (talk | contribs) m add missing null node check to iterative Post/In order |
→Types: Being bold and adding an interactive example of tree traversal. I think this is the sort of thing that's easier to think about if you can click through it step by step. |
||
| (10 intermediate revisions by 7 users not shown) | |||
Line 6:
==Types==
{{Tree traversal demo}}
Unlike [[linked list]]s, [[one-dimensional array]]s and other [[List of data structures#Linear data structures|linear data structures]], which are canonically traversed in linear order, trees may be traversed in multiple ways. They may be traversed in [[Depth-first search|depth-first]] or [[Breadth-first search|breadth-first]] order. There are three common ways to traverse them in depth-first order: in-order, pre-order and post-order.<ref name="holtenotes">{{cite web|url=http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html|title=Lecture 8, Tree Traversal|access-date=2 May 2015}}</ref> Beyond these basic traversals, various more complex or hybrid schemes are possible, such as [[depth-limited search]]es like [[iterative deepening depth-first search]]. The latter, as well as breadth-first search, can also be used to traverse infinite trees, see [[#Infinite trees|below]].
Line 103 ⟶ 104:
{{unreferenced section|date=June 2013}}
===Depth-first search implementation===
Below are examples of [[stack (abstract data type)|stack]]-based implementation for pre-order, post-order and in-order traversal in recursive approach (left) as well as iterative approach (right).
Implementations in iterative approach are able to avoid the [[Recursion (computer science)#Recursion versus iteration|drawbacks of recursion]], particularly limitations of stack space and performance issues.
Several alternative implementations are also mentioned.
===={{anchor|Pre-order traversal code|Pre-order traversal code}}Pre-order implementation====
Line 187 ⟶ 193:
|}
====Another variant of
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}}
| |||