Template Class PreorderArrayTree

Defined in File PreorderArrayTree.h

Nested Relationships

Nested Types

Struct PreorderArrayTree::Cell

Class Documentation

template<class T> class PreorderArrayTree

an ordered tree in a vector of ( parent , value ) in preorder

Public Types

using Item = T : the type of the values

Public Functions

PreorderArrayTree(void) = default

explicit PreorderArrayTree(const T &v): a tree of one node of value v

bool empty(void) const

int size(void) const

int root(void) const

int parent(int i) const

const T &read(int i) const

void write(int i, const T &v)

int leftmostChild(int i) const: the first child, i + 1 if its parent is i

int rightSibling(int i) const: the next sibling, the place after the subtree of i if it has the same parent

bool isLeaf(int i) const

int subtreeEnd(int i) const: the place after the subtree of i

void insertChild(int i, const PreorderArrayTree &t): a copy of t as the first child of i; t may be this tree, copied as it was before the call

void insertSibling(int i, const PreorderArrayTree &t): a copy of t as the next sibling of i, not the root; t may be this tree, copied as it was before the call

void remove(int i): removes the subtree of i

auto values(void) const: the values of the nodes in preorder, which is the order of the array, random access

Public Static Attributes

static constexpr int NIL = -1