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 emtpy 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)
FullBinaryNode(FullBinaryNode<T>&&) = default
FullBinaryNode &operator=(FullBinaryNode<T>&&) = default
inline FullBinaryNode const &left() const
Returns:

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

inline FullBinaryNode const &right() const
Returns:

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

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 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, typename Order = PostOrder, std::enable_if_t<std::is_void_v<std::invoke_result_t<F, FullBinaryNode<T> const&>>, bool> = true>
inline void visit(F visitor, Order = {}) const

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

Template Parameters:

  • F – Type of the visitor.

  • Order – Type of the order. Can be PreOrder, InOrder or PostOrder. By default it is PostOrder. That means parent node will be visited after visiting left and right children in that order.

Parameters:

visitor – Visitor to be invoked on each node.

template<typename F, std::enable_if_t<std::is_invocable_r_v<bool, F, FullBinaryNode<T> const&>, bool> = true>
inline void visit(F visitor) const

Visit the children nodes only if the visitor returns true upon visiting the parent node.

This is a pre-order traversal with short-circuit behavior.

Template Parameters:

F – Type of the visitor.

Parameters:

visitor – Visitor to be invoked on each node.

template<typename F, std::enable_if_t<std::is_invocable_r_v<bool, F, FullBinaryNode<T> const&>, bool> = true>
inline void visit_internal(F visitor) const

Visit the children nodes only if the visitor returns true upon visiting the parent node, and current node is not a leaf node.

This is a pre-order traversal with short-circuit behavior.

Template Parameters:

F – Type of the visitor.

Parameters:

visitor – Visitor to be invoked on each node.

template<typename F, typename Order = PostOrder, std::enable_if_t<std::is_void_v<std::invoke_result_t<F, FullBinaryNode<T> const&>>, bool> = true>
inline void visit_internal(F visitor, Order = {}) const

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

Template Parameters:

  • F – Type of the visitor.

  • Order – Type of the order. Can be PreOrder, InOrder or PostOrder. By default it is PostOrder. That means parent node will be visited after visiting left and right children in that order.

Parameters:

visitor – Visitor to be invoked on each node.

template<typename F, typename Order = PostOrder, std::enable_if_t<std::is_void_v<std::invoke_result_t<F, FullBinaryNode<T> const&>>, bool> = true>
inline void visit_leaf(F visitor, Order = {}) const

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

Template Parameters:

  • F – Type of the visitor.

  • Order – Type of the order. Can be PreOrder, InOrder or PostOrder. By default it is PostOrder. That means parent node will be visited after visiting left and right children in that order.

Parameters:

visitor – Visitor to be invoked on each node.

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.