Create an implementation of a binary tree using the recursiv

\"Create an implementation of a binary tree using the recursive approach introduced in the chapter. In this approach, each node is a binary tree. Thus a binary tree contains a reference to the element stored at its root as well as references to its left and right subtrees. You may also want to include a reference to its parent.\" p.741

You need to use the locally implemented binary tree. This means you need to have a \"jsjf\" subfolder with at least these files: BinaryTreeADT.java, LinkedBinaryTree.java, BinaryTreeNode.java, and the exceptions sub-subfolder.

Test/demonstrate your binary tree by doing the following:

Request file name from user,

Read an infix expression from file,

Build binary expression tree,

Display binary expression tree,

Evaluate binary expression tree,

Display result.

##############################################

Note a typical input file can be found here

##############################################

# Version 0.2, fully parenthesized.
# This is a comment

((9 + 4) * 5) + (4 - (6 + 3))
# Note first expression should evaluate to 60

((42 + ( 10 - 2 )) + ( 5 * 3 )) / 6
# Note second expression should evaluate to 65 / 6 or 10 (integer division)

##############################################

My program is below but the out put is incorrect

##############################################

StringTree.java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;
import jsjf.BinaryTreeNode;
import jsjf.LinkedBinaryTree;

public class StringTree extends LinkedBinaryTree<String> {

public StringTree(String rootStr, StringTree leftSubtree, StringTree rightSubtree) {

root = new BinaryTreeNode<String>(rootStr, leftSubtree, rightSubtree);
} // StringTree

public StringTree(File f) {

       Stack<StringTree> leftStack = new Stack<StringTree>(), rightStack = new Stack<StringTree>();
       // stacks of left and right subtrees of nodes
       Scanner scan;
       // scanner for reading from the file
       String nodeType,
               nodeStr;
       // string contained in the current node
       boolean hasLeftChild, hasRightChild;
       // true if the current node has a left or right child
       StringTree leftSubtree, rightSubtree,
               // left and right subtrees of the current node
               subtree;
               // subtree having the current node as its root

       // Create a scanner for reading from the file.
       try {
           scan = new Scanner(f);
       } catch (FileNotFoundException e) {
           System.out.println(e.getMessage());
           root = null;
           System.out.println(\"\ \"+\"The program has terminated......\");
           System.exit(0);
           return;
       }

       // Read the file and build a tree from the bottom up.
       while (scan.hasNext()) {
           // Input information about a tree node.
           nodeType = scan.next();
           hasLeftChild = (scan.next().equalsIgnoreCase(\"y\"));
           hasRightChild = (scan.next().equalsIgnoreCase(\"y\"));
           nodeStr = scan.next();

           // Determine the left and right subtrees of the subtree
           // having the node as its root.
           if (hasLeftChild)
               leftSubtree = leftStack.pop();
           else
               leftSubtree = null;
           if (hasRightChild)
               rightSubtree = rightStack.pop();
           else
               rightSubtree = null;

// Create the subtree having the node as its root.
subtree = new StringTree(nodeStr, leftSubtree, rightSubtree);

           // Push the subtree onto the appropriate stack or finish
           // construction of the whole tree.
           if (nodeType.equalsIgnoreCase(\"L\"))
               leftStack.push(subtree);
           else if (nodeType.equalsIgnoreCase(\"R\"))
               rightStack.push(subtree);
           else {
               root = subtree.root;
               break;
           }
       } // while
   } // StringTree

public static void main(String[] args) {

       Scanner scan = new Scanner(System.in);
       // scanner to read keyboard input
       String name;
       // name of a tree description file
       File f;
       // the corresponding file object
       StringTree tree;
       // tree constructed from the file

       // Input a tree description file name and create a
       // corresponding file object.
       System.out.print(\"Enter a tree description file name: \");
       name = scan.nextLine();
       scan.close();
       f = new File(name);
       // Create a tree as described by the file.
       tree = new StringTree(f);
       // Display the tree.
       System.out.print(tree.toString());
       // Find and display the tree\'s height.
       System.out.println(\"The tree\'s height is: \" + tree.getHeight());
       // List the nodes in the order visited in a post-order
       // traversal.
       Iterator<String> post = tree.iteratorPostOrder();
       System.out.print(\"Traversed in PostOrder: \");
       while (post.hasNext()) {
           System.out.print(post.next() + \" \");
       }
       //Printing terminating message
       System.out.println(\"\ \"+\"\ \"+\"The program has terminated......\");
   } // main

} // class StringTree

// ***************************************************************

LinkedBinaryTree.java

package jsjf;

import java.util.*;
import jsjf.exceptions.*;

public class LinkedBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T> {

protected BinaryTreeNode<T> root;
protected int modCount = 0;

   public LinkedBinaryTree() {
       root = null;
   } // LinkedBinaryTree

   public LinkedBinaryTree(T element) {
       root = new BinaryTreeNode<T>(element);
   } // LinkedBinaryTree

public LinkedBinaryTree(T element, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right) {

       root = new BinaryTreeNode<T>(element);
       root.setLeft(left.root);
       root.setRight(right.root);
   } // LinkedBinaryTree

public T getRootElement() throws EmptyCollectionException {

       if (root == null) {
           throw new EmptyCollectionException(\"There is no element at root! There must be a root element to\"
                   + \"create a tree.\");
       } else {
           return root.getElement();
       }

} // getRootElement

   protected BinaryTreeNode<T> getRootNode() throws EmptyCollectionException {
       if(root == null){
           throw new EmptyCollectionException(\"There is no node at root! There must be a root node to\"
                   + \"create a tree.\");
       } else{
           return root;
       }
   } // getRootNode

public LinkedBinaryTree<T> getLeft() {

BinaryTreeNode<T> leftChild;
LinkedBinaryTree<T> leftSubtree;

if (root == null)
return null;

       leftChild = root.getLeft();
       if (leftChild == null)
           return null;

       leftSubtree = new LinkedBinaryTree<T>();
       leftSubtree.root = leftChild;
       return leftSubtree;
   } // getLeft

public LinkedBinaryTree<T> getRight() {

BinaryTreeNode<T> rightChild;
LinkedBinaryTree<T> rightSubtree;

if (root == null)
return null;

       rightChild = root.getRight();
       if (rightChild == null)
           return null;

       rightSubtree = new LinkedBinaryTree<T>();
       rightSubtree.root = rightChild;
       return rightSubtree;
   } // getRight

   public boolean isEmpty() {
       return (root == null);
   } // isEmpty
   public int size() {

return 0;

} // size

public int getHeight() {

       if (this.isEmpty()) {
           System.out.println(\"\ \"+\"Check file for formatting errors.....\");
           System.out.println(\"\ \"+\"The program has terminated......\");
           System.exit(0);
           return 0;
       } else {
           BinaryTreeNode<T> node = root;
           return height(node);
       }
   } // getHeight

private int height(BinaryTreeNode<T> node) {

       if (node == null){
           return -1;
       }

       int leftSub = height(node.left);
       int rightSub = height(node.right);

       if (leftSub > rightSub){
           return leftSub + 1;
       }
       else{
           return rightSub + 1;
       }

} // height

public boolean contains(T targetElement) {

return false;

} // contains

public T find(T targetElement) throws ElementNotFoundException {

BinaryTreeNode<T> current = findNode(targetElement, root);

if (current == null)
throw new ElementNotFoundException(\"LinkedBinaryTree\");

       return (current.getElement());
   } // find
   private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next) {

if (next == null)
return null;

if (next.getElement().equals(targetElement))
return next;

BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());

if (temp == null)
temp = findNode(targetElement, next.getRight());

return temp;
} // findNode

   public String toString() {
       return toString(root, 0);
   } // toString

// Recursive helper method for the toString method.

private String toString(BinaryTreeNode<T> node, int indent) {

String result = \"\";
BinaryTreeNode<T> leftChild, rightChild;

if (node == null)
return \"\";

       rightChild = node.getRight();
       if (rightChild != null)
           result += toString(rightChild, indent + 1);

       for (int k = 1; k <= indent; k++)
           result += \"   \";
       result += node.getElement() + \"\ \";

       leftChild = node.getLeft();
       if (leftChild != null)
           result += toString(leftChild, indent + 1);
       return result;

} // toString

   public Iterator<T> iterator() {
       return iteratorInOrder();
   } // iterator

public Iterator<T> iteratorInOrder() {

ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();

inOrder(root, tempList);

return new TreeIterator(tempList.iterator());
} // iteratorInOrder

protected void inOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {

       if (node != null) {
           inOrder(node.getLeft(), tempList);
           tempList.addToRear(node.getElement());
           inOrder(node.getRight(), tempList);
       }
   } // inOrder
   public Iterator<T> iteratorPreOrder() {

return null;

} // iteratorPreOrder

protected void preOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {

// To be completed as a Programming Project

} // preOrder

public Iterator<T> iteratorPostOrder() {

ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();

postOrder(root, tempList);

return new TreeIterator(tempList.iterator());

} // iteratorPostOrder

protected void postOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {

       if (node != null) {
           postOrder(node.getLeft(), tempList);
           postOrder(node.getRight(), tempList);
           tempList.addToRear(node.getElement());
       }

} // postOrder

public Iterator<T> iteratorLevelOrder() {

       ArrayUnorderedList<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<BinaryTreeNode<T>>();
       ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
       BinaryTreeNode<T> current;

nodes.addToRear(root);

while (!nodes.isEmpty()) {
current = nodes.removeFirst();

           if (current != null) {
               tempList.addToRear(current.getElement());
               if (current.getLeft() != null)
                   nodes.addToRear(current.getLeft());
               if (current.getRight() != null)
                   nodes.addToRear(current.getRight());
           } else
               tempList.addToRear(null);
       }

return new TreeIterator(tempList.iterator());
} // iteratorLevelOrder

private class TreeIterator implements Iterator<T> {

private int expectedModCount;
private Iterator<T> iter;

       public TreeIterator(Iterator<T> iter) {
           this.iter = iter;
           expectedModCount = modCount;
       } // TreeIterator

public boolean hasNext() throws ConcurrentModificationException {

if (!(modCount == expectedModCount))
throw new ConcurrentModificationException();

return (iter.hasNext());
} // hasNext

       public T next() throws NoSuchElementException {
           if (hasNext())
               return (iter.next());
           else
               throw new NoSuchElementException();
       } // next

       public void remove() {
           throw new UnsupportedOperationException();
       } // remove

} // class TreeIterator

} // class LinkedBinaryTree<T>

// ***************************************************************

BinaryTreeADT.java

package jsjf;

import java.util.Iterator;

public interface BinaryTreeADT<T>
{
public T getRootElement();

public boolean isEmpty();

public int size();

public boolean contains(T targetElement);

public T find(T targetElement);

public String toString();

    public Iterator<T> iterator();

    public Iterator<T> iteratorInOrder();

    public Iterator<T> iteratorPreOrder();

public Iterator<T> iteratorPostOrder();

public Iterator<T> iteratorLevelOrder();
}

BinaryTreeNode.java

package jsjf;

public class BinaryTreeNode<T>
{
protected T element;
protected BinaryTreeNode<T> left, right;

    public BinaryTreeNode(T obj)
    {
        element = obj;
        left = null;
        right = null;
    }

    public BinaryTreeNode(T obj, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right)
    {
        element = obj;
        if (left == null)
            this.left = null;
        else
            this.left = left.getRootNode();

         if (right == null)
            this.right = null;
        else
            this.right = right.getRootNode();
    }

    public int numChildren()
    {
        int children = 0;

if (left != null)
children = 1 + left.numChildren();

if (right != null)
children = children + 1 + right.numChildren();

        return children;
    }

    public T getElement()
    {
        return element;
    }

    public BinaryTreeNode<T> getRight()
    {
        return right;
    }

    public void setRight(BinaryTreeNode<T> node)
    {
        right = node;
    }

    public BinaryTreeNode<T> getLeft()
    {
        return left;
    }

    public void setLeft(BinaryTreeNode<T> node)
    {
        left = node;
    }
}

EmptyCollectionException.java

package jsjf.exceptions;

public class EmptyCollectionException extends RuntimeException
{
   private static final long serialVersionUID = 1L;
    public EmptyCollectionException (String collection)
    {
        super (\"The \" + collection + \" is empty.\");
    }
}

ElementNotFoundException.java

package jsjf.exceptions;

public class ElementNotFoundException extends RuntimeException
{
private static final long serialVersionUID = 1L;

    public ElementNotFoundException (String collection)
    {
        super (\"The target element is not in this \" + collection);
    }
}

ArrayUnorderedList.java

package jsjf;

import jsjf.exceptions.*;

public class ArrayUnorderedList<T> extends ArrayList<T>
         implements UnorderedListADT<T>
{
    public ArrayUnorderedList()
    {
        super();
    }

    public ArrayUnorderedList(int initialCapacity)
    {
        super(initialCapacity);
    }

    public void addToFront(T element)
    {
        if (size() == list.length)
            expandCapacity();

        // shift elements up one
        for (int scan=rear; scan > 0; scan--)
            list[scan] = list[scan-1];

        list[0] = element;
        rear++;
       modCount++;
    }

    public void addToRear(T element)
    {
        if (size() == list.length)
            expandCapacity();

        list[rear] = element;
        rear++;
       modCount++;
    }

    public void addAfter(T element, T target)
    {
        if (size() == list.length)
            expandCapacity();

        int scan = 0;

       // find the insertion point
        while (scan < rear && !target.equals(list[scan]))
            scan++;

        if (scan == rear)
            throw new ElementNotFoundException(\"UnorderedList\");

        scan++;

       // shift elements up one
        for (int shift=rear; shift > scan; shift--)
            list[shift] = list[shift-1];

       // insert element
       list[scan] = element;
        rear++;
       modCount++;
    }
}

UnorderedListADT.java

package jsjf;

public interface UnorderedListADT<T> extends ListADT<T>
{
public void addToFront(T element);

public void addToRear(T element);

public void addAfter(T element, T target);
}

ListADT.java

package jsjf;

import java.util.Iterator;

public interface ListADT<T> extends Iterable<T>
{
public T removeFirst();

public T removeLast();

public T remove(T element);

public T first();

public T last();

public boolean contains(T target);

public boolean isEmpty();

public int size();

public Iterator<T> iterator();

public String toString();
}

ArrayList.java

package jsjf;

import jsjf.exceptions.*;
import java.util.*;

public abstract class ArrayList<T> implements ListADT<T>, Iterable<T>
{
    private final static int DEFAULT_CAPACITY = 100;
    private final static int NOT_FOUND = -1;

    protected int rear;
    protected T[] list;
   protected int modCount;

    public ArrayList()
    {
        this(DEFAULT_CAPACITY);
    }

   // Added.
    @SuppressWarnings(\"unchecked\")

    public ArrayList(int initialCapacity)
    {
        rear = 0;
        list = (T[])(new Object[initialCapacity]);
       modCount = 0;
    }

    protected void expandCapacity()
    {
       list = Arrays.copyOf(list, list.length*2);
    }

    public T removeLast() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException(\"ArrayList\");

        T result;
        rear--;
        result = list[rear];
        list[rear] = null;
       modCount++;

return result;
}

    public T removeFirst() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException(\"ArrayList\");

        T result = list[0];
        rear--;
        /** shift the elements */
        for (int scan=0; scan < rear; scan++)
            list[scan] = list[scan+1];

        list[rear] = null;
       modCount++;

        return result;
    }

    public T remove(T element)
    {
        T result;
        int index = find(element);

if (index == NOT_FOUND)
throw new ElementNotFoundException(\"ArrayList\");

        result = list[index];
        rear--;

        // shift the appropriate elements
        for (int scan=index; scan < rear; scan++)
            list[scan] = list[scan+1];

        list[rear] = null;
       modCount++;

        return result;
    }

    public T first() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException(\"ArrayList\");

return list[0];
}

    public T last() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException(\"ArrayList\");

return list[rear-1];
}

    public boolean contains(T target)
    {
        return (find(target) != NOT_FOUND);
    }

    private int find(T target)
    {
        int scan = 0;
       int result = NOT_FOUND;

        if (!isEmpty())
            while (result == NOT_FOUND && scan < rear)
                if (target.equals(list[scan]))
                    result = scan;
                else
                    scan++;

return result;
}

    public boolean isEmpty()
    {
        return (rear == 0);
    }

    public int size()
    {
        return rear;
    }

    public String toString()
    {
        String result = \"\";

for (int scan=0; scan < rear; scan++)
result = result + list[scan] + \"\ \";

        return result;
    }

    public Iterator<T> iterator()
    {
        return new ArrayListIterator();
    }

   private class ArrayListIterator implements Iterator<T>
   {
       int iteratorModCount;
       int current;

       public ArrayListIterator()
       {
           iteratorModCount = modCount;
           current = 0;
       }

       public boolean hasNext() throws ConcurrentModificationException
       {
           if (iteratorModCount != modCount)
               throw new ConcurrentModificationException();

           return (current < rear);
       }

       public T next() throws ConcurrentModificationException
       {
           if (!hasNext())
               throw new NoSuchElementException();

           current++;

           return list[current - 1];
       }

       public void remove() throws UnsupportedOperationException
       {
           throw new UnsupportedOperationException();
       }

   }
}

# include <iostream>

# include <cstdlib>

using namespace std;

struct node

{

int info;

struct node *left;

struct node *right;

}*root;

class BST

{

public:

void find(int, node **, node **);

void insert(int);

void del(int);

void case_a(node *,node *);

void case_b(node *,node *);

void case_c(node *,node *);

void preorder(node *);

void inorder(node *);

void postorder(node *);

void display(node *, int);

BST()

{

root = NULL;

}

};

int main()

{

int choice, num;

BST bst;

node *temp;

while (1)

{

cout<<\"-----------------\"<<endl;

cout<<\"Operations on BST\"<<endl;

cout<<\"-----------------\"<<endl;

cout<<\"1.Insert Element \"<<endl;

cout<<\"2.Delete Element \"<<endl;

cout<<\"3.Inorder Traversal\"<<endl;

cout<<\"4.Preorder Traversal\"<<endl;

cout<<\"5.Postorder Traversal\"<<endl;

cout<<\"6.Display\"<<endl;

cout<<\"7.Quit\"<<endl;

cout<<\"Enter your choice : \";

cin>>choice;

switch(choice)

{

case 1:

temp = new node;

cout<<\"Enter the number to be inserted : \";

cin>>temp->info;

bst.insert(root, temp);

case 2:

if (root == NULL)

{

cout<<\"Tree is empty, nothing to delete\"<<endl;

continue;

}

cout<<\"Enter the number to be deleted : \";

cin>>num;

bst.del(num);

break;

case 3:

cout<<\"Inorder Traversal of BST:\"<<endl;

bst.inorder(root);

cout<<endl;

break;

case 4:

cout<<\"Preorder Traversal of BST:\"<<endl;

bst.preorder(root);

cout<<endl;

break;

case 5:

cout<<\"Postorder Traversal of BST:\"<<endl;

bst.postorder(root);

cout<<endl;

break;

case 6:

cout<<\"Display BST:\"<<endl;

bst.display(root,1);

cout<<endl;

break;

case 7:

exit(1);

default:

cout<<\"Wrong choice\"<<endl;

}

void BST::find(int item, node **par, node **loc)

{

node *ptr, *ptrsave;

if (root == NULL)

{

*loc = NULL;

*par = NULL;

return;

}

if (item == root->info)

{

*loc = root;

*par = NULL;

return;

}

if (item < root->info)

ptr = root->left;

else

ptr = root->right;

ptrsave = root;

while (ptr != NULL)

{

if (item == ptr->info)

{

*loc = ptr;

*par = ptrsave;

return;

}

ptrsave = ptr;

if (item < ptr->info)

ptr = ptr->left;

else

ptr = ptr->right;

}

*loc = NULL;

*par = ptrsave;

}

void BST::insert(node *tree, node *newnode)

{

if (root == NULL)

{

root = new node;

root->info = newnode->info;

root->left = NULL;

root->right = NULL;

cout<<\"Root Node is Added\"<<endl;

return;

}

if (tree->info == newnode->info)

{

cout<<\"Element already in the tree\"<<endl;

return;

}

if (tree->info > newnode->info)

{

if (tree->left != NULL)

{

insert(tree->left, newnode);

}

else

{

tree->left = newnode;

(tree->left)->left = NULL;

(tree->left)->right = NULL;

cout<<\"Node Added To Left\"<<endl;

return;

}

else

{

if (tree->right != NULL)

{

insert(tree->right, newnode);

}

else

{

tree->right = newnode;

(tree->right)->left = NULL;

(tree->right)->right = NULL;

cout<<\"Node Added To Right\"<<endl;

return;

}

void BST::del(int item)

{

node *parent, *location;

if (root == NULL)

{

cout<<\"Tree empty\"<<endl;

return;

}

find(item, &parent, &location);

if (location == NULL)

{

cout<<\"Item not present in tree\"<<endl;

return;

}

if (location->left == NULL && location->right == NULL)

case_a(parent, location);

if (location->left != NULL && location->right == NULL)

case_b(parent, location);

if (location->left == NULL && location->right != NULL)

case_b(parent, location);

if (location->left != NULL && location->right != NULL)

case_c(parent, location);

free(location);

}

void BST::case_a(node *par, node *loc )

{

if (par == NULL)

{

root = NULL;

}

else

{

if (loc == par->left)

par->left = NULL;

else

par->right = NULL;

}

void BST::case_b(node *par, node *loc)

{

node *child;

if (loc->left != NULL)

child = loc->left;

else

child = loc->right;

if (par == NULL)

{

root = child;

}

else

{

if (loc == par->left)

par->left = child;

else

par->right = child;

}

void BST::case_c(node *par, node *loc)

{

node *ptr, *ptrsave, *suc, *parsuc;

ptrsave = loc;

ptr = loc->right;

while (ptr->left != NULL)

{

ptrsave = ptr;

ptr = ptr->left;

}

suc = ptr;

parsuc = ptrsave;

if (suc->left == NULL && suc->right == NULL)

case_a(parsuc, suc);

else

case_b(parsuc, suc);

if (par == NULL)

{

root = suc;

}

else

{

if (loc == par->left)

par->left = suc;

else

par->right = suc;

}

suc->left = loc->left;

suc->right = loc->right;

}

void BST::preorder(node *ptr)

{

if (root == NULL)

{

cout<<\"Tree is empty\"<<endl;

return;

}

if (ptr != NULL)

{

cout<<ptr->info<<\" \";

preorder(ptr->left);

preorder(ptr->right);

}

void BST::inorder(node *ptr)

{

if (root == NULL)

{

cout<<\"Tree is empty\"<<endl;

return;

}

if (ptr != NULL)

{

inorder(ptr->left);

cout<<ptr->info<<\" \";

inorder(ptr->right);

}

void BST::postorder(node *ptr)

{

if (root == NULL)

{

cout<<\"Tree is empty\"<<endl;

return;

}

if (ptr != NULL)

{

postorder(ptr->left);

postorder(ptr->right);

cout<<ptr->info<<\" \";

}

void BST::display(node *ptr, int level)

{

int i;

if (ptr != NULL)

{

display(ptr->right, level+1);

cout<<endl;

if (ptr == root)

cout<<\"Root->: \";

else

{

for (i = 0;i < level;i++)

cout<<\" \";

}

cout<<ptr->info;

display(ptr->left, level+1);

}

Create an implementation of a binary tree using the recursiv

Solution

Get Help Now

Submit a Take Down Notice