tpl_tree_node.H File Reference

General tree (n-ary tree) node. More...

#include <stdexcept>
#include <dlink.H>
#include <ahDry.H>
#include <ah-dry-mixin.H>
#include <ahIterator.H>
#include <ahFunction.H>
#include <ahFunctional.H>
#include <htlist.H>
#include <tpl_dynListStack.H>
#include <tpl_dynListQueue.H>
#include <tpl_binNode.H>
#include <ah-errors.H>

Include dependency graph for tpl_tree_node.H:

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

Go to the source code of this file.

Classes
class	Aleph::Tree_Node< T >
	Generic m-ary trees. More...
struct	Aleph::Tree_Node< T >::Flags
class	Aleph::Tree_Node< T >::Children_Iterator
	Iterator over the children of this. More...
struct	Aleph::Tree_Node< T >::Children_Set
struct	Aleph::Tree_Node< T >::Children_Set::Iterator
class	Aleph::Tree_Node< T >::Iterator
struct	Aleph::Tree_Node_Vtl< T >

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

Macros
#define	ISROOT(p)   ((p)->is_root())
#define	ISLEAF(p)   ((p)->is_leaf())
#define	ISLEFTMOST(p)   ((p)->is_leftmost())
#define	ISRIGHTMOST(p)   ((p)->is_rightmost())
#define	SIBLING_LIST(p)   ((p)->get_sibling_list())
#define	CHILD_LIST(p)   ((p)->get_child_list())
#define	SIBLING_LINK(p)   ((p)->get_sibling_list())
#define	LCHILD(p)   ((p)->get_left_child())
#define	RSIBLING(p)   ((p)->get_right_sibling())
#define	IS_UNIQUE_SIBLING(p)   (RSIBLING(p) == (p))

Functions
template<class Node >
static void	Aleph::clone_tree (Node *src, Node *tgt)
template<class Node >
Node *	Aleph::clone_tree (Node *root)
template<class Node >
static void	Aleph::__tree_preorder_traversal (Node *root, const int &level, const int &child_index, void(*visitFct)(Node *, int, int))
template<class Node >
void	Aleph::tree_preorder_traversal (Node *root, void(*visitFct)(Node *, int, int))
	Preorder traversal of a tree.
template<class Node >
void	Aleph::forest_preorder_traversal (Node *root, void(*visitFct)(Node *, int, int))
	Preorder traversal of a forest.
template<class Node >
static void	Aleph::__tree_postorder_traversal (Node *node, const int &level, const int &child_index, void(*visitFct)(Node *, int, int))
template<class Node >
void	Aleph::tree_postorder_traversal (Node *root, void(*visitFct)(Node *, int, int))
	Postorder traversal of a tree.
template<class Node >
void	Aleph::forest_postorder_traversal (Node *root, void(*visitFct)(Node *, int, int))
	Postorder traversal of a forest.
template<class Node , class Eq >
bool	Aleph::are_tree_equal (Node *t1, Node *t2, Eq &eq)
	Returns true if t1 is equal to t2.
template<class Node , class Eq = std::equal_to<typename Node::key_type>>
bool	Aleph::are_tree_equal (Node *t1, Node *t2, Eq &&eq=Eq())
template<class Node >
void	Aleph::destroy_tree (Node *root)
	Destroys (frees memory) the tree whose root is root.
template<class Node >
void	Aleph::destroy_forest (Node *root)
	Destroys (frees memory) the forest whose first tree is root.
template<class Node >
size_t	Aleph::compute_height (Node *root)
	Computes the height of the tree root.
template<class Node >
static Node *	Aleph::__deway_search (Node *node, int path[], const int &idx, const size_t &size)
template<class Node >
Node *	Aleph::deway_search (Node *root, int path[], const size_t &size)
	Returns a node of a forest given its Dewey number.
template<class Node , class Equal >
static Node *	Aleph::__search_deway (Node *root, const typename Node::key_type &key, const size_t &current_level, int deway[], const size_t &size, size_t &n)
template<class Node , class Equal = Aleph::equal_to<typename Node::key_type>>
Node *	Aleph::search_deway (Node *root, const typename Node::key_type &key, int deway[], const size_t &size, size_t &n)
	Searches key in a forest and computes the Dewey number of the node containing the key.
template<class TNode , class BNode >
BNode *	Aleph::forest_to_bin (TNode *root)
	Converts a forest to its equivalent binary tree.
template<class TNode , class BNode >
static void	Aleph::insert_child (BNode *lnode, TNode *tree_node)
template<class TNode , class BNode >
static void	Aleph::insert_sibling (BNode *rnode, TNode *tree_node)
template<class TNode , class BNode >
static void	Aleph::bin_to_tree (BNode *broot, TNode *troot)
template<class TNode , class BNode >
TNode *	Aleph::bin_to_forest (BNode *broot)
	Converts a binary tree to its equivalent forest.

Detailed Description

General tree (n-ary tree) node.

Node for general trees with arbitrary number of children. Uses first-child/next-sibling representation.

See also

tpl_binNodeUtils.H Binary tree utilities

Author

Leandro Rabindranath León

Definition in file tpl_tree_node.H.

Macro Definition Documentation

CHILD_LIST

#define CHILD_LIST

(

p

)

((p)->get_child_list())

Definition at line 66 of file tpl_tree_node.H.

IS_UNIQUE_SIBLING

#define IS_UNIQUE_SIBLING

(

p

)

(RSIBLING(p) == (p))

Definition at line 70 of file tpl_tree_node.H.

ISLEAF

#define ISLEAF

(

p

)

((p)->is_leaf())

Definition at line 61 of file tpl_tree_node.H.

ISLEFTMOST

#define ISLEFTMOST

(

p

)

((p)->is_leftmost())

Definition at line 62 of file tpl_tree_node.H.

ISRIGHTMOST

#define ISRIGHTMOST

(

p

)

((p)->is_rightmost())

Definition at line 63 of file tpl_tree_node.H.

ISROOT

#define ISROOT

(

p

)

((p)->is_root())

Definition at line 60 of file tpl_tree_node.H.

LCHILD

#define LCHILD

(

p

)

((p)->get_left_child())

Definition at line 68 of file tpl_tree_node.H.

RSIBLING

#define RSIBLING

(

p

)

((p)->get_right_sibling())

Definition at line 69 of file tpl_tree_node.H.

SIBLING_LINK

#define SIBLING_LINK

(

p

)

((p)->get_sibling_list())

Definition at line 67 of file tpl_tree_node.H.

SIBLING_LIST

#define SIBLING_LIST

(

p

)

((p)->get_sibling_list())

Definition at line 65 of file tpl_tree_node.H.