Explain the process of converting a tree to a binary tree.
Answers
Answer:
A tree is an unordered hierarchical data structure with unlimited children nodes for each parent. A binary tree only has a maximum of two children nodes for each parent, commonly called left node and right node.
Converting from tree to binary tree would simply require that you start with the root node and start copying each node into the binary tree. The only rules would be that each node cannot have more than two children, including the root node.
General Trees and Conversion to Binary Trees
General trees are those in which the number of subtrees for any node is not
required to be 0, 1, or 2. The tree may be highly structured and therefore
have 3 subtrees per node in which case it is called a ternary tree.
However, it is often the case that the number of subtrees for any node may
be variable. Some nodes may have 1 or no subtrees, others may have 3, some
4, or any other combination. The ternary tree is just a special case of a
general tree (as is true of the binary tree).
General trees can be represented as ADT's in whatever form they exist.
However, there are some substantial problems. First, the number of references
for each node must be equal to the maximum that will be used in the tree.
Obviously, some real problems are presented when another subtree is added to
a node which already has the maximum number attached to it. It is also
obvious that most of the algorithms for searching, traversing, adding and
deleting nodes become much more complex in that they must now cope with
situations where there are not just two possibilities for any node but
multiple possibilities. It is also possible to represent a general tree in
a graph data structure (to be discussed later) but many of the advantages of
the tree processes are lost.
Fortunately, general trees can be converted to binary trees. They don't
often end up being well formed or full, but the advantages accrue from
being able to use the algorithms for processing that are used for binary
trees with minor modifications. Therefore, each node requires only two
references but these are not designated as left or right. Instead they are
designated as the reference to the first child and the reference to next
sibling. Therefore the usual left pointer really points to the first child