The Left-Child Right-Sibling tree (LC-RS) is a kind of binary tree that can be u

Question

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

Given below is the implentation to convert a trinary tree to binary tree.

public static <K> BinaryTreenode<K> convertTrinary2LCRS(TrinaryTreenode<K> triTreeRoot) {
   if(triTreeRoot == null)
       return null;
   BinaryTreenode<K> left = convertTrinary2LCRS(triTreeRoot.getLeft());
   BinaryTreenode<K> mid = convertTrinary2LCRS(triTreeRoot.getMid());
   BinaryTreenode<K> right = convertTrinary2LCRS(triTreeRoot.getRight());
   if(mid != null)
       mid.setRight(right);
   if(left != null)
       left.setRight(mid);
   BinaryTreenode<K> newRoot = new BinaryTreenode<K>(triTreeRoot.getKey(), left, null);
   return newRoot;
   }

In order to test the correctness of this function, I just modified the node classes to print the contents. The following program demonstrates the function implemented above. Please don't forget to rate the answer if it helped. Thank you.

The program constructs the trinary tree with 9 nodes shown in the question and prints the converted binary tree.

TerinaryTreenode.java

class TrinaryTreenode <K> {
// *** fields ***
private K key;
private TrinaryTreenode<K> leftChild;
private TrinaryTreenode<K> midChild;
private TrinaryTreenode<K> rightChild;

// *** methods ***
public K getKey() { return key; }
public TrinaryTreenode<K> getLeft() { return leftChild; }
public TrinaryTreenode<K> getMid() { return midChild; }
public TrinaryTreenode<K> getRight() { return rightChild; }
  
public TrinaryTreenode(K keyRef, TrinaryTreenode<K> leftNodeRef, TrinaryTreenode<K> midNodeRef,
       TrinaryTreenode<K> rightNodeRef) {
key = keyRef;
leftChild = leftNodeRef;
midChild = midNodeRef;
rightChild = rightNodeRef;
}
  
public void print(String indent, String childname)
{
   System.out.println(indent + "---" + childname + key);
   if(leftChild == null)
       System.out.println(indent + " " +"---"+ "L:Nil");
   else
       leftChild.print(indent+ " " , "L:");
  
  
   if(midChild == null)
       System.out.println(indent + " " + "---"+"M:Nil");
   else
       midChild.print(indent+ " " , "M:");
  
   if(rightChild == null)
       System.out.println(indent + " " + "---"+"R:Nil");
   else
       rightChild.print(indent+ " " , "R:");
  
}
  
}

BinaryTreenode.java

public class BinaryTreenode <K> {
// *** fields ***
private K key;
private BinaryTreenode<K> leftChild;
private BinaryTreenode<K> rightChild;

// *** methods ***
public K getKey() { return key; }
public BinaryTreenode<K> getLeft() { return leftChild; }
public BinaryTreenode<K> getRight() { return rightChild; }
  
public BinaryTreenode(K keyRef, BinaryTreenode<K> leftNodeRef, BinaryTreenode<K> rightNodeRef) {
key = keyRef;
leftChild = leftNodeRef;
rightChild = rightNodeRef;
}
public void setLeft(BinaryTreenode<K> leftNodeRef) { leftChild = leftNodeRef; }
public void setRight(BinaryTreenode<K> rightNodeRef) { rightChild = rightNodeRef; }
  
public void print(String indent, String childname)
{
   System.out.println(indent + "---" + childname + key);
   if(leftChild == null)
       System.out.println(indent + " " +"---"+ "L:Nil");
   else
       leftChild.print(indent+ " " , "L:");
  
     
  
   if(rightChild == null)
       System.out.println(indent + " " + "---"+"R:Nil");
   else
       rightChild.print(indent+ " " , "R:");
  
  
}
}

ConvertTrinary.java

public class ConvertTrinary {
   public static <K> BinaryTreenode<K> convertTrinary2LCRS(TrinaryTreenode<K> triTreeRoot) {
   if(triTreeRoot == null)
       return null;
   BinaryTreenode<K> left = convertTrinary2LCRS(triTreeRoot.getLeft());
   BinaryTreenode<K> mid = convertTrinary2LCRS(triTreeRoot.getMid());
   BinaryTreenode<K> right = convertTrinary2LCRS(triTreeRoot.getRight());
   if(mid != null)
       mid.setRight(right);
   if(left != null)
       left.setRight(mid);
   BinaryTreenode<K> newRoot = new BinaryTreenode<K>(triTreeRoot.getKey(), left, null);
   return newRoot;
   }
  
   public static void main(String[] args) {
       TrinaryTreenode<Integer> node5 = new TrinaryTreenode<Integer>(5, null, null, null);
       TrinaryTreenode<Integer> node6 = new TrinaryTreenode<Integer>(6, null, null, null);
      
       TrinaryTreenode<Integer> node3 = new TrinaryTreenode<Integer>(3, null, null, null);
       TrinaryTreenode<Integer> node8 = new TrinaryTreenode<Integer>(8, null, null, null);
       TrinaryTreenode<Integer> node9 = new TrinaryTreenode<Integer>(9, null, null, null);
       TrinaryTreenode<Integer> node2 = new TrinaryTreenode<Integer>(2, node5, node6, null);
       TrinaryTreenode<Integer> node7 = new TrinaryTreenode<Integer>(7, node8, node9, null);
       TrinaryTreenode<Integer> node4 = new TrinaryTreenode<Integer>(4, node7, null, null);
       TrinaryTreenode<Integer> node1 = new TrinaryTreenode<Integer>(1, node2, node3, node4);
       System.out.println("Trinary tree is ");
       node1.print(" ", "Root:");
      
       System.out.println("Binary tree is ");
       BinaryTreenode<Integer> binTree = convertTrinary2LCRS(node1);
       binTree.print(" ", "Root:");
   }
}

output

Trinary tree is
---Root:1
---L:2
---L:5
---L:Nil
---M:Nil
---R:Nil
---M:6
---L:Nil
---M:Nil
---R:Nil
---R:Nil
---M:3
---L:Nil
---M:Nil
---R:Nil
---R:4
---L:7
---L:8
---L:Nil
---M:Nil
---R:Nil
---M:9
---L:Nil
---M:Nil
---R:Nil
---R:Nil
---M:Nil
---R:Nil

Binary tree is
---Root:1
---L:2
---L:5
---L:Nil
---R:6
---L:Nil
---R:Nil
---R:3
---L:Nil
---R:4
---L:7
---L:8
---L:Nil
---R:9
---L:Nil
---R:Nil
---R:Nil
---R:Nil
---R:Nil

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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