Binary Trees

Table of Contents

• Introduction
• Implementations

Introduction

Coalescence Binary Trees classes provide a way to guarantee that each vertex \(v\) has exactly

• 0 successor (the vertex is a leaf)
• 2 successors (the vertex is an internal node)

The graph structure is bidirectional and allows to model a forest of disconnected trees. That is, if a vertex has no predecessor, then it's either a root (if it has 2 successors) or an isolated vertex (if it has no successor).

Users will encounter this type of tree when returning from coalescence binary mergers, or if they simply want to build and manipulate graphs while enforcing a binary tree structure.

Implementations

Coalescence Binary Trees can store an additional arbitrary type of information (called a Property Class) along their vertices or edges: if the user decides to do so, the tree class interface adapts to offer ways to manipulate this information.

There are logically 4 different classes (equivalently interfaces) resulting from this:

• A class to represent a simple topology with no additional information (no property):
  quetzal::coalescence::binary_tree< no_property, no_property >
• A class to embed a user-defined class VertexProperty on each vertex:
  quetzal::coalescence::binary_tree< VertexProperty, no_property >
• A class to embed a user-defined class EdgeProperty on each edge:
  quetzal::coalescence::binary_tree< boost::no_property, EdgeProperty >
• A class to embed both VertexProperty and EdgeProperty information :
  quetzal::coalescence::binary_tree< VertexProperty, EdgeProperty >

Usage examples are described in their respective class documentation.