Question

Design algorithms for the following operations for a binary tree T:

. preorderNext(p) : Return the position visited after p in a preorder traversal of T, or NULL if p is the last node visited.
. inorderNext(p) : Return the position visited after p in an inorder traversal of T, or NULL if p is the last node visited.
. postorderNext(p) : Return the position visited after p in a postorder traversal of T, or NULL if p is the last node visited.

Answer 1

ANSWER :

CODE IN JAVA:
NOTE: Add the below methods to either LinkedBinaryTree or AbstractBinaryTree class.

//The following preorderNext method accepts a position p and then returns a
//position visited after the position p in a preorder traversal of a binary
//tree T.
//In the preorder traversal, get the current position, traverse the left
//subtree, and traverse the right subtree.
public Position<E> preorderNext(Position<E> p)
{
   if(left(p) != null)
        return left(p);

   if(right(p) != null)
        return right(p);

   Position<E> k = parent(p);
   while(k != null && (right(k) == null || right(k) == p))
   {
        p = k;
        k = parent(k);
   }

   if(k == null)
        return null;

   return right(k);
} // end of preorderNext method

TEST PROGRAM:

File: LinkedBinaryTreeDemo.java

// LinkedBinaryTreeDemo class implementation
public class LinkedBinaryTreeDemo
{
   // start main method
   public static void main(String[] args)
   {
       // create an object for LinkedBinaryTree class
       LinkedBinaryTree<Integer> T = new LinkedBinaryTree<Integer>();
    
       // add several elements to the binary tree T
       Position<Integer> p1 = T.addRoot(45);
       Position<Integer> p2 = T.addLeft(p1, 35);
       Position<Integer> p3 = T.addLeft(p2, 25);    
       Position<Integer> p4 = T.addRight(p1, 55);
       Position<Integer> p5 = T.addRight(p2, 40);    
       Position<Integer> p6 = T.addLeft(p4, 50);
       Position<Integer> p7 = T.addLeft(p5, 38);
       Position<Integer> p8 = T.addRight(p7, 39);
       Position<Integer> p9 = T.addRight(p5, 42);
       Position<Integer> p10 = T.addRight(p9, 44);
       Position<Integer> p11 = T.addRight(p4, 60);
       Position<Integer> p12 = T.addRight(p11, 63);
            
       // display the preorder traversal of T
       System.out.print("Preorder traversal of T: ");
       Iterable<Position<Integer>> itr2 = T.preorder();    
       for(Position<Integer> p : itr2)
           System.out.print(p.getElement() + " ");
       System.out.println();

// display the position visited after each element in a preorder traversal of T
       for(Position<Integer> p : itr2)
       {
           Position<Integer> result = T.preorderNext(p);
           if(result == null)
               System.out.println("preorderNext(" + p.getElement() + "): null");
           else
               System.out.println("preorderNext(" + p.getElement() + "): " + result.getElement());
       }
       System.out.println();
    
       // display the inorder traversal of T
       System.out.print("Inorder traversal of T: ");
       Iterable<Position<Integer>> itr1 = T.inorder();    
       for(Position<Integer> p : itr1)
           System.out.print(p.getElement() + " ");
       System.out.println();

OUTPUT:

( PLEASE VOTE FOR THIS ANSWER )

I THINK IT WILL BE USEFULL TO YOU ........

PLZZZZZ COMMENT IF YOU HAVE ANY PROBLEM I WILL TRY TO SOLVE IT ..........

THANK YOU ..........