Tree traversal: Difference between revisions
Content added Content deleted
| Line 2,522: | 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>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 |
<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). |
||
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): |
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): |
||