tpl_binNodeUtils.H File Reference

Utility functions for binary tree operations. More...

#include <ahFunction.H>
#include <tpl_arrayStack.H>
#include <tpl_arrayQueue.H>
#include <tpl_dynListQueue.H>
#include <bitArray.H>
#include <tpl_dynDlist.H>
#include <tpl_binNode.H>
#include <ah-errors.H>

Include dependency graph for tpl_binNodeUtils.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::For_Each_In_Order< Node >
	Generic inorder traversal of a binary tree. More...
class	Aleph::For_Each_Preorder< Node >
	Generic preorder traversal of a binary tree. More...
class	Aleph::For_Each_Postorder< Node >
	Generic postorder traversal of a binary tree. More...
class	Aleph::BinNodePrefixIterator< Node >
	Preorder iterator on the nodes of a binary tree. More...
class	Aleph::BinNodeInfixIterator< Node >
	Inorder iterator on the nodes of a binary tree. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Enumerations
enum	Aleph::ThreeWayCmp : int { Aleph::CmpLess = -1 , Aleph::CmpEqual = 0 , Aleph::CmpGreater = 1 }
	Constants for three-way comparison results. More...

Functions
template<class Node >
static void	Aleph::inorder_rec_helper (Node *node, const int &level, int &position, void(*visitFct)(Node *, int, int))
template<class Node >
int	Aleph::inOrderRec (Node *root, void(*visitFct)(Node *, int, int))
	Traverse recursively inorder a binary tree.
template<class Node >
static void	Aleph::preorder_rec_helper (Node *p, const int &level, int &position, void(*visitFct)(Node *, int, int))
template<class Node >
int	Aleph::preOrderRec (Node *root, void(*visitFct)(Node *, int, int))
	Traverse recursively in preorder a binary tree.
template<class Node >
static void	Aleph::postorder_rec_helper (Node *node, const int &level, int &position, void(*visitFct)(Node *, int, int))
template<class Node >
int	Aleph::postOrderRec (Node *root, void(*visitFct)(Node *, int, int))
	Traverse recursively in postorder a binary tree.
template<class Node , class Op >
void	Aleph::for_each_in_order (Node *root, Op &&op)
	Execute an operation in order sense for each node of tree.
template<class Node , class Op >
void	Aleph::for_each_preorder (Node *root, Op &&op)
	Execute an operation in preorder sense for each node of tree.
template<class Node , class Op >
void	Aleph::for_each_postorder (Node *root, Op &&op)
	Execute an operation in postorder sense for each node of tree.
template<class Node >
static void	Aleph::prefix (Node *root, DynList< Node * > &acc)
template<class Node >
static void	Aleph::infix (Node *root, DynList< Node * > &acc)
template<class Node >
static void	Aleph::suffix (Node *root, DynList< Node * > &acc)
template<class Node >
DynList< Node * >	Aleph::prefix (Node *root)
	Return a list with preorder traversal of a tree.
template<class Node >
DynList< Node * >	Aleph::infix (Node *root)
	Return a list with inorder traversal of a tree.
template<class Node >
DynList< Node * >	Aleph::suffix (Node *root)
	Return a list with postorder traversal of a tree.
template<class Node >
size_t	Aleph::compute_cardinality_rec (Node *root) noexcept
	Count the number of nodes of a binary tree.
template<class Node >
size_t	Aleph::size (Node *root) noexcept
template<class Node >
size_t	Aleph::computeHeightRec (Node *root) noexcept
	Compute recursively the height of root
template<class Node >
void	Aleph::destroyRec (Node *&root) noexcept
	Free recursively all the memory occupied by the tree root
template<class Node >
void	Aleph::callKeyDestructorsRec (Node *&root) noexcept
	Traverses recursively the tree and calls key's destructors.
template<class Node >
Node *	Aleph::copyRec (Node *root)
	Copy recursively a tree.
template<class Node >
bool	Aleph::areSimilar (Node *t1, Node *t2) noexcept
	Return true if both trees are similar.
template<class Node , class Equal >
bool	Aleph::areEquivalents (Node *t1, Node *t2, Equal &op) noexcept
	Return true if trees are equivalents.
template<class Node , class Equal = std::equal_to<typename Node::key_type>>
bool	Aleph::areEquivalents (Node *t1, Node *t2, Equal &&op=Equal()) noexcept
template<class Node >
void	Aleph::levelOrder (Node *root, void(*visitFct)(Node *, int, bool))
	Traverse a binary tree by levels.
template<class Node , class Operation >
bool	Aleph::level_traverse (Node *root, Operation &operation)
	Level traverse a tree and execute an operation.
