Question

This is in Java

Create a client class that does the following:

• Manually creates an instance of a binary expression tree that represents the following expression:
• (((5+2)*(2-1)/((2+9))+((7-2)-1))*8)
• Do this by using methods such as addRoot, addLeft, addRight, set, and attach.
• The element should be of type String
• Note that you are manually building this specific expression tree, the pseudo code might look something like:
  • Create a LinkedBinaryTree
  • Add “*” as the root to the tree
  • Add “/” as the left child to the tree
  • Add “8” the right child to the tree
  • Add a left child to the root’s left child
  • Add a right child to the root’s left child
  • etc.

You may want to consider if it would be easier to build the tree in a top down fashion or in a bottom up fashion.

Once you have created the expression tree have your client print out the following:

• The string that represents the expression:

      ( ( ( 5 + 2 ) * ( 2 – 1 ) / ( 2 + 9 ) + ( ( 7 – 2 ) – 1 ) ) * 8 )

• The preOrder traversal of the tree
• The inOrder traversal of the tree
• The postOrder traversal of the tree
• The breathFirst traversal of the tree

The parenthesized representation of the tree using Euler’s Tour

Answer 1

Here is the program. Please comment below for any queries i will help

public class PrintRoot extends EulerTour<Character, Character> {

    @Override

    public Character execute(BinaryTree<Character> T) {

        init(T);

        return eulerTour(T.root());

    }

    @Override

    protected void Left_Visited(Position<Character> vt, TourResult<Character> rt) {

        Character t_1 = new Character('T');

        Character t_2 = new Character('F');

            System.out.print("(");

    }

  protected void Below_visited(Position<Character> vt, TourResult<Character> rt)

  {

    Character t_3 = new Character('+');

      Character t_4 = new Character('vt');

      if(!vt.element().equals(t_4)&&!vt.element().equals(t_3))

          rt.out=vt.element();

            System.out.print(vt.element());

  }

  protected void rt_visited(Position<Character> vt, TourResult<Character> rt)

  {

      Character t_1 = new Character('T');

      Character t_2 = new Character('F');

      Character t_3 = new Character('+');

      Character t_4 = new Character('vt');

      if(vt.element().equals(t_4))

      {

       if(rt.out==null&&rt.left!=null&&rt.rt!=null){

        if(rt.left.equals(t_1) && rt.rt.equals(t_1))

            rt.out = t_1;

        else if(rt.left.equals(t_1) && rt.rt.equals(t_2))

            rt.out = t_1;

        else if(rt.left.equals(t_2) && rt.rt.equals(t_2))

             rt.out = t_2;

      }

      }

      if(vt.element().equals(t_3))

      {

          if(rt.out==null&&rt.left!=null&&rt.rt!=null){

        if(rt.left.equals(t_1) && rt.rt.equals(t_1))

            rt.out = t_1;

        else if(rt.left.equals(t_1) && rt.rt.equals(t_2))

           rt.out = t_2;

        else if(rt.left.equals(t_2) && rt.rt.equals(t_2))

             rt.out = t_2;

        }

      }

    else if(rt.rt==null || rt.left == null)

     rt.out = vt.element();

     System.out.print(")");

  }

}