Template Class ArrayBinaryTree

Nested Relationships

Nested Types

Class Documentation

template<class T>
class ArrayBinaryTree

a binary tree in a positional vector

Public Types

using Item = T

the type of the values

Public Functions

ArrayBinaryTree(void) = default

the empty tree

explicit ArrayBinaryTree(const T &v)

a tree of one node of value v

ArrayBinaryTree(const T &v, const ArrayBinaryTree &l, const ArrayBinaryTree &r)

a new root of value v with copies of l and r as its subtrees

bool empty(void) const
long root(void) const

the root, NIL if the tree is empty

long parent(long i) const

the parent of i, NIL for the root

Pre:

i is a node

long left(long i) const

the left child of i, NIL if there is none

Pre:

i is a node

long right(long i) const

the right child of i, NIL if there is none

Pre:

i is a node

bool isLeaf(long i) const
Pre:

i is a node

const T &read(long i) const
void write(long i, const T &v)
void setRoot(const T &v)

the root of value v of the empty tree

void insertLeft(long i, const ArrayBinaryTree &t)

a copy of t as the left subtree of i, which must be missing; t may be this tree, copied as it was before the call

void insertRight(long i, const ArrayBinaryTree &t)

a copy of t as the right subtree of i, which must be missing; t may be this tree, copied as it was before the call

void remove(long i)

empties the subtree of i

std::vector<long> preorder(void) const

the places of the nodes in preorder

inline auto nodes(void) const

the nodes, in the order of their places, bidirectional

Public Static Attributes

static constexpr long NIL = -1
struct Used

the places in use, for SlotIterator

Public Static Functions

static inline std::size_t size(const auto &o)
static inline bool occupied(const auto &o, std::size_t i)
static inline long read(const auto&, std::size_t i)