A series of functions to map a binary tree to a list
npm install flat-tree
You can represent a binary tree in a simple flat list using the following structure
3
1 5
0 2 4 6 ...
This module exposes a series of functions to help you build and maintain this data structure
var tree = require('flat-tree')
var list = []
var i = tree.index(0, 0) // get array index for depth: 0, offset: 0
var j = tree.index(1, 0) // get array index for depth: 1, offset: 0
// use these indexes to store some data
list[i] = 'a'
list[j] = 'b'
list[tree.parent(i)] = 'parent of a and b'
Returns an array index for the tree element at the given depth and offset
Returns the index of the parent element in tree
Returns the index of this elements sibling
Returns an array [leftChild, rightChild]
with the indexes of this elements children.
If this element does not have any children it returns null
Returns the range (inclusive) the tree root at index
spans.
For example tree.spans(3)
would return [0, 6]
(see the usage example).
Returns the left spanning in index in the tree index
spans.
Returns the right spanning in index in the tree index
spans.
Returns how many nodes (including parent nodes) a tree contains
Returns the depth of an element
Returns the relative offset of an element
Returns a list of all the full roots (subtrees where all nodes have either 2 or 0 children) <
index.
For example fullRoots(8)
returns [3]
since the subtree rooted at 3
spans 0 -> 6
and the tree
rooted at 7
has a child located at 9
which is >= 8
.
Create a stateful tree iterator starting at a given index. The iterator exposes the following methods.
Move the iterator the next item in the tree.
Move the iterator the prev item in the tree.
Move the iterator the this specific tree index.
Move the iterator to the current parent index
Move the iterator to the current left child index.
Move the iterator to the current right child index.
Move the iterator to the current left span index.
Move the iterator to the current right span index.
Is the iterator at a left sibling?
Is the iterator at a right sibling?
Move the iterator to the current sibling
- datrs/flat-tree: A port of the node module to rust.
- mafintosh/print-flat-tree: A cli that can pretty print flat-trees.
- bcomnes/flattree: A port of the node module to Go.
MIT