template<class Node , class Operation >
bool	Aleph::level_traverse (Node *root, Operation &&operation)
template<template< class > class Node, typename Key >
Node< Key > *	Aleph::build_tree (const DynArray< Key > &preorder, long l_p, long r_p, const DynArray< Key > &inorder, long l_i, long r_i)
	Build a binary tree form its preorder and inorder traversals.
template<template< class > class Node, typename Key >
Node< Key > *	Aleph::build_postorder (const DynArray< Key > &post, long lp, long rp, const DynArray< Key > &in, long li, long ri)
template<class Node >
static void	Aleph::compute_nodes_in_level_helper (Node *root, long level, const long current_level, DynDlist< Node * > &level_list)
template<class Node >
DynDlist< Node * >	Aleph::compute_nodes_in_level (Node *root, const int &level)
	Count the number of nodes in a specific tree level.
template<class Node >
void	Aleph::inOrderThreaded (Node *root, void(*visitFct)(Node *))
	Traverse inorder a binary tree without recursion and without stack.
template<class Node >
void	Aleph::preOrderThreaded (Node *node, void(*visitFct)(Node *))
	Traverse preorder a binary tree without recursion and without stack.
template<class Node >
static size_t	Aleph::internal_path_length_helper (Node *p, const size_t &level) noexcept
template<class Node >
size_t	Aleph::internal_path_length (Node *p) noexcept
	Compute the internal path length.
template<class Node >
void	Aleph::tree_to_bits (Node *root, BitArray &array)
	Compute a bit code for the binary tree.
template<class Node >
BitArray	Aleph::tree_to_bits (Node *root)
	Compute a bit code for the binary tree.
