panwave::Tree< Element, k > Class Template Reference

#include <Tree.h>

Public Member Functions
	Tree (size_t height)

Protected Member Functions
size_t	GetLeafCount () const
size_t	GetFirstLeaf () const
size_t	GetLastLeaf () const
bool	IsLeaf (size_t node) const
size_t	GetChild (size_t parent, size_t child_index) const
size_t	GetParent (size_t child) const
Element &	GetNodeData (size_t index)
bool	IsMarked (size_t node) const
void	SetMark (size_t node)
void	Unmark ()
size_t	GetHeight () const

Detailed Description

template<class Element, size_t k>
class panwave::Tree< Element, k >

A simple, generic k-ary tree implementation.
This class is designed to serve as the basis for the WaveletPacketTree set of classes and, as such, doesn't provide much functionality to use it as a stand-alone tree.
Template argument k defines the number of children each node in the tree has.
If k=2 the tree is an ordinary binary tree.
If k=4 the tree is an ordinary quad tree.
Etc.
Nodes are physically allocated in a vector. The first node in the vector is the root node. The next k nodes are the nodes in the second level of the tree (these are the children of the root node) and the remaining nodes in the vector continue this trend.

Constructor & Destructor Documentation

Tree()

template<class Element , size_t k>

panwave::Tree< Element, k >::Tree ( size_t  height )

inlineexplicit

Tree constructor.

Parameters

height

The height of the tree. A tree consisting only of a single root node has height = 1.

Member Function Documentation

GetChild()

template<class Element , size_t k>

size_t panwave::Tree< Element, k >::GetChild ( size_t  parent, size_t  child_index  ) const

inlineprotected

Get the child of a parent node.

Parameters

parent	The parent node index.
child_index	The 0-based index of the child relative to parent. The first child is 0. A binary tree node would have child indices of [0,1]. A quad tree node would have child indicies [0,1,2,3].

GetFirstLeaf()

template<class Element , size_t k>

size_t panwave::Tree< Element, k >::GetFirstLeaf ( ) const

inlineprotected

Return the index of the first leaf node.

GetHeight()

template<class Element , size_t k>

size_t panwave::Tree< Element, k >::GetHeight ( ) const

inlineprotected

Get the height of the tree.

Returns

size_t The height of the tree. A height of one indicates only a root node with no children.

GetLastLeaf()

template<class Element , size_t k>

size_t panwave::Tree< Element, k >::GetLastLeaf ( ) const

inlineprotected

Return the index of the last leaf node.

GetLeafCount()

template<class Element , size_t k>

size_t panwave::Tree< Element, k >::GetLeafCount ( ) const

inlineprotected

Return the number of leaves in the tree.
Leaves are the nodes in the bottom (last) level of the tree which themselves do not have children nodes.

GetNodeData()

template<class Element , size_t k>

Element& panwave::Tree< Element, k >::GetNodeData ( size_t  index )

inlineprotected

Get the writable data stored at tree node |index|.

GetParent()

template<class Element , size_t k>

size_t panwave::Tree< Element, k >::GetParent ( size_t  child ) const

inlineprotected

Get the parent index for a child node.

Parameters

child

The child node index.

IsLeaf()

template<class Element , size_t k>

bool panwave::Tree< Element, k >::IsLeaf ( size_t  node ) const

inlineprotected

Returns true if node is a leaf node.

Parameters

node	The index of a node to check.

IsMarked()

template<class Element , size_t k>

bool panwave::Tree< Element, k >::IsMarked ( size_t  node ) const

inlineprotected

Return true if node is set as marked.

Parameters

node	The node index to check for mark state.

SetMark()

template<class Element , size_t k>

void panwave::Tree< Element, k >::SetMark ( size_t  node )

inlineprotected

Set node as marked.

Parameters

node	The node index to mark.

Unmark()

template<class Element , size_t k>

void panwave::Tree< Element, k >::Unmark ( )

inlineprotected

Unmark all nodes in the tree.

---

The documentation for this class was generated from the following file:

• src/Tree.h