Content deleted Content added
m while the breadth-first search is easily implemented via a queue, Tags: Manual revert Reverted Visual edit Mobile edit Mobile web edit |
|||
Line 11:
Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node (it is not a linear data structure), then, assuming sequential computation (not parallel), some nodes must be deferred—stored in some way for later visiting. This is often done via a [[Stack (abstract data type)|stack]] (LIFO) or [[Queue (abstract data type)|queue]] (FIFO). As a tree is a self-referential (recursively defined) data structure, traversal can be defined by [[recursion]] or, more subtly, [[corecursion]], in a natural and clear fashion; in these cases the deferred nodes are stored implicitly in the [[call stack]].
Depth-first search is easily implemented via a stack, including recursively (via the call stack), while the breadth-first search is easily implemented via a queue, including corecursively.<ref name="Pfaff">{{cite book|last1=Pfaff|first1=Ben|title=An Introduction to Binary Search Trees and Balanced Trees|date=2004|publisher=Free Software Foundation, Inc.}}</ref>{{rp|45−61}}
===Depth-first search===
| |||