template<class Node >
std::string	Aleph::code (Node *root)
	Compute a string with the Lukasiewicz`s word of a tree.
template<class Node >
static Node *	Aleph::bits_to_tree_helper (const BitArray &array, int &i)
template<class Node >
Node *	Aleph::bits_to_tree (const BitArray &array, int idx=0)
	Build a binary tree given its bits code.
template<class Node >
void	Aleph::save_tree_keys_in_prefix (Node *root, std::ostream &output)
	Store in output stream the tree keys in preorder.
template<class Node >
void	Aleph::load_tree_keys_in_prefix (Node *root, std::istream &input)
	Load the keys stored in preorder from an input stream.
template<class Node >
void	Aleph::save_tree (Node *root, std::ostream &output)
	Store a binary tree in a stream.
template<class Node >
Node *	Aleph::load_tree (std::istream &input)
	Load and build a binary tree from a stream.
template<class Node , class Get_Key >
void	Aleph::put_tree_keys_in_array (Node *root, std::ostream &out)
template<class Node , class Load_Key >
void	Aleph::load_tree_keys_from_array (Node *root, const char *keys[], int &idx)
template<class Node , class Get_Key >
void	Aleph::save_tree_in_array_of_chars (Node *root, const std::string &array_name, std::ostream &output)
	Generate C++ array declarations for a binary tree.
template<class Node , class Load_Key >
Node *	Aleph::load_tree_from_array (const unsigned char bits[], const size_t &num_bits, const char *keys[])
	Build a binary tree from two arrays.
template<class Node , class Compare >
static bool	Aleph::check_bst_range (Node *p, const typename Node::key_type *min_key, const typename Node::key_type *max_key, const Compare &cmp)
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
bool	Aleph::check_bst (Node *p, const Compare &cmp=Compare())
	Return true if p is a binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::preorder_to_bst (DynArray< typename Node::key_type > &preorder, int l, int r, const Compare &cmp=Compare())
	Build a binary search tree from its preorder traversal.
template<typename T , class Compare = Aleph::less<T>>
ThreeWayCmp	Aleph::three_way_compare (const T &a, const T &b, const Compare &cmp=Compare()) noexcept
	Three-way comparison using a binary comparator.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::searchInBinTree (Node *root, const typename Node::key_type &key, const Compare &cmp=Compare()) noexcept
	Search a key in a binary search tree.
template<class Node >
Node *	Aleph::find_min (Node *root) noexcept
	Return the minimum key contained in a binary search tree.
template<class Node >
Node *	Aleph::find_max (Node *root) noexcept
	Return the maximum key contained in a binary search tree.
template<class Node >
Node *	Aleph::find_successor (Node *p, Node *&pp) noexcept
	Find the inorder successor of p
template<class Node >
Node *	Aleph::find_predecessor (Node *p, Node *&pp) noexcept
	Find the inorder predecessor of p
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_parent (Node *root, const typename Node::key_type &key, Node *&parent, const Compare &cmp=Compare()) noexcept
	Search a key and find its node and parent.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_rank_parent (Node *root, const typename Node::key_type &key, const Compare &cmp=Compare()) noexcept
	Rank search of a key in a binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_in_bst (Node *&r, Node *p, const Compare &cmp=Compare()) noexcept
	Insert a node p in a binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_in_bst (Node *&root, Node *p, const Compare &cmp=Compare()) noexcept
	Insert a node p in a binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_or_insert_in_bst (Node *&r, Node *p, const Compare &cmp=Compare()) noexcept
	Search or insert a node in a binary search tree.
template<class Node , class Compare >
static bool	Aleph::split_key_rec_helper (Node *root, const typename Node::key_type &key, Node *&ts, Node *&tg, Compare &cmp) noexcept
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
bool	Aleph::split_key_rec (Node *&root, const typename Node::key_type &key, Node *&ts, Node *&tg, const Compare &cmp=Compare()) noexcept
	Split recursively according to a key.
template<class Node , class Compare >
static void	Aleph::split_key_dup_rec_helper (Node *root, const typename Node::key_type &key, Node *&ts, Node *&tg, Compare &cmp) noexcept
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
void	Aleph::split_key_dup_rec (Node *&root, const typename Node::key_type &key, Node *&ts, Node *&tg, const Compare &cmp=Compare()) noexcept
	Split a tree according to a key value.
template<class Node >
Node *	Aleph::join_exclusive (Node *&ts, Node *&tg) noexcept
	Exclusive join of two binary trees.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::remove_from_bst (Node *&root, const typename Node::key_type &key, const Compare &cmp=Compare()) noexcept
	Remove a key from a binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_root (Node *&root, Node *p, const Compare &cmp=Compare()) noexcept
	Insert the node p as root of a binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_root (Node *&root, Node *p, const Compare &cmp=Compare()) noexcept
	Insert node p as root of a binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::join_preorder (Node *t1, Node *t2, Node *&dup, const Compare &cmp=Compare()) noexcept
	Union of two binary search trees.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::join (Node *t1, Node *t2, Node *&dup, const Compare &cmp=Compare()) noexcept
	Fast union of two binary search trees.
template<class Node >
Node *	Aleph::rotate_to_right (Node *p) noexcept
	Rotate to the right the tree with root p
template<class Node >
Node *	Aleph::rotate_to_right (Node *p, Node *pp) noexcept
	Rotate to the right the tree with root p and update its parent.
template<class Node >
Node *	Aleph::rotate_to_left (Node *p) noexcept
	Rotate to the left the tree with root p
template<class Node >
Node *	Aleph::rotate_to_left (Node *p, Node *pp) noexcept
	Rotate to the left the tree with root p and update its parent.
template<class Node , class Key , class Compare = Aleph::less<typename Node::key_type>>
void	Aleph::split_key (Node *&root, const Key &key, Node *&l, Node *&r, const Compare &cmp=Compare()) noexcept
	Split a binary search tree according to a key.
template<class Node >
void	Aleph::swap_node_with_successor (Node *p, Node *&pp, Node *q, Node *&pq) noexcept
	Swap a node with its successor inorder.
template<class Node >
void	Aleph::swap_node_with_predecessor (Node *p, Node *&pp, Node *q, Node *&pq) noexcept
	Swap a node with its predecessor inorder.
template<class Node , class Key = typename Node::key_type, class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_root_rec (Node *root, Node *p, const Compare &cmp=Compare()) noexcept
	Insert a node as root in a binary search tree.
template<class Node , class Key = typename Node::key_type, class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_or_insert_root_rec (Node *root, Node *p, const Compare &cmp=Compare()) noexcept
	Search and eventually insert p as root in a binary search tree.
template<class Node , class Op >
bool	Aleph::prefix_traverse (Node *root, Op op)
	Traverse a tree in preorder via its iterator and performs a conditioned operation on each item.
template<class Node , class Op >
void	Aleph::prefix_for_each (Node *root, Op op)
	Traverse in preorder all the container and performs an operation on each element.
template<class Node , class Op >
bool	Aleph::infix_traverse (Node *root, Op op)
	Traverse a tree in inorder via its iterator and performs a conditioned operation on each item.
template<class Node , class Op >
bool	Aleph::traverse (Node *root, Op op)
template<class Node , class Op >
void	Aleph::infix_for_each (Node *root, Op op)
	Traverse all the container and performs an operation on each element.

Detailed Description

Utility functions for binary tree operations.

This file provides a comprehensive set of utility functions for binary trees including traversals (inorder, preorder, postorder, level-order), tree construction, copying, destruction, rotation, and various query operations.

Author

Leandro Rabindranath León

Definition in file tpl_binNodeUtils.H.