Data Structures: The Left-Child Right-Sibling tree (LC-RS) is a kind of binary t

Question

Data Structures:

The Left-Child Right-Sibling tree (LC-RS) is a kind of binary tree that can be used to represent general trees, which have an arbitrary number of children per node. For example, the general tree on the left below can be converted to its equivalent LC-RS tree on the right:

Implement the generic convertTrinary2LCRS method below so that it converts a given tree into an LC-RS binary tree. For simplicity, assume the given tree will be a full trinary tree, that is, a tree where every parent has exactly three children and all leaves are at the same level.

The method is passed a reference to a TrinaryTreenode that is the root of the tree to be converted, and it returns a reference to the root of a BinaryTreenode that is the equivalent LC-RS tree.

The TrinaryTreenode class is implemented as shown below:

Assume the BinaryTreenode class is done similarly but without the midChild field and accessor method, and with this constructor and these mutator methods:

Explanation / Answer

The traverse function is called like

To get the parent node

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.