Content deleted Content added
Yabananaboy (talk | contribs) Tag: Reverted |
→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. |
||
| (6 intermediate revisions by 4 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 31 ⟶ 32:
The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited node. No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely. Given a tree with distinct elements, either pre-order or post-order paired with in-order is sufficient to describe the tree uniquely. However, pre-order with post-order leaves some ambiguity in the tree structure.<ref>{{cite web|url=https://cs.stackexchange.com/q/439 |title=Algorithms, Which combinations of pre-, post- and in-order sequentialisation are unique?, Computer Science Stack Exchange|access-date=2 May 2015}}</ref>
:{{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}}
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====
| |||