---

Node

Compounds
class	Node
	This class provides the basic interface to the node-classes. More...
class	NormalNode
class	RootNode

---

Detailed Description

Trees can consist of common nodes (NormalNode-s) and subtrees. Subtrees consist of a RootNode as root node and NormalNode-s.

For the construction of this recursive structure we used the compositum design pattern by [Gamma]. This design pattern consists of a common interface for trees, subtrees and nodes, which can always be handled (except during construction) with a pointer on the abstract base class (see picture).

Extending trees by additional application specific functionality is traditionally done this way by extending the interface of Node. But to make the tree structure as generic and reusable as possible, these extensions should not be done in the Nodes directly but in the visitors (see section NodeVisitor). Therefore the Node classes implement the method Node::acceptVisitor(), where they transfer themselves to the visitor.

Each node of the tree has its own list of children and parents which are accessible with the methods Node::getChildren() and Node::getParent(). To be able to also handle complete subtrees, the method Node::getLeaves() return the leaves of a subtree without the inner nodes. The list of all leaves of one node is initialized once after the tree creation by calling Node::recalcLeaves(). Besides the parent node each node also contains a reference to its root node, accessible by Node::getRoot(). RootNode's root is either a pointer to themselves or if they are part of a larger tree, a pointer to the root node. NormalNode-s root pointer always points to the next upper RootNode. That is i.e. important for iterators which either iterate over all children of one node or over all children that are part of the same tree.

Another extension of the original design pattern is, that NormalNode-s also can have children and that there are no special leave nodes. Leaves are nodes that have no children.

Since children have a certain order, the insertion of children must be possible at any given point. For these operations the methods Node::addChildFront(), Node::addChildBack() und Node::addChild() are given. The method Node::addchild() insert a node either where one was deleted using Node::deleteChild() or at the right end of list of children. This makes it easy to replace a node.

Important are also the methods to traverse a tree. As in STL the methods Node::begin() and Node::end() return iterators that point to the first resp. behind the last node. These iterators are of type NodeIterator (see section NodeIterator) and iterate over all nodes that have the same root as the start node. That means, that nodes that are part of a subtree (and thus having a different RootNode as root) can not be reached by this iterator. To get all nodes the AllNodeIterator must be used, which can be accessed by Node::beginAll() and Node::endAll().

Nodes can be marked as fixed with Node::setFixed(). These cannot be deleted from the tree, given that they are not deleted as a whole subtree. In order to merge neighbored fixed nodes to subtrees the method reduce() can be used.

A copy of a node can be made with the method Node::clone(), a copy of a whole tree returns Node::cloneTree(). The destructor of Node is recursive and deletes all child nodes.

Each node can also contain data, which can be configured as a template parameter. It is accessible from the node interface with the method Node::getContent().

Hierarchy of Node classes

---