Next: , Previous: , Up: bst bnodes iterating   [Index]


41.2.6.5 Breadth–first iterations

Breadth–first iteration: visit the tree level by level. Example:

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

the order of the forwards iteration is: 5, 1, 10, 3, 7, 12, 2, 4, 6, 9, 11, 8. To do it we need a moving cursor that always “turns right” keeping the count of the level. The order of the backwards iteration is: 5, 10, 1, 12, 7, 3, 11, 9, 6, 4, 2, 8.

The implementation of the breadth–first iteration makes use, internally of a queue container. The API of this iteration is different from the one of the other iterations.

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-breadth-first-forwards kons knil root
Function: $binary-tree-fold-breadth-first-forwards kons knil root

Like fold-left for lists, visit the nodes of a binary tree with a breadth–first 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-breadth-first-forwards root
Function: $binary-tree-begin-breadth-first-forwards root

Perform the first step in a breadth–first 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. Return 2 values:

Function: binary-tree-step-breadth-first-forwards state
Function: $binary-tree-step-breadth-first-forwards state

Advance a breadth–first forwards iteration by one step; state must be the object representing the state of the iteration. Return 2 values:

Backwards iteration

Function: binary-tree-fold-breadth-first-backwards kons knil root
Function: $binary-tree-fold-breadth-first-backwards kons knil root

Like fold-left for lists, visit the nodes of a binary tree with a breadth–first 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-breadth-first-backwards root
Function: $binary-tree-begin-breadth-first-backwards root

Perform the first step in a breadth–first 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. Return 2 values:

Function: binary-tree-step-breadth-first-backwards state
Function: $binary-tree-step-breadth-first-backwards state

Advance a breadth–first backwards iteration by one step; state must be the object representing the state of the iteration. Return 2 values:


Next: , Previous: , Up: bst bnodes iterating   [Index]