Question

Add a non-recursive inorder() method to class LinkedBinaryTree<E> to traverse binary tree. Test inorder() method. Implementation in Java

#########LinkedBinary Tree class#########

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

//---------------- nested Node class ----------------
/** Nested static class for a binary tree node. */
protected static class Node<E> implements Position<E> {
private E element; // an element stored at this node
private Node<E> parent; // a reference to the parent node (if any)
private Node<E> left; // a reference to the left child (if any)
private Node<E> right; // a reference to the right child (if any)

public Node(E e, Node<E> above, Node<E> leftChild, Node<E> rightChild) {
element = e;
parent = above;
left = leftChild;
right = rightChild;
}

// accessor methods
public E getElement() { return element; }
public Node<E> getParent() { return parent; }
public Node<E> getLeft() { return left; }
public Node<E> getRight() { return right; }

// update methods
public void setElement(E e) { element = e; }
public void setParent(Node<E> parentNode) { parent = parentNode; }
public void setLeft(Node<E> leftChild) { left = leftChild; }
public void setRight(Node<E> rightChild) { right = rightChild; }
} //----------- end of nested Node class -----------

/** Factory function to create a new node storing element e. */
protected Node<E> createNode(E e, Node<E> parent,
Node<E> left, Node<E> right) {
return new Node<E>(e, parent, left, right);
}

// LinkedBinaryTree instance variables
/** The root of the binary tree */
protected Node<E> root = null; // root of the tree

/** The number of nodes in the binary tree */
private int size = 0; // number of nodes in the tree

// constructor
/** Construts an empty binary tree. */
public LinkedBinaryTree() { } // constructs an empty binary tree

// nonpublic utility

protected Node<E> validate(Position<E> p) throws IllegalArgumentException {
if (!(p instanceof Node))
throw new IllegalArgumentException("Not valid position type");
Node<E> node = (Node<E>) p; // safe cast
if (node.getParent() == node) // our convention for defunct node
throw new IllegalArgumentException("p is no longer in the tree");
return node;
}

// accessor methods (not already implemented in AbstractBinaryTree)

@Override
public int size() {
return size;
}

@Override
public Position<E> root() {
return root;
}

@Override
public Position<E> parent(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return node.getParent();
}

  
@Override
public Position<E> left(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return node.getLeft();
}

@Override
public Position<E> right(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
return node.getRight();
}

// update methods supported by this class

public Position<E> addRoot(E e) throws IllegalStateException {
if (!isEmpty()) throw new IllegalStateException("Tree is not empty");
root = createNode(e, null, null, null);
size = 1;
return root;
}

public Position<E> addLeft(Position<E> p, E e)
throws IllegalArgumentException {
Node<E> parent = validate(p);
if (parent.getLeft() != null)
throw new IllegalArgumentException("p already has a left child");
Node<E> child = createNode(e, parent, null, null);
parent.setLeft(child);
size++;
return child;
}

  
public Position<E> addRight(Position<E> p, E e)
throws IllegalArgumentException {
Node<E> parent = validate(p);
if (parent.getRight() != null)
throw new IllegalArgumentException("p already has a right child");
Node<E> child = createNode(e, parent, null, null);
parent.setRight(child);
size++;
return child;
}

public E set(Position<E> p, E e) throws IllegalArgumentException {
Node<E> node = validate(p);
E temp = node.getElement();
node.setElement(e);
return temp;
}

  
public void attach(Position<E> p, LinkedBinaryTree<E> t1,
LinkedBinaryTree<E> t2) throws IllegalArgumentException {
Node<E> node = validate(p);
if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");
size += t1.size() + t2.size();
if (!t1.isEmpty()) { // attach t1 as left subtree of node
t1.root.setParent(node);
node.setLeft(t1.root);
t1.root = null;
t1.size = 0;
}
if (!t2.isEmpty()) { // attach t2 as right subtree of node
t2.root.setParent(node);
node.setRight(t2.root);
t2.root = null;
t2.size = 0;
}
}

  
public E remove(Position<E> p) throws IllegalArgumentException {
Node<E> node = validate(p);
if (numChildren(p) == 2)
throw new IllegalArgumentException("p has two children");
Node<E> child = (node.getLeft() != null ? node.getLeft() : node.getRight() );
if (child != null)
child.setParent(node.getParent()); // child's grandparent becomes its parent
if (node == root)
root = child; // child becomes root
else {
Node<E> parent = node.getParent();
if (node == parent.getLeft())
parent.setLeft(child);
else
parent.setRight(child);
}
size--;
E temp = node.getElement();
node.setElement(null); // help garbage collection
node.setLeft(null);
node.setRight(null);
node.setParent(node); // our convention for defunct node
return temp;
}
  
public static void main(String[] args)
{
   //create and populate a linked binary tree
   LinkedBinaryTree lbt = new LinkedBinaryTree();
   Position<String> root =lbt.addRoot("ICET");
  
   //  
   Position<String> softwarePosition = lbt.addLeft(root, "Software");
   Position<String> networkingPosition = lbt.addRight(root, "Networking");
   Position<String> set = lbt.addLeft(softwarePosition, "SET");
   Position<String> ig = lbt.addRight(softwarePosition, "IG");

   //
   printPreorder(lbt);
  
}
//
public static <E> void printPreorder(AbstractTree<E> T) {
   for (Position<E> p : T.preorder())
   System.out.println(p.getElement());
}//

} //----------- end of LinkedBinaryTree class -----------

Answer 1

import java.util.Stack; // used for non-recursive inorder traversal

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

//---------------- nested Node class ----------------

/** Nested static class for a binary tree node. */

protected static class Node<E> implements Position<E> {

private E element; // an element stored at this node

private Node<E> parent; // a reference to the parent node (if any)

private Node<E> left; // a reference to the left child (if any)

private Node<E> right; // a reference to the right child (if any)

public Node(E e, Node<E> above, Node<E> leftChild, Node<E> rightChild) {

element = e;

parent = above;

left = leftChild;

right = rightChild;

}

// accessor methods

public E getElement() { return element; }

public Node<E> getParent() { return parent; }

public Node<E> getLeft() { return left; }

public Node<E> getRight() { return right; }

// update methods

public void setElement(E e) { element = e; }

public void setParent(Node<E> parentNode) { parent = parentNode; }

public void setLeft(Node<E> leftChild) { left = leftChild; }

public void setRight(Node<E> rightChild) { right = rightChild; }

} //----------- end of nested Node class -----------

/** Factory function to create a new node storing element e. */

protected Node<E> createNode(E e, Node<E> parent,

Node<E> left, Node<E> right) {

return new Node<E>(e, parent, left, right);

}

// LinkedBinaryTree instance variables

/** The root of the binary tree */

protected Node<E> root = null; // root of the tree

/** The number of nodes in the binary tree */

private int size = 0; // number of nodes in the tree

// constructor

/** Construts an empty binary tree. */

public LinkedBinaryTree() { } // constructs an empty binary tree

// nonpublic utility

protected Node<E> validate(Position<E> p) throws IllegalArgumentException {

if (!(p instanceof Node))

throw new IllegalArgumentException("Not valid position type");

Node<E> node = (Node<E>) p; // safe cast

if (node.getParent() == node) // our convention for defunct node

throw new IllegalArgumentException("p is no longer in the tree");

return node;

}

// accessor methods (not already implemented in AbstractBinaryTree)

@Override

public int size() {

return size;

}

@Override

public Position<E> root() {

return root;

}

@Override

public Position<E> parent(Position<E> p) throws IllegalArgumentException {

Node<E> node = validate(p);

return node.getParent();

}

@Override

public Position<E> left(Position<E> p) throws IllegalArgumentException {

Node<E> node = validate(p);

return node.getLeft();

}

@Override

public Position<E> right(Position<E> p) throws IllegalArgumentException {

Node<E> node = validate(p);

return node.getRight();

}

// update methods supported by this class

public Position<E> addRoot(E e) throws IllegalStateException {

if (!isEmpty()) throw new IllegalStateException("Tree is not empty");

root = createNode(e, null, null, null);

size = 1;

return root;

}

public Position<E> addLeft(Position<E> p, E e)

throws IllegalArgumentException {

Node<E> parent = validate(p);

if (parent.getLeft() != null)

throw new IllegalArgumentException("p already has a left child");

Node<E> child = createNode(e, parent, null, null);

parent.setLeft(child);

size++;

return child;

}

public Position<E> addRight(Position<E> p, E e)

throws IllegalArgumentException {

Node<E> parent = validate(p);

if (parent.getRight() != null)

throw new IllegalArgumentException("p already has a right child");

Node<E> child = createNode(e, parent, null, null);

parent.setRight(child);

size++;

return child;

}

public E set(Position<E> p, E e) throws IllegalArgumentException {

Node<E> node = validate(p);

E temp = node.getElement();

node.setElement(e);

return temp;

}

public void attach(Position<E> p, LinkedBinaryTree<E> t1,

LinkedBinaryTree<E> t2) throws IllegalArgumentException {

Node<E> node = validate(p);

if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");

size += t1.size() + t2.size();

if (!t1.isEmpty()) { // attach t1 as left subtree of node

t1.root.setParent(node);

node.setLeft(t1.root);

t1.root = null;

t1.size = 0;

}

if (!t2.isEmpty()) { // attach t2 as right subtree of node

t2.root.setParent(node);

node.setRight(t2.root);

t2.root = null;

t2.size = 0;

}

}

public E remove(Position<E> p) throws IllegalArgumentException {

Node<E> node = validate(p);

if (numChildren(p) == 2)

throw new IllegalArgumentException("p has two children");

Node<E> child = (node.getLeft() != null ? node.getLeft() : node.getRight() );

if (child != null)

child.setParent(node.getParent()); // child's grandparent becomes its parent

if (node == root)

root = child; // child becomes root

else {

Node<E> parent = node.getParent();

if (node == parent.getLeft())

parent.setLeft(child);

else

parent.setRight(child);

}

size--;

E temp = node.getElement();

node.setElement(null); // help garbage collection

node.setLeft(null);

node.setRight(null);

node.setParent(node); // our convention for defunct node

return temp;

}

// method to implement inorder traversal of the tree

public void inorder()

{

               if(root != null)

               {

                              Stack<Node<E>> stack = new Stack<Node<E>>();

                              Node<E> curr = root;

                             

                              while(curr != null || stack.size() > 0)

                              {

                                             // push all nodes into the stack, while reaching the leftmost node of curr

                                             while(curr != null)

                                             {

                                                            stack.push(curr);

                                                            curr = curr.getLeft();

                                             }

                                             curr = stack.pop();          

                                             System.out.print(curr.getElement()+" ");

                                            

                                             // Node and left subtree has been printed , now traverse its right subtree

                                             curr = curr.getRight();

                              }

               }

}

   

public static void main(String[] args)

{

   //create and populate a linked binary tree

   LinkedBinaryTree lbt = new LinkedBinaryTree();

   Position<String> root =lbt.addRoot("ICET");

   //

   Position<String> softwarePosition = lbt.addLeft(root, "Software");

   Position<String> networkingPosition = lbt.addRight(root, "Networking");

   Position<String> set = lbt.addLeft(softwarePosition, "SET");

   Position<String> ig = lbt.addRight(softwarePosition, "IG");

   //

   printPreorder(lbt);

}

//

public static <E> void printPreorder(AbstractTree<E> T) {

   for (Position<E> p : T.preorder())

   System.out.println(p.getElement());

}//

} //----------- end of LinkedBinaryTree class -----------