I've had to come up with a traversal order/algorithm for a project, and I am wondering if it has a name.
The requirements of the algorithm are:
- it visits the parent before the children.
- it visits all the children in one group.
- it is otherwise depth-first.
I basically modified a pre-order to visit the siblings all together, before going down to the child of the first sibling. Note that this is not breadth-first.
Here is an example of the traversal order:
As you can see, in this tree, the traversal would be
H, D, L, B, F, A, C, E, G, J, N, I, K, M, O, and grouping for siblings:
(H), (D, L), (B, F), (A, C), (E, G), (J, N), (I, K), (M, O).
Some things to ponder:
- I think one can also view this as a pre-order traversal of the "dual" of this tree, where the dual nodes are representative of each group of siblings.
- Notice the z-shapes. It is like a "z-order-traversal", an analog to a z-order-curve, but for tree traversal. It has the similar property of traversing children together, just like a z-order curve will visit the siblings of the finest level of a full quadtree.
So, what is the name of this traversal order?