## Transcribed Text

M-ary Trees, Last Child, and Left Sibling Topics: Trees, Tree Operations, Traversals, Recursion, Queues, and Linked Lists
M-ary Tree
A rooted tree is an m-ary tree if every internal node has no more than m children. Example: 3-ary tree
Last Child Left Sibling Method
A node keeps track of only two links:
a) right most child (unless the node is a leaf) and
b) sibling to its left (unless the node is the left most child).
By simple rearrangement of links, an m-ary tree can thus be converted into its corresponding binary form:
Which is essentially a binary tree of the form:
TASK 1
Create a m-ary tree node class. An outline is given below:
Class Name:
MTreeNode<AnyType> Instance variables:
1. AnyType element
2.int m
3. ArrayList<MTreeNode> children
Constructors:
1. public MTreeNode (AnyType element, int m, ArrayList<MTreeNode> children)
2. public MTreeNode (AnyType el, int m)
where element represents values or elements of type AnyType, m is the branching factor which
is 3 in 3-ary trees and 4 in 4-ary trees, and an array containing a total of m or less children.
Methods:
1. public static int height(MTreeNode<?> t) returns the height of the tree rooted at t and -1 if null
2. public static int size(MTreeNode<?> t) returns the size of the tree rooted at t and 0 if null
3. public <AnyType> boolean addChild(MTreeNode<AnyType> child) adds the child to the list of children; returns true if child is added, false if the array is full thus can’t add more children
4. public String toStringPreOrder()
returns a String representation of a pre-order walk on the m-ary tree rooted at this node.
5. public String toStringPostOrder()
returns a String representation of a post-order walk on the m-ary tree rooted at this node.
6. public String toStringLevelOrder()
returns a String representation of a level-order walk on the m-ary tree rooted at this node. Hint: Use a queue.
All walks are from right to left as compared to the traditional left to right.
Example Outputs of tree traversals on the m-ary tree given on the right:
Pre-order: “A D F L K E C B I J H G” Post-order: “L K F E D C J I H G B A” Level-order: “A D C B F E I H G L K J”
Height of the tree = 3
Size of the tree = 12
TASK 2
From an input text file, read the nodes and construct an m-ary tree. Format of input.txt is given below:
m <root node> <level one nodes> <level two nodes>
Represents the following 3-ary tree:
Example 1:
Example 2:
Represents the following 4-ary tree:
Explanation: First character represents m of the m-ary tree. It is the maximum number of children a node can have. Next character is the root node. Root node is followed by level 1 nodes which are root’s children in order from left to right. Then, followed by level 2 nodes which are level 1 node’s children and so on. If a node does not have the maximum m children, the space for those children will be filled by the underscore symbol. i.e. “_” is just a placeholder for empty children. It should only be used to figuring out whose children are whose. For examples, for a 3-ary tree, the input text file starts with 3. The 30 characters for level 1 nodes, 31 characters for level 2 nodes, 32
characters for level 3 nodes, and so on. Each character is separated by one empty space “ ”. Sample input files given with the assignment: input1.txt, input2.txt
Methods:
public static MTreeNode<String> createMTree(String fileName) accepts a file name and returns the root node of your m-ary tree. Method should throw an IOException if the file is not found. Include this method in MTreeNode class.
Note on input format: The given examples are single character nodes but your code should handle more than just letters. Some sample inputs are given below:
“2 root level1node1 level1node2 level2node1 level2node2 level2node3 level2node4”
(a total of 𝑁 = 2h+1 −1 “2 root level1node1
(a total of 𝑁 = 2h+1 −1 2−1
words including underscores after 2, where h is the height) 2−1
_ level2node1 level2node2 _ _” words including underscores after 2, where h is the height)
“3 animal human cat dog student professor _ _ _ _ pug lab _”
(a total of 𝑁 = 3h+1 −1
“4 STEGEN ALBA MASCHERANO PIQUE
RAKITIC _ _ _ _ _ _ _”
(a total of 𝑁 = 4h+1 −1 4−1
words including underscores after 3, where his the height) 3−1
_ INIESTA _ _ _ BUSQUETS _ _ _ words including underscores after 3 4, where his the height)
TASK 3
Given a m-arytree, convert it into its binary tree using Last Child Left Sibling method. From To
Method Signature:
public static <AnyType>
BinTreeNode<AnyType> createBinTree(MTreeNode<AnyType> mroot) accepts a MTreeNode which is the root of the m-ary tree and returns the root of the binary tree created. Include this method in MTreeNode class.
You will need to create BinTreeNode class for this task. An outline is given below:
Class Name:
BinTreeNode<AnyType> Instance variables:
1. AnyType element
2. BinTreeNode lastChild 3. BinTreeNode leftSibling
Constructors:
1. public BinTreeNode (AnyType element, BinTreeNode<AnyType> lastChild, BinTreeNode<AnyType> leftSibling)
2. public BinTreeNode (AnyType el)
Methods:
1. public static int height(BinTreeNode<?> t) returns the height of the tree rooted at t and -1 if null
2. public static int size(BinTreeNode<?> t) returns the size of the tree rooted at t and 0 if null
3. public String toStringPreOrder() returns a String representation of a pre- order walk on the binary tree rooted at this node.
4. public String toStringPostOrder()returns a String representation of a post- order walk on the binary tree rooted at this node.
5. public String toStringLevelOrder()returns a String representation of a level-order walk on the binary tree rooted at this node.
6. Task 5
Again, all walks are from right to left as compared to the
traditional left to right.
Example Outputs of tree traversals on the binary tree given on the
right:
Pre-order: “A D F L K E C B I J H G” Post-order: “K L E F J G H I B C D A”
Level-order: “A D F C L E B K I J H G”
TASK 4
Simulate pre-order, post-order, and level-order of the m-ary tree using the binary tree created from the m-arytree. You should be getting the exact same results as Task 1. Add the following methods to the BinTreeNode class.
Methods:
7. public String toStringPreOrderMTree()returns a String representation of a pre-order walk on the m-ary tree rooted at this node.
8. public String toStringPostOrderMTree()returns a String representation of a post-order walk on the m-ary tree rooted at this node.
9. public String toStringLevelOrderMTree()returns a String representation of a level-order walk on the m-ary tree rooted at this node.
Hint: Here your goal is to simulate the M-ary tree traversals using its Binary Tree representation. As you may have noticed from task 3, a simple pre/post/level order traversals on the Binary Tree will not produce the traversals that match its corresponding M-ary tree traversals. A slight twist to the
steps in task 3 can produce the M-ary Tree traversal results. Closely look at the paths of M-ary Tree (Task 1) and Binary Tree (Task 3) traversals and see if you can figure out what the trick is.
TASK 5
Convert the Binary Tree back to its corresponding M-ary Tree. From To
Method Signature:
public static <AnyType> MTreeNode<AnyType> createMTree(BinTreeNode<AnyType> broot)
accepts a BinTreeNode which is the root of the binary tree and returns the root of the m-ary tree created. Include this method in MTreeNode class.
TASK 6
Add a leafRemove method in the two tree classes which will remove the node with the given element only-if the node is a leaf. The method returns true if the node is removed successfully and returns false if removal is not possible.
Method Signatures:
public static <AnyType extends Comparable<AnyType>> boolean leafRemove(BinTreeNode<AnyType> root, AnyType valueToRemove) Include this method in BinTreeNode class.
public static <AnyType extends Comparable<AnyType>> boolean leafRemove(MTreeNode<AnyType> root, AnyType valueToRemove) Include this method in MTreeNode class.
TEST.JAVA
Use test.java provided along with the project to compile and check the correctness of your method signatures.
Basic Procedures
You must:
• Fill out a readme.txt file with your information (goes in your user folder, an example readme.txt file is provided)
• Have a style (indentation, good variable names, etc.)
• Comment your code well in JavaDoc style (no need to overdo it, just do it well)
• Have code that compiles with the command: javac *.java in your user directory
• Build your own Queues
• Make all the instance variables private and create public getter and setter methods
You may:
• Build your own ArrayList
• Add additional static nested classes with non-private methods, but the nested class itself must
be private
o Hint: add a Queue and ArrayList class with as many public/private methods andvariables
as you want
• Import: java.io.*, java.util.Scanner You may not:
• Make your program part of a package.
• Add additional public methods or variables to MTreeNode and BinTreeNode classes
• Use any built in Java Collections Framework classes anywhere in your program(e.g. no
ArrayList, LinkedList, HashSet, etc.)
• Add any additional libraries/packages which require downloading from the internet.
• Implement First Child Next Sibling method. We are implementing a mirror-image of the
method given in the textbook
• Create an empty node storing “_” from the text file
• Use the textbook author's code anywhere in your program, for trees, queues, lists, or any
other data structures

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.

