/flat-tree

A series of functions to map a binary tree to a list

Primary LanguageC++MIT LicenseMIT

SYNOPSIS

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

USAGE

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

TEST

build test

USAGE

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

EXAMPLE

#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;
}

SEE ALSO

LICENSE

MIT