I need help creating a Java m-ary tree node class: Class Name: MTreeNode Instanc

Question

I need help creating a Java m-ary tree node class:

Class Name: MTreeNode

Instance variables:
1. AnyType element
2. int m
3. ArrayList children

Constructors:
1. public MTreeNode (AnyType element, int m, ArrayList 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 boolean addChild(MTreeNode 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 shown below:
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

Explanation / Answer

Node-

public class Node {

private int value;

private Node lower;

private Node higher;

public void insert(int newValue) {

if (newValue < value)

if(lower == null)

lower=new Node(value);

else

lower.insert(newValue);

else

if(higher == null)

higher=new Node(value);

else

higher.insert(newValue);

}

// and you'll need a constructor

public Node(int value) {

this.value=value;

}

}

Tree-

import java.util.ArrayList;

import java.util.List;

public class Tree {

public Node root;

public Tree(int kArity)

{

Node.maxNrOfChildren=kArity;

}

public void addRoot(Object info)

{

root=new Node(info);

root.parent=null;

root.children=new ArrayList<Node>(Node.maxNrOfChildren);

}

public void addNewNodeVasithChildOfNodeU(Node u, Object info, int i)

{

Node child=new Node(info);

u.addChild(child, i);

}

// I've made the above two methods of type void, not Node, because

// I see no reason in returning anything; however, you can override by calling

//'return root;' or 'return child;'

public int numberOfNodesInTree(Node rootNode){

int count=0;

count++;

if(rootNode.children.size()!=0) {

for(Node ch : rootNode.children)

count=count+numberOfNodesInTree(ch);

}

return count;

}

public int numberOfNodesInTree()

{

return numberOfNodesInTree(this.root);

}

public void changeRoot(Node newRoot, int i)

{

Node oldRoot=this.root;

newRoot.parent=null;

newRoot.addChild(oldRoot, i);

oldRoot.parent=newRoot;

this.root=newRoot;

}

public static void main(String args[])

{

Tree tree=new Tree(3);

Node a = new Node("a");

Node b = new Node("b");

Node c = new Node("c");

tree.addRoot("root");

tree.root.addChild(a,0);

a.addChild(b,0);

tree.root.addChild(c,1);

System.out.println(tree.numberOfNodesInTree(tree.root));

}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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