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
-
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.
LICENSE
MIT