The program will ask for the number of leaves and
it will construct a binary tree with the given number of leaves. The method
of construction can be of four different types according to your selection.
The tree constructed can be rooted or rootless.
-
A rootless binary tree is a binary
tree with vertices of degree one or three.
-
A rooted binary tree is similar, but
it has an extra vertex of degree two.
Vertices of degree one are leaves, other vertices are internal vertices.
The vertex of degree two is the root.
Given the number of leaves, the program can construct a (rooted or rootless)
binary tree in two different ways:
-
The Uniform method chooses each tree
on the given number of leaves with the same probability.
Take a random permutation of leaves with uniform distribution.
The construction
of the tree is recursive.
It starts from a single edge connecting the first two leaves
in the rootless case and an edge subdivided by a root
in the rooted case. We add new leaves until the desired number of leaves
is obtained as follows: One of the edges of the current tree
is chosen randomly with uniform distribution
and is subdivided by a vertex. A new edge is connected to this
subdividing vertex and joins it to the current
new leaf.
-
The Yule-Harding method is the same,
except for the choice of the edge to be subdivided. In this case we choose
one edge from the leaf edges uniformly.
Both algorithms can construct all tree, but the Yule-Harding algorithm
tends to generate bushier trees than the Uniform algorithm.
©1999
All Rights Reserved
e-mail
the Pagemaster
GoBack