- there is one node designated as the root, denoted root(T);
- the remaining nodes are partitioned into subsets T1, T2, ..., Tm, each of which is also a tree (subtrees).
It is often more convenient to represent an ordered tree as a rooted binary tree, so that each node can be stored in the same amount of memory. The conversion is performed by the following steps:
- remove all edges from each node to its children;
- for each node, add an edge to its first child in T (if any) as the left child;
- for each node, add an edge to its next sibling in T (if any) as the right child.
This is illustrated by the following:
In most cases, the height of the tree (the number of edges in the longest root-to-leaf path) increases after the conversion. This is undesirable because the complexity of many algorithms on trees depends on its height.0 0 / | \\ / 1 2 3 ===> 1 / \\ \\ 4 5 2 / \\ 4 3 \\ 5
You are asked to write a program that computes the height of the tree before and after the conversion.
where t is the case number (starting from 1), h1 is the height of the tree before the conversion, and h2 is the height of the tree after the conversion.Tree t: h1 => h2
dudduduudu ddddduuuuu dddduduuuu dddduuduuu #
Tree 1: 2 => 4 Tree 2: 5 => 5 Tree 3: 4 => 5 Tree 4: 4 => 4