/**-------------------------------------------------------------------
  FactorTree sample algorithm - generates a prime-factor tree
  
  (1) Run the program.  Try out a small, medium, and large number.
  
  (2) Try the same number 3 times.  Does it always produce the same factorization?
  
  (3) Explain how the INDENTATION works.
  
  (4) Change the TRAVERSAL to an IN-ORDER traversal. What does this accomplish?
      
  (5) Change the TRAVERSAL to a POST-ORDER traversal. What happens now?

  (6) We define the function SP(int n) as follows:
      
      SP(0) = 0
      SP(1) = 0
      
      For n>1,
        SP(n) = the SUM of all the PRIME factors of n, including repetition

      For n<0,
        SP(n) = - SP(-n)

      For example,
         SP(10) = 7   , because 10 = 2*5
         SP(61) = 61  , because 61 is prime, so it has no prime factors
         SP(180) = 15 , because 180 = 2*3*2*3*5
         SP(-10) = -7 , because SP(10) = 7
      
      Write a method to calculate the value of SP(n).
      It should start by creating a factor tree.
      Then it must search for the LEAVES in the tree (they have NULL children),
        and ADD THEM ALL UP.  You will need to search RECURSIVELY.
        
      This is a relatively tricky programming problem.  
      Here are a couple possibilities:

      (A) The Array Algorithm
          Do a traversal (any kind will work).  Each time a LEAF is encountered,
          you must APPEND it to the array (store it in the next empty position).
          When finished, add up the numbers in the array.
          
      (B) Better Algorithm
          Works the same as A, but don't bother with the array.
          Simply ADD each LEAF number onto the running total when you find it.

      Be careful to program SPECIAL CASES for 0, 1, and negative numbers.
      And DON'T add 1 into any of the totals, e.g.  61 = 61*1, but S(61) = 61
      
  (7) Tree Validation

      It is conceivable that a programming error, or a hardware fault,
      might produce an incorrect factor tree.  The validation method
      should check that the tree is correct, by checking that each NODE
      is actually equal to the product of the children.  It must do this
      throughout the entire tree.  It must avoid CRASHING when it reaches
      the LEAF nodes.
      
  (8) Prime Validation
     
      A more sophisticated version of #7 is to also check that the LEAF nodes
      really are prime numbers.  This requires a PRIME function, that accepts
      an int parameter and then returns TRUE if the int is prime, FALSE otherwise.
      Then at each LEAF node, the Tree Validation should call the PRIME function.
          
 -------------------------------------------------------------------**/

public class FactorTree
{ public static void main(String[] args)
  { new FactorTree();}

  class Node                             // Use an "inner class"
  { int data;                            // to create a RECORD structure
    Node leftChild;
    Node rightChild;
  }

  public FactorTree()
  { int number;
    Node root = null;
    number = inputInt("Type an integer:");
    if (number > 2)
     { root = makeTree(number);
       output("The prime factors are");
       showFactors(root);
     }
    output("-----------------");
    outline(root,"");
  }

  public Node makeTree(int number)
                                   // Recursive method to create factor tree
  { Node temp = new Node();        // creates a Node (allocates memory)
    temp.leftChild = null;
    temp.rightChild = null;
    temp.data = number;
    int count = 1;
    int fac = 0;
    while (count*count <= number)
    { if ( (number % count) == 0 )
       { fac = count; }
      count = count + 1;
    }
    if (fac > 1)
    { temp.leftChild = makeTree(fac);
      temp.rightChild = makeTree(number / fac);
    }
    return temp;
  }

  public void showFactors(Node here)
  { if (here == null) { output("null"); return;}
    if ( (here.leftChild == null) && (here.rightChild == null))
    { output(here.data);
    }
    else
    { showFactors(here.leftChild);
      showFactors(here.rightChild);
    }
  }

  public void outline(Node here,String indent)
  // Pre-order traversal prints tree in "outline" format
  { output(indent + here.data);
    if (here.leftChild != null)
     {outline(here.leftChild, indent + "   ");}
    if (here.rightChild != null)
     {outline(here.rightChild, indent + "   ");}
  }

//---- Write your program above -------
//---- Below are simple input and output methods ----

  static void output(String info)
  {  System.out.println(info);
  }

  static void output(double info)
  {  System.out.println(info);
  }

  static void output(long info)
  {  System.out.println(info);
  }

  static int inputInt(String Prompt)
  {  int result=0;
     try{result=Integer.valueOf(input(Prompt).trim()).intValue();}
     catch (Exception e){result = 0;}
     return result;
  }

  static double inputDouble(String Prompt)
  {  double result=0;
     try{result=Double.valueOf(input(Prompt).trim()).doubleValue();}
     catch (Exception e){result = 0;}
     return result;
  }

  static String input(String prompt)
  {  String inputLine = "";
     System.out.print(prompt);
     try
      {inputLine = (new java.io.BufferedReader(
                    new java.io.InputStreamReader(System.in))).readLine();}
     catch (Exception e)
      { String err = e.toString();
        System.out.println(err);
      }
     return inputLine;
  }

}