41.2.6.1 In–order iterations

Forwards in–order iteration: visit all the nodes from the leftmost to the rightmost. Backwards in–order iteration: visit all the nodes from the rightmost to the leftmost. As example, given the tree:

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

the inorder iteration is:

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

Here is an example of forwards and backwards in–order iteration using trees of fixnums as defined in the introduction (see bst intro):

(define root
  ;; 5-------10----12
  ;; |        |     |
  ;; 1--3--4  7--9 11
  ;;    |     |  |
  ;;    2     6  8
  (tree 5 1 3 2 4 10 7 12 6 9 8 11))

;;By reversing we return a list in which: the first item
;;is the sort key of the first node visited in the iteration.
(reverse
  (binary-tree-fold-in-order-forwards
      (lambda (knil node)
        (cons (<fixnum-node>-sort-key node) knil))
    '() root))
⇒ (1 2 3 4 5 6 7 8 9 10 11 12)

;;By reversing we return a list in which: the first item
;;is the sort key of the first node visited in the iteration.
(reverse
  (binary-tree-fold-in-order-backwards
      (lambda (node knil)
        (cons (<fixnum-node>-sort-key node) knil))
    '() root))
⇒ (12 11 10 9 8 7 6 5 4 3 2 1)

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

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

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

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

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

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

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

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

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

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

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

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

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