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 see image.

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: see image.

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 cant 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: see image.

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>

Example 1: see image.

Example 2: see image.

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 roots children in order from left to right. Then, followed by level 2 nodes which are level 1 nodes 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 3⁰ characters for level 1 nodes, 3¹ characters for level 2 nodes, 3² 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 N = (2h+1 - 1) / (2-1) words including underscores after 2, where h is the height)

"2 root level1node1 _ level2node1 level2node2 _ _"
(a total of N = (2h+1 - 1) / (2-1) words including underscores after 2, where h is the height)

"3 animal human cat dog student professor _ _ _ _ pug lab _"
(a total of N = (3h+1 - 1) / (3-1) words including underscores after 3, where h is the height)

"4 STEGEN ALBA MASCHERANO PIQUE _ INIESTA _ _ _ BUSQUETS _ _ _ RAKITIC _ _ _ _ _ _ _"
(a total of N = (4h+1 - 1) / (4-1) words including underscores after 3, where h is the height)

TASK 3

Given a m-ary tree, convert it into its binary tree using Last Child Left Sibling method.

From see image.

To see image.

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 preorder walk on the binary tree rooted at this node.
4. public String toStringPostOrder() returns a String representation of a postorder 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. see image.

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-ary tree. You should be getting the exact same results as Task 1. Add the following methods to the BinTreeNode class.

Methods:

1. public String toStringPreOrderMTree() returns a String representation of a pre-order walk on the m-ary tree rooted at this node.
2. public String toStringPostOrderMTree() returns a String representation of a post-order walk on the m-ary tree rooted at this node.
3. 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 see image.

To see image.

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 and variables 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
• pub (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