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:

• If the tree is empty: return #f and #f.
• If the tree is not empty: return an object representing the state of the iteration and an instance of <binary-node> representing the first visited node.

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:

• If the iteration is over: return #f and #f.
• If the iteratio is not over: return an object representing the state of the iteration and an instance of <binary-node> representing the next visited node.

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:

• If the tree is empty: return #f and #f.
• If the tree is not empty: return an object representing the state of the iteration and an instance of <binary-node> representing the first visited node.

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:

• If the iteration is over: return #f and #f.
• If the iteratio is not over: return an object representing the state of the iteration and an instance of <binary-node> representing the next visited node.