Implementation Requirements in Java For this project you must write a program th

Question

Implementation Requirements in Java

For this project you must write a program that reads the preorder and inorder traversals of a
binary tree, constructs an internal linked representation of the tree, and then outputs the
corresponding postorder traversal. You must implement your own binary tree node and tree
classes. You do not need to implement all methods of the tree ADT -- it is sufficient to
implement only the methods that are required to provide the desired output. At least one of
your methods must use recursion.

Program Input

The program should read from the standard input two lines. The first line contains a string
representing the preorder traversal of a binary tree, and the second contains a string
representing the inorder traversal of the same tree. Nodes of the tree are identified by
unique capital letters.

Output

Your program must print a string representing the postorder traversal of the tree followed by
a newline character.

Sample Input #1

DBACEGF
ABCDEFG

Sample Output #1

ACBFGED

Sample Input #2
BCAD
CBAD

Sample Output #2

CDAB

IN Javascript.

Explanation / Answer

// Tree.java
// TreeNode and Tree class declarations for a binary search tree.
// class Tree definition
public class Tree<T extends Comparable<T>>
{
   private TreeNode<T> root;

   // constructor initializes an empty Tree of integers
   public Tree()
   {
      root = null;
   }

   // insert a new node in the binary search tree
   public void insertNode(T insertValue)
   {
      if (root == null)
         root = new TreeNode<T>(insertValue); // create root node
      else
         root.insert(insertValue); // call the insert method
   }

   // begin preorder traversal
   public void preorderTraversal()
   {
      preorderHelper(root);
   }

   // recursive method to perform preorder traversal
   private void preorderHelper(TreeNode<T> node)
   {
      if (node == null)
         return;

      System.out.printf("%c",node.data); // output node data
      preorderHelper(node.leftNode); // traverse left subtree
      preorderHelper(node.rightNode); // traverse right subtree
   }

   // begin inorder traversal
   public void inorderTraversal()
   {
      inorderHelper(root);
   }

   // recursive method to perform inorder traversal
   private void inorderHelper(TreeNode<T> node)
   {
      if (node == null)
         return;

      inorderHelper(node.leftNode); // traverse left subtree
      System.out.printf("%s ", node.data); // output node data
      inorderHelper(node.rightNode); // traverse right subtree
   }

   // begin postorder traversal
   public void postorderTraversal()
   {
      postorderHelper(root);
   }

   // recursive method to perform postorder traversal
   private void postorderHelper(TreeNode<T> node)
   {
      if (node == null)
         return;

      postorderHelper(node.leftNode); // traverse left subtree
      postorderHelper(node.rightNode); // traverse right subtree
      System.out.printf("%s ", node.data); // output node data
   }




} // end class Tree

------------------------------------------------------------

// class TreeNode definition
public class TreeNode<T extends Comparable<T>>
{
   // package access members
   TreeNode<T> leftNode;
   T data; // node value
   TreeNode<T> rightNode;

   // constructor initializes data and makes this a leaf node
   public TreeNode(T nodeData)
   {
      data = nodeData;            
      leftNode = rightNode = null; // node has no children
   }

   // locate insertion point and insert new node; ignore duplicate values
   public void insert(T insertValue)
   {
      // insert in left subtree
      if (insertValue.compareTo(data) < 0)
      {
         // insert new TreeNode
         if (leftNode == null)
            leftNode = new TreeNode<T>(insertValue);
         else // continue traversing left subtree recursively
            leftNode.insert(insertValue);
      }
      // insert in right subtree
      else if (insertValue.compareTo(data) > 0)
      {
         // insert new TreeNode
         if (rightNode == null)
            rightNode = new TreeNode<T>(insertValue);
         else // continue traversing right subtree recursively
            rightNode.insert(insertValue);
      }
   }
} // end class TreeNode

----------------------------------------------------------------

//Sample test program that reads pre order
//,inorder of a tree and print post order traversal
import java.util.Scanner;
public class TreeTest
{
   public static void main(String[] args)
   {
       //Create an instance of Scanner class
       Scanner scanner=new Scanner(System.in);
       //Create an instance of Tree of character data type
       Tree<Character> tree = new Tree<Character>();

       //Create three string variables to read preorder, inorder and postoder
       String preOrder;
       String inOrder;
       String postOrder;

       System.out.println("Sample input #1 ");
       //read pre order
       preOrder=scanner.nextLine();
       //read in order
       inOrder=scanner.nextLine();
      
       //insert elements into the Tree object, tree      
       for (int index = 0; index < preOrder.length(); index++)
       {
           tree.insertNode(preOrder.charAt(index));
       }
          
       System.out.println("Sample output #1 ");
       System.out.println("Post-Order Traversal : ");
       //call the method postoderTraversal method on tree object
       tree.postorderTraversal();

   }
} // end class TreeTest

----------------------------------------------------
Sample output:

Sample input #1
DBACEGF
ABCDEFG
Sample output #1
Post-Order Traversal :
A C B F G E D

sample run2:

Sample input #1
BCAD
CBAD
Sample output #1
Post-Order Traversal :
A D C B

//Note : sample second input BCAD post order traversal is in correct .

Hope this helps you

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects