open-cpp-utils 0.0.1
|
Class for creating a directed tree. More...
#include <directed_tree.h>
Classes | |
class | breadth_first |
Breadth first traversal. More... | |
class | in_order |
In-order traversal. More... | |
class | post_order |
Post-order traversal. More... | |
class | pre_order |
Pre-order traversal. More... | |
class | traverser |
Visitor pattern for traversing the tree. More... | |
Public Types | |
using | data_type = T |
using | node = uint32_t |
using | node_queue = std::deque<node> |
Public Member Functions | |
directed_tree () | |
Default constructor, creates tree with empty root. | |
node | parent (node id) const |
Get the parent of a node. O(1) | |
node | first_child (node id) const |
Get the first child of a node. O(1) | |
node | prev_sibling (node id) const |
Get the previous sibling of a node. O(1) | |
node | next_sibling (node id) const |
Get the next sibling of a node. O(1) | |
node | left_most (node id) const |
Get the left most child of a node. O(log(n)) | |
uint32_t | depth (node id) const |
Get the depth of a node. | |
node | insert (const data_type &data, node p_id) |
Insert a node into the tree as a child of the provided node. | |
void | erase (node id) |
Erase a node in the tree. | |
data_type & | operator[] (node id) |
Getter for data associated with a node. | |
const data_type & | operator[] (node id) const |
Constant getter for data associated with a node. | |
template<typename O = pre_order, typename V > | |
void | traverse (V &visitor) |
Traverser-Visitor pattern for accessing the tree. | |
Static Public Attributes | |
static constexpr constant_value< node, node(0)> | root {} |
Class for creating a directed tree.
T | Type of the data associated with each node |
The tree is a series of child nodes in forward linked lists.
|
inline |
Get the depth of a node.
id |
|
inline |
Erase a node in the tree.
id | Id of the node to erase |
|
inline |
Get the first child of a node. O(1)
id | Node id to reference |
|
inline |
Insert a node into the tree as a child of the provided node.
data | Value to insert |
p_id | Id of the parent node |
|
inline |
Get the left most child of a node. O(log(n))
id | Node id to reference |
|
inline |
Get the next sibling of a node. O(1)
id | Node id to reference |
|
inline |
Getter for data associated with a node.
id | Id of the node to access |
|
inline |
Constant getter for data associated with a node.
node | Id of the node to access |
|
inline |
Get the parent of a node. O(1)
id | Node id to reference |
|
inline |
Get the previous sibling of a node. O(1)
id | Node id to reference |
|
inline |
Traverser-Visitor pattern for accessing the tree.
V | Visitor type. |
O | Order type. Defaults to Pre-Order Traversal. |
visitor |