class BinTreeNode<AnyType> {

public static void leafRemove(BinTreeNode<String> myNode, String e) {

if (myNode == null) {

return;

}

BinTreeNode<String> btn = myNode.leftSibling;

if (btn != null) {

if (btn.element.equals(e)) {

if (btn.lastChild == null

&& btn.leftSibling == null) {

myNode.leftSibling = null;

}

return;

}

leafRemove(btn, e);

}

btn = myNode.lastChild;

if (btn != null) {

if (btn.element.equals(e)) {

if (btn.lastChild == null

&& btn.leftSibling == null) {

myNode.lastChild = null;

}

return;

}

leafRemove(btn, e);

}

}

private AnyType element;

private BinTreeNode lastChild;

private BinTreeNode leftSibling;

private int m;

public BinTreeNode(AnyType element, BinTreeNode<AnyType> lastChild,

BinTreeNode<AnyType> leftSibling) {

this.element = element;

this.leftSibling = leftSibling;

this.lastChild = lastChild;

}

public BinTreeNode(AnyType el) {

this.element = el;

this.leftSibling = null;

this.lastChild = null;

}

public void setLastChild(BinTreeNode lastChild) {

this.lastChild = lastChild;

}

public void setLeftSibling(BinTreeNode leftSibling) {

this.leftSibling = leftSibling;

}...