41.2.6.3 Post–order iterations

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

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

the post–order iteration is:

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

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-post-order-forwards kons knil root

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

Like fold-left for lists, visit the nodes of a binary tree with a post–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-post-order-forwards root

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

Perform the first step in a post–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-post-order-forwards bnode

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

Advance an post–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-post-order-backwards kons knil root

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

Like fold-right for lists, visit the nodes of a binary tree with a post–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-post-order-backwards root

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

Perform the first step in a post–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-post-order-backwards bnode

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

Advance an post–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.