There are other questions like this on here but read careully instructions becau
ID: 3710255 • Letter: T
Question
There are other questions like this on here but read careully instructions because my teachers has tweaked a couple things on it.
Objective: The objective of this lab is to help the students have a better understanding of the reference based implementation of a Binary tree. The LAB will go back to a common node structure with each node only has two references refers to the left child and right child (no direct reference to its parent). This will help the students better adjust their learning to popular interview questions they may have to deal with in their future interviews. The LAB provides a simpler implementation for the linked binary tree discussed in class but slightly different (the size variable is removed from the binary tree class, the parent reference variable for each node has also been removed).
Create a project and put/copy all files in the simple binary treefolder and paste into the srcfolder. Remark: the size variable and parent reference have already been removed. You are recommended to read the provided code first, to figure out what is already available.
Due to the changes, the original implementation of the following methods will no longer work. Please based on this change, make necessary changes to the following methods
publicintsize() //return the number of nodes
public Node<E> parent(Node<E> p) throws IllegalArgumentException //return the parent node for a node referred by p
Add and implement the following methods within the class:
public boolean isIdentical(Node<E> p1, Node<E> p2):check if two binary trees rooted at p1 and p2 are identical or not. i.e. if they have identical structure & their contents are also same. Return true for yes and false, otherwise.
public ArrayList<Node<E>> ancestors(Node<E>p1, Node<E> p2):find all ancestors of a given node referred by p2 on a tree rooted at p1.
The following is the code from the method we were told to change.
package simpleBinaryTree;
import java.util.ArrayList;
public class simpleLinkedBinaryTree<E extends Comparable<E>> {
protected Node<E> root = null; // root of the tree
public simpleLinkedBinaryTree() { }//constructor_Construts an empty binary tree.
// Returns the root of the tree (or null if tree is empty).
public Node<E> root() {
return root;
}
public boolean isEmpty() { return root == null; }
public int numChildren(Node<E> p) {
int count=0;
if(p.getLeft()!=null) count++;
if(p.getRight()!=null) count++;
return count;
}
public ArrayList<Node<E>> children(Node<E> p) {
ArrayList<Node<E>> snapshot = new ArrayList<>(2); // max capacity of 2
if (left(p) != null)
snapshot.add(left(p));
if (right(p) != null)
snapshot.add(right(p));
return snapshot;
}
public boolean isInternal(Node<E> p) { return numChildren(p) > 0; }
public boolean isExternal(Node<E> p) { return numChildren(p) == 0; }
public Node<E> left(Node<E> p) throws IllegalArgumentException {
return p.getLeft();
}
public Node<E> right(Node<E> p) throws IllegalArgumentException {
return p.getRight();
}
// update methods supported by this class
/**
* Places element e at the root of an empty tree and returns its new Position.
*
* @param e the new element
* @return the Position of the new element
* @throws IllegalStateException if the tree is not empty
*/
public Node<E> addRoot(E e) throws IllegalStateException {
if (!isEmpty()) throw new IllegalStateException("Tree is not empty");
root = new Node<E>(e, null, null);
return root;
}
/**
* Creates a new left child of Position p storing element e and returns its Position.
*/
public Node<E> addLeft(Node<E> p, E e)
throws IllegalArgumentException {
if (p.getLeft() != null)
throw new IllegalArgumentException("p already has a left child");
Node<E> child = new Node<E>(e, null, null);
p.setLeft(child);
return child;
}
/**
* Creates a new right child of Position p storing element e and returns its Position.
*/
public Node<E> addRight(Node<E> p, E e)
throws IllegalArgumentException {
if (p.getRight() != null)
throw new IllegalArgumentException("p already has a right child");
Node<E> child = new Node<E>(e,null, null);
p.setRight(child);
return child;
}
/**
* Replaces the element at Position p with element e and returns the replaced element.
*/
public E set(Node<E> p, E e) throws IllegalArgumentException {
E temp = p.getElement();
p.setElement(e);
return temp;
}
public void attach(Node<E> p, simpleLinkedBinaryTree<E> t1,
simpleLinkedBinaryTree<E> t2) throws IllegalArgumentException {
if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");
if (!t1.isEmpty()) { // attach t1 as left subtree of node
p.setLeft(t1.root);
t1.root = null;
}
if (!t2.isEmpty()) { // attach t2 as right subtree of node
p.setRight(t2.root);
t2.root = null;
}
}
public E remove(Node<E> p) throws IllegalArgumentException {
if (numChildren(p) == 2)
throw new IllegalArgumentException("p has two children");
Node<E> child = (p.getLeft() != null ? p.getLeft() : p.getRight() );
if (p == root)
root = child; // child becomes root
else {
Node<E> parent = (Node<E>) parent(p);
if (p == parent.getLeft())
parent.setLeft(child);
else
parent.setRight(child);
}
E temp = p.getElement();
p.setElement(null); // help garbage collection
p.setLeft(null);
p.setRight(null);
return temp;
}
//pre_order traversal
private void preorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
snapshot.add(p); // for preorder, we add position p before exploring subtrees
for (Node<E> c : children(p))
preorderSubtree(c, snapshot);
}
public ArrayList<Node<E>> preorder() {
ArrayList<Node<E>> snapshot = new ArrayList<>();
if (!isEmpty())
preorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}
//in_order traversal
private void inorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
if (left(p) != null)
inorderSubtree(left(p), snapshot);
snapshot.add(p);
if (right(p) != null)
inorderSubtree(right(p), snapshot);
}
public ArrayList<Node<E>> inorder() {
ArrayList<Node<E>> snapshot = new ArrayList<Node<E>>();
if (!isEmpty())
inorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}
//post_order traversal
private void postorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
for (Node<E> c : children(p))
postorderSubtree(c, snapshot);
snapshot.add(p); // for postorder, we add position p after exploring subtrees
}
public ArrayList<Node<E>> postorder() {
ArrayList<Node<E>> snapshot = new ArrayList<Node<E>>();
if (!isEmpty())
postorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}
/****************************************************************************************/
/*****************Your LAB starts here!******************/
/****************************************************************************************/
//Returns the number of nodes in the tree.
public int size() {
}
//Returns the Node of p's parent (or null if p is root).
public Node<E> parent(Node<E> p1, Node<E> p2){
}
public boolean isIdentical(Node<E> p1, Node<E> p2){
}
public ArrayList<Node<E>> ancestors(Node<E> p1, Node<E> p2)
{
return null;
}
}
Explanation / Answer
package simpleBinaryTree;
import java.util.ArrayList;
public class simpleLinkedBinaryTree<E extends Comparable<E>> {
static class Node<E> {
Node<E> left, right;
E data1;
Node(E data, Node<E> left, Node<E> right) {
this.data1 = data1;
this.left = left;
this.right = right;
}
Node<E> getLeft() {return left;}
Node<E> getRight() {return right;}
E getElement(){return data1;}
void setElement(E data1) { this.data1 = data1;}
void setLeft(Node<E> left) {
this.left = left;
}
void setRight(Node<E> right) {
this.right = right;
}
}
protected Node<E> root = null; // root of the tree
public simpleLinkedBinaryTree() { }//constructor_Construts an empty binary tree.
// Returns the root of the tree (or null if tree is empty).
public Node<E> root() {
return root;
}
public boolean isEmpty() { return root == null; }
public int numChildren(Node<E> p) {
int count=0;
if(p.getLeft()!=null) count++;
if(p.getRight()!=null) count++;
return count;
}
public ArrayList<Node<E>> children(Node<E> p) {
ArrayList<Node<E>> snapshot = new ArrayList<>(2); // max capacity of 2
if (left(p) != null)
snapshot.add(left(p));
if (right(p) != null)
snapshot.add(right(p));
return snapshot;
}
public boolean isInternal(Node<E> p) { return numChildren(p) > 0; }
public boolean isExternal(Node<E> p) { return numChildren(p) == 0; }
public Node<E> left(Node<E> p) throws IllegalArgumentException {
return p.getLeft();
}
public Node<E> right(Node<E> p) throws IllegalArgumentException {
return p.getRight();
}
// update methods supported by this class
/**
* Places element e at the root of an empty tree and returns its new Position.
*
* @param e the new element
* @return the Position of the new element
* @throws IllegalStateException if the tree is not empty
*/
public Node<E> addRoot(E e) throws IllegalStateException {
if (!isEmpty()) throw new IllegalStateException("Tree is not empty");
root = new Node<E>(e, null, null);
return root;
}
/**
* Creates a new left child of Position p storing element e and returns its Position.
*/
public Node<E> addLeft(Node<E> p, E e)
throws IllegalArgumentException {
if (p.getLeft() != null)
throw new IllegalArgumentException("p already has a left child");
Node<E> child = new Node<E>(e, null, null);
p.setLeft(child);
return child;
}
/**
* Creates a new right child of Position p storing element e and returns its Position.
*/
public Node<E> addRight(Node<E> p, E e)
throws IllegalArgumentException {
if (p.getRight() != null)
throw new IllegalArgumentException("p already has a right child");
Node<E> child = new Node<E>(e,null, null);
p.setRight(child);
return child;
}
/**
* Replaces the element at Position p with element e and returns the replaced element.
*/
public E set(Node<E> p, E e) throws IllegalArgumentException {
E temp = p.getElement();
p.setElement(e);
return temp;
}
public void attach(Node<E> p, simpleLinkedBinaryTree<E> t1,
simpleLinkedBinaryTree<E> t2) throws IllegalArgumentException {
if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");
if (!t1.isEmpty()) { // attach t1 as left subtree of node
p.setLeft(t1.root);
t1.root = null;
}
if (!t2.isEmpty()) { // attach t2 as right subtree of node
p.setRight(t2.root);
t2.root = null;
}
}
public E remove(Node<E> p) throws IllegalArgumentException {
if (numChildren(p) == 2)
throw new IllegalArgumentException("p has two children");
Node<E> child = (p.getLeft() != null ? p.getLeft() : p.getRight() );
if (p == root)
root = child; // child becomes root
else {
Node<E> parent = (Node<E>) parent(p, root);
if (p == parent.getLeft())
parent.setLeft(child);
else
parent.setRight(child);
}
E temp = p.getElement();
p.setElement(null); // help garbage collection
p.setLeft(null);
p.setRight(null);
return temp;
}
//pre_order traversal
private void preorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
snapshot.add(p); // for preorder, we add position p before exploring subtrees
for (Node<E> c : children(p))
preorderSubtree(c, snapshot);
}
public ArrayList<Node<E>> preorder() {
ArrayList<Node<E>> snapshot = new ArrayList<>();
if (!isEmpty())
preorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}
//in_order traversal
private void inorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
if (left(p) != null)
inorderSubtree(left(p), snapshot);
snapshot.add(p);
if (right(p) != null)
inorderSubtree(right(p), snapshot);
}
public ArrayList<Node<E>> inorder() {
ArrayList<Node<E>> snapshot = new ArrayList<Node<E>>();
if (!isEmpty())
inorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}
//post_order traversal
private void postorderSubtree(Node<E> p, ArrayList<Node<E>> snapshot) {
for (Node<E> c : children(p))
postorderSubtree(c, snapshot);
snapshot.add(p); // for postorder, we add position p after exploring subtrees
}
public ArrayList<Node<E>> postorder() {
ArrayList<Node<E>> snapshot = new ArrayList<Node<E>>();
if (!isEmpty())
postorderSubtree(root(), snapshot); // fill the snapshot recursively
return snapshot;
}
/****************************************************************************************/
/*****************Your LAB starts here!******************/
/****************************************************************************************/
//Returns the number of nodes in the tree.
public int size() {
return countNodesInTree(root);
}
private int countNodesInTree(Node<E> node) {
if(node == null) return 0;
return 1 + countNodesInTree(node.getLeft()) + countNodesInTree(node.getRight());
}
//Returns the Node of p's parent (or null if p is root).
public Node<E> parent(Node<E> node, Node<E> root){
return _parent(node, root);
}
public Node<E> _parent(Node<E> node, Node<E> parent){
if(node == null || parent == null) return null;
if(node.equals(parent.getLeft()) || node.equals(parent.getRight())) return parent;
Node<E> par = _parent(node, parent.getLeft());
if(par != null) return par;
return _parent(node, parent.getRight());
}
public boolean isIdentical(Node<E> p1, Node<E> p2){
if(p1 == null && p2 == null) return true;
if(p1 == null || p2 == null) return false;
if(p1.getElement().equals(p2.getElement())) {
return isIdentical(p1.getLeft(), p2.getLeft());
}
return false;
}
// P1 is root, p2 is node
public ArrayList<Node<E>> ancestors(Node<E> p1, Node<E> p2) {
ArrayList<Node<E>> _ancestors = new ArrayList<>();
if(p1 != null && p2 != null) {
ancestors(p1, p2, _ancestors);
}
return _ancestors;
}
public void ancestors(Node<E> p1, Node<E> p2, ArrayList<Node<E>> _ancestors) {
if(p2.equals(p1)) {
_ancestors.add(p1);
return;
}
if(p1.getLeft() != null) {
ancestors(p1.getLeft(), p2, _ancestors);
}
if(_ancestors.isEmpty() && p1.getRight() != null) {
ancestors(p1.getRight(), p2, _ancestors);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.