Template Class FullBinaryNode

Class Documentation

template<typename T>
class FullBinaryNode

Represents a node with data of T type in a full-binary tree.

A full binary tree is a binary tree in which each node has two children or no children.

Public Types

using node_ptr = std::unique_ptr<FullBinaryNode<T>>
using value_type = T

Public Functions

inline explicit FullBinaryNode(T d)

Construct an internal node with empty left and right nodes.

Parameters:

d – Data in the internal node.

inline FullBinaryNode(T d, T l, T r)

Construct an internal node with left and right node data.

Parameters:

  • d – Data in the internal node.

  • l – Data in the left node.

  • r – Data in the right node.

inline FullBinaryNode(T d, FullBinaryNode<T> l, FullBinaryNode<T> r)

Constructs an internal node with left and right nodes.

Parameters:

  • d – Data in the internal node.

  • l – Left node.

  • r – Right node

inline FullBinaryNode(T d, node_ptr &&l, node_ptr &&r)

Constructs an internal node with left and right node pointers.

Parameters:

  • d – Data in the internal node.

  • l – Left node pointer.

  • r – Right node pointer.

inline FullBinaryNode(FullBinaryNode<T> const &other)
inline FullBinaryNode &operator=(FullBinaryNode<T> const &other)
inline FullBinaryNode(FullBinaryNode<T> &&other)
inline FullBinaryNode &operator=(FullBinaryNode<T> &&node)
inline FullBinaryNode const &left() const
Returns:

Left node if this is an internal node, throws otherwise.

inline FullBinaryNode &left()
inline FullBinaryNode const &right() const
Returns:

Right node if this is an internal node, throws otherwise.

inline FullBinaryNode &right()
inline bool leaf() const

Check if the object is a leaf node.

Note

Left and right children are nullptr like

Returns:

True if this object represents a terminal binary node.

inline bool root() const

Check if the object is a root node.

Returns:

Whether this node represents the root in its respective tree

inline const FullBinaryNode<T> &parent() const

Note

This assumes that this object is not a root node

Returns:

The parent node

inline FullBinaryNode<T> &parent()

Note

This assumes that this object is not a root node

Returns:

The parent node

inline std::size_t size() const
Returns:

Size of the tree rooted at this node

inline T const &operator*() const
Returns:

Returns the data stored by the node.

inline T &operator*()
Returns:

Returns the data stored by the node.

inline T const *operator->() const
Returns:

Returns the pointer to the data stored by the node.

inline T *operator->()
Returns:

Returns the pointer to the data stored by the node.

template<typename Cont, typename F>
inline FullBinaryNode(Cont const &container, F &&binarize)

Left-fold a container to make a full-binary node.

Parameters:

  • container – To be binarized.

  • binarize – Fold function. binarize needs to support:

    • unary function call with a return value (say of type R) to the element type of the container (say of type V)

    • binary function call of kind f(R,V) that returns R type

template<typename F>
inline void visit(F &&visitor, TreeTraversal order = TreeTraversal::PreOrder) const

Visit the tree in the order specified by the order argument.

Template Parameters:

F – Type of the visitor.

Parameters:

  • visitor – Visitor to be invoked on each node. The visitor can optionally return a value convertible to bool to indicate whether the subtree of the current node shall be explored.

  • order – Tree traversal order(s) to invoke the visitor for.

template<typename F>
inline void visit(F &&visitor, TreeTraversal order = TreeTraversal::PreOrder)
template<typename F>
inline void visit_internal(F &&visitor, TreeTraversal order = TreeTraversal::PreOrder) const

Visit the internal nodes of the tree in the order specified by the order argument.

Template Parameters:

F – Type of the visitor.

Parameters:

  • visitor – Visitor to be invoked on each node. The visitor can optionally return a value convertible to bool to indicate whether the subtree of the current node shall be explored.

  • order – Tree traversal order(s) to invoke the visitor for.

template<typename F>
inline void visit_internal(F &&visitor, TreeTraversal order = TreeTraversal::PreOrder)
template<typename F>
inline void visit_leaf(F &&visitor, TreeTraversal order = TreeTraversal::PreOrder) const

Visit the leaf nodes of the tree in the order specified by the order argument.

Template Parameters:

F – Type of the visitor.

Parameters:

  • visitor – Visitor to be invoked on each node. The visitor can optionally return a value convertible to bool to indicate whether the subtree of the current node shall be explored.

  • order – Tree traversal order(s) to invoke the visitor for.

template<typename F>
inline void visit_leaf(F &&visitor, TreeTraversal order = TreeTraversal::PreOrder)
template<typename F, typename String = std::invoke_result_t<F, FullBinaryNode>>
inline String digraph(F label_gen, std::basic_string_view<typename String::value_type> graph_name = {}) const
template<typename L, typename String = std::invoke_result_t<L, FullBinaryNode>, typename S = std::function<String(FullBinaryNode)>>
inline String tikz(L label_gen, S spec_gen = [](auto &&) { return String{};}) const

Note

Make sure the following are present in the preamble. 

             @c \usepackage{tikz}
             @c \usetikzlibrary{graphs,graphdrawing}
             @c \usegdlibrary{trees}

Parameters:

  • label_gen – Generates the label for tikz nodes.

  • spec_gen – Generates the node spec that goes into the square bracket of tikz node statement.

Returns:

TikZ graph.