A series of functions to map a binary tree to a list. This is a port of this library and matches the tests.

This module is designed to work with the datcxx build tool. To add this module to your project us the following command...

build add datcxx/flat-tree

build test

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

        3
    1       5
  0   2   4   6  ...

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

      A
  B       C
D   E   F   G  ...

...is represented as a list: [D B E A F C G].

Indexes 0, 2, 4, 6 are on depth 0. 1, 5, 9 on depth 1.

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    10   12    14    15

#include "index.hxx"
#include <vector>
#include <string>

std::vector<std::string> list(4);

auto i = flatTree::index(0, 0); // get array index for depth: 0, offset: 0
auto j = flatTree::index(1, 0); // get array index for depth: 2, offset: 0

// use these indexes to store some data

list[i] = "a";
list[j] = "b";

auto p = flatTree::parent(j);
list[p] = "parent of a and b";

for (const auto& i: list) {
  std::cout << i << ' ' << std::endl;
}

• mafintosh/flat-tree: A series of functions to map a binary tree to a list.

• mafintosh/print-flat-tree: A cli that can pretty print flat-trees.

• datrs/flat-tree: A port of the node module to rust.

• bcomnes/flattree: A port of the node module to Go.

MIT