Tree traversal: Difference between revisions
m
→J: Alternate implementation
Line 2,522:
<code>reorder</code> is like indexing, except that it returns an equivalent tree (with the structural elements updated to maintain the original tree structure). The left argument for reorder should select the entire tree. Selecting partial trees is a more complex problem which needs specifications about how to deal with issues such as dangling roots and multiple roots. (Our abstraction here has no problem ''representing'' trees with multiple roots, but they are not relevant to this task.)
<code>childinds</code> extracts the child pointers which some of these results assume. This implementation assumes we are working with a binary tree (which is an explicit requirement of this task -- the parent node representation is far more general and can represent trees with any number of children at each node, but what would an "inorder" traversal look like with a trinary tree?).
Next, we define our "traversal" routines (actually, we are going a bit overboard here - we really only need to extract the data for this tasks's concept of traversal):
| |||