Crate flat_tree

Series of functions to map a binary tree to a list

You can represent a binary tree in a simple flat list using the following structure:

                                    15
              7                                             23
      3                 11                      19                      27
  1       5        9          13          17          21          25          29
0   2   4   6   8    10    12    14    16    18    20    22    24    26    28    30...

Each number represents an index in a flat list. So a tree:

      A
  B       C
D   E   F   G  ...

would be represented as a list: [D B E A F C G]

Furthermore, indexes 0, 2, 4, 6 are on depth 0. 1, 5, 9 on depth 1. And so forth.

depth = 2  ^        3
depth = 1  |    1       5
depth = 0  |  0   2   4   6  ...

In some cases it is also useful to calculate an offset. Indexes 0, 1, 3, 7 have an offset 0:

                (7)
       (3)
  (1)       5
(0)   2   4   6      ...

2, 5, 11, 23 offset 1:

                 7
       3                  (11)
  1        (5)        9          13
0   (2)   4   6    8    10    12    14

This module exposes a series of functions to help you build and maintain this data structure.

Structs

• Iterator
  Iterator over a flat-tree.

Functions

• children
  Returns both children of a node.
• count
  Returns how many nodes are in the tree that the node spans.
• count_leaves
  Returns how many leaves are in the tree that the node spans.
• depth
  Returns the depth of a node.
• full_roots
  Returns a list of all the full roots (subtrees where all nodes have either 2 or 0 children) < index.
• index
  Returns the flat-tree of the tree node at the specified depth and offset.
• left_child
  Returns only the left child of a node.
• left_span
  Returns the left most node in the tree that it spans.
• offset
  Returns the offset of a node.
• parent
  Returns the parent of a node with a depth.
• right_child
  Returns only the left child of a node.
• right_span
  Returns the right most node in the tree that the node spans.
• sibling
  Returns the sibling of a node.
• spans
  Returns the left and right most nodes in the tree that the node spans.
• uncle
  Returns the parent’s sibling, of a node.