Information Technology Reference
In-Depth Information
terms, the sequence encoding of trees over
n
nodes is given by two sequences: the
sequence ordering the nodes, and another sequence, of length
n
−
1, over the nodes.
7.8.7
Binary Trees
A natural correspondence can be easily established between any forest and a binary
tree (each node which is not a leaf has at most two sons). The correspondence is
depicted by Fig. 7.24. The idea is very simple: the roots of the forest are linked in
the order of the corresponding trees of the forest; moreover, every father is linked
only to the first son and every son to the following son. The root of the first tree of
the forest is the root of the resulting tree. In this way, any forest provides a binary
tree.
Fig. 7.24
Representation of a forest of trees by means of a binary tree
7.8.8
Phylogenetic Trees
Given
n
organisms how many different phylogenetic trees can be built from them?
Let us assume that we are interested only to the phylogenetic branching processes.
Abinarytreeis
complete
if any node different from the root has exactly two sons (a
tree is
k
-ary if any node different from the root has at most
k
sons, and it is complete
if any node different from the root has exactly
k
sons).
The problem of (branching) phylogenetic reconstruction reduces to the enumer-
ation of the set
BT
(
)
n
of rooted complete binary trees on
n
leaves [219].
