Lab:

Tree Traversals

Prelab Tasks:

1.      Review what we learned about binary tree traversal and understand different orders of nodes:  in-order, pre-order, post-order, level-order.

2.      Read and understand d_tnode.h

3.      Read d_tnodel.h and understand functions:  inorderOutput, postorderOutput, levelorderOutput

Lab Tasks:  In this lab, we’ll apply the prefix order of the binary tree to output arithmetic expression. An arithmetic expression involving the binary operators such as +, -, *, and / can be represented by using a binary expression tree.  In a binary expression tree, each operator has two children, which are either operands or subexpressions. Leaf nodes contain an operand; nonleaf nodes contain a binary operator. The left and right subtrees of an operator describe a subexpression that is evaluated and used one of the operands for the operator. More details can be found online: https://en.wikipedia.org/wiki/Binary_expression_tree

  1. For the following infix expression, build the corresponding expression tree in paper (not in program yet).

    1.1  a*b

    1.2  a+b*c

    1.3  a+b*c/d-e

  2. Perform pre-order and post-order traversal of the above binary expression trees. What relationship exists among these scans and prefix and postfix notation for the expression?
  3. Read inf2pstf.h and understand the implementation of class infix2Postfix, which converts an infix expression to postfix.
  4. Read and understand the implementation of  function buildExpTree
  5. Design and implement void prefixoutput(tnode<char> *exp), which scans of an expression tree and outputs the prefix form of the expression represented by the tree.

  6. Write a program that inputs an infix expression and creates an expression tree; output the prefix form of the expression; output posfix form of the expression by traversing the tree using postorderOutput(); and dispaly the tree by using displayTree(). [Note: You will need to update/add the functions you wrote in tasks 3-5  in d_tnodel.h.

    6.1 Copy the following 5 files: d_except.h, d_expsym.h,  d_tnodel.h  d_tnode.h,  inf2pstf.h, to your working directory for this lab

    6.2 Name the program  as lab_04.cpp and copy the implementations of  functions buildExpTree in task 4 and prefixOutput in task 5 into program lab_04.cpp.

    6.3 Run your program and compare your output for lab_04.cpp with the sample output.

 

What to Turn In