41.2.6.2 Pre–order iterations

Pre–order iteration: visit the current node then the left child then the right child. As example, given the tree:

5-------10----12
|        |     |
1--3--4  7--9 11
   |     |  |
   2     6  8

the pre–order iteration is:

forward:    5,  1,  3,  2,  4, 10,  7,  6,  9,  8, 12, 11
backward:   5, 10, 12, 11,  7,  9,  8,  6,  1,  3,  4,  2

the forwards iteration is a “worm that always turns right”, while the backwards iteration is a “worm that always turns left”.

The following syntactic bindings are exported by the library (vicare containers binary-search-trees). The bindings whose name is prefixed with $ are unsafe operations: they do not validate their arguments before accessing them.

Forwards iteration

Function: binary-tree-fold-pre-order-forwards kons knil root

Function: $binary-tree-fold-pre-order-forwards kons knil root

Like fold-left for lists, visit the nodes of a binary tree with a pre–order forwards iteration. The argument root must be #f to represent an empty tree or an instance of <binary-node> representing the root of a tree.

Function: binary-tree-begin-pre-order-forwards root

Function: $binary-tree-begin-pre-order-forwards root

Perform the first step in a pre–order forwards iteration. The argument root must be #f to represent an empty tree or an instance of <binary-node> representing the root of a tree. If the tree is empty: return #f; otherwise return an instance of <binary-node> representing the first visited node.

Function: binary-tree-step-pre-order-forwards bnode

Function: $binary-tree-step-pre-order-forwards bnode

Advance an pre–order forwards iteration by one step starting from bnode, which must be an instance of <binary-node>. If bnode is the last in the iteration: return #f; otherwise return an instance of <binary-node> representing the next visited node.

Backwards iteration

Function: binary-tree-fold-pre-order-backwards kons knil root

Function: $binary-tree-fold-pre-order-backwards kons knil root

Like fold-right for lists, visit the nodes of a binary tree with a pre–order backwards iteration. The argument root must be #f to represent an empty tree or an instance of <binary-node> representing the root of a tree.

Function: binary-tree-begin-pre-order-backwards root

Function: $binary-tree-begin-pre-order-backwards root

Perform the first step in a pre–order backwards iteration. The argument root must be #f to represent an empty tree or an instance of <binary-node> representing the root of a tree. If the tree is empty: return #f; otherwise return an instance of <binary-node> representing the first visited node.

Function: binary-tree-step-pre-order-backwards bnode

Function: $binary-tree-step-pre-order-backwards bnode

Advance an pre–order backwards iteration by one step starting from bnode, which must be an instance of <binary-node>. If bnode is the last in the iteration: return #f; otherwise return an instance of <binary-node> representing the next visited node.