Tree ra es AaBbCcDd AaBbCc 1 Normal 1 No Spa Paragraph Tree Traverse Lab Today y
ID: 3704921 • Letter: T
Question
Tree ra es AaBbCcDd AaBbCc 1 Normal 1 No Spa Paragraph Tree Traverse Lab Today you will be implementing a simple tree sructure and getting the inorder, postorder, and preorder traversals of this tree In this Lab you will create 2 java files. One will be the main file in which to test your program and the other will contain the Tree ADT Let's start by discussing what will need to be contained within the Tree ADT dass There should be a private Node dass contained within the Tree ADTdass This Node dand contain the fields: data of type Generic, left of type Node and right of type Node. All the methods within this class should be private There should be 2 constructors within this dass One which takes in no parameters and one which takes in a data paramoter Other Methods to be implemented are listed below Getters- get the value from the ields getData getRighNode Setters -set the values of the fields setData) setL eftNode0 Copy * O-copy's the tree and returns the root Node Now to implement the Tree ADT There should be a root Node field which is set to peivate Please implement two constructors: One that takes in no parameters and the other which takes in a data parameter Note that the bellow methods should be public unless otherwise specified Inorder Traversalo .preorder Traversalo . isEmpty0 setTree)-This method should take in a new data value and two trees It will make the postorder Traversal( clear) data value the new node, while making one tree the left branch of this node and the other tree the right branch of this node PsExplanation / Answer
/*------------- TREE ADT CLASS WITH METHODS ----------------*/
private class Node
{
//1. ------------ Fields -------------//
< E > data;
Node left, right;
// 2. ----------- Constructors -------------//
//----Non Parameterized Constructor
public Node()
{
data = null;
left = right = null;
}
//----Parameterized Constructor
public Node(< E > data)
{
this.data = data;
left = right = null;
}
//3.------ Getter Methods--------------//
public <E> getData()
{
return data;
}
public Node getLeftNode()
{
return left;
}
public Node getRightNode()
{
return right;
}
//3.------ Setter Methods--------------//
public void setData(< E > data)
{
this.data = data;
}
public void setLeftNode(Node left)
{
this.left = left;
}
public void setRightNode(Node right)
{
this.right = right;
}
//4. ------- Copy Tree Method -------------//
public Node copy() {
Node left = null;
Node right = null;
if (this.left != null) {
left = this.left.copy();
}
if (this.right != null) {
right = this.right.copy();
}
return new Node(value, left, right);
}
}
/*--------------------- TREE ADT IMPLEMENTATION ---------------------*/
class SimpleTree
{
// 5. Root Node of SimpleTree
private Node root;
// 6. ----------- Constructors -------------//
//Non Parameterized Constructor
SimpleTree()
{
root = null;
}
//Parameterized Constructor
SimpleTree(< E > data)
{
root = new Node(data);
}
//------------------TREE METHODS ---------------------//
/*7. ----- Inorder Traversal ---- */
public void inorderTraversal(Node node)
{
if (node == null)
return;
/* first recur on left child */
inorderTraversal(node.left);
/* then print the data of node */
System.out.print(node.key + " ");
/* now recur on right child */
inorderTraversal(node.right);
}
/*8. ------ Preorder Traversal -----*/
public void preorderTraversal(Node node)
{
if (node == null)
return;
/* first print data of node */
System.out.print(node.key + " ");
/* then recur on left sutree */
preorderTraversal(node.left);
/* now recur on right subtree */
preorderTraversal(node.right);
}
/*9. ------ Postorder Traversal -------*/
public void postorderTraversal(Node node)
{
if (node == null)
return;
// first recur on left subtree
postorderTraversal(node.left);
// then recur on right subtree
postorderTraversal(node.right);
// now deal with the node
System.out.print(node.key + " ");
}
/*10 -------- is empty method ----------- */
public boolean isEmpty()
{
if(root == null) return true;
else return false;
}
/*11 ------- clear method ----------*/
public void clear()
{
root = null;
}
/*12 -------- set tree method --------*/
public void setTree(Node root) {
this.root = root;
}
// Wrappers over above recursive functions
public void inorderTraversal() { inorderTraversal(root); }
public void preorderTraversal() { preorderTraversal(root); }
public void postorderTraversal() { postorderTraversal(root); }
// Main method
public static void main(String[] args)
{
SimpleTree tree = new SimpleTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Preorder traversal of binary tree is ");
tree.preorderTraversal();
System.out.println(" Inorder traversal of binary tree is ");
tree.inorderTraversal();
System.out.println(" Postorder traversal of binary tree is ");
tree.postorderTraversal();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.