Results 1 to 5 of 5
  1. #1
    hansmoolman is offline Member
    Join Date
    Oct 2010
    Posts
    5
    Rep Power
    0

    Default Iterative Preorder

    Can anyone help.
    I have written some recursive pre/postOrder methods for my BinartTree and they seem to be working fine. However, my iterative version of the preOrder doesnt seem to be working as I had expected. It simply prints all the values in the order they are added.

    Can anyone spot where I am going wrong, or point me in the right direction.

    My code is as follows:
    Java Code:
    import javax.swing.*;
    import java.util.*;
    
    public class BinaryTree {
    
        public static void main(String[] args) {
            
            BinaryTree tree = new BinaryTree();
    
    
            /**Then populate the Tree with some integer values         
              */
            int numberOfNumbers = Integer.parseInt(JOptionPane.showInputDialog(
                    "Enter the total number of values you wish to add to the tree"));
    
            for (int i = 0; i < numberOfNumbers; i++)
            {
                int myNumbers = Integer.parseInt(JOptionPane.showInputDialog(
                        "Enter number " + (i + 1) + " to the tree"));
    
                tree.insert(myNumbers);
            }
    
            
            /**Allows the user to select a printing method for the BinaryTree
             */
            int choice = Integer.parseInt(JOptionPane.showInputDialog("Plese choose a display method: " +
                                                                      "\n1: Recursive preOrder" +
                                                                      "\n2: Recursive postOrder" +
                                                                      "\n3: Iterativeive preOrder")) ;
    
            System.out.println("The values are: ");
            /**User written methods to print the values of the tree
             * print(), printPreOrder(), printPostOrder() and printPreOrderIterative() traversals to print values
             * Depending on the users, choice, prints:
             *
             * tree.print();
             * tree.printPostorder();
             * tree.printPreorder();
             */
            if (choice == 1)
            {
                tree.printPreorder();
            }
            if (choice == 2)
            {
                tree.printPostorder();
            }
            if (choice == 3)
            {
                /**My printPreorderIterative() that prints all the user supplied values
                 */
                tree.printPreorderIterative();
            }
        }
    
    
        // Root node pointer, will be null for an empty tree
        private Node root;
        
       private static class Node 
       {
           Node left;
           Node right;
           int data;
           
           /**Private inner class Constructor
            * Sets left and right node to null
            * and sets the Node data to be the newDate that is read in
            * @param newData
            */
           Node (int newData) 
           {
               left = null;
               right = null;
               data = newData;
           }
       }
       
       
       public BinaryTree() 
       {
           root = null;       
       }
       
       
       /**Returns true if the given target is in the binary tree. 
        * Uses a recursive helper.
        */
       public boolean contains(int data)
       {
           return (containsSub(root, data));
       }
       
       
       /**Given a node, recur down searching for the given data.
        * Recursive containsSub
        */ 
       private boolean containsSub(Node node, int data)
       {
           if (node == null)
           {
               return (false);
           }
    
           if (data == node.data)
           {
               return(true);
           }
           else if (data < node.data)
           {
               return (containsSub(node.left, data));
           }
           else
           {
               return (containsSub(node.right, data));
           }
       }
       
       
       /**Inserts the given data into the BinaryTree
        * Uses a recursive helper
        */
       public void insert(int data) 
       {
           root = insertSub(root, data);
       }
    
       /**Given a node pointer, recur down and insert the given data into the tree
        * Returns the new node pointer
        * Recursive insertSub
        */
       private Node insertSub(Node node, int data)
       {
           if (node == null)
           {
               node = new Node(data);
           }
           else
           {
               if (data <= node.data)
               {
                   node.left = insertSub(node.left, data);
               }
               else
               {
                   node.right = insertSub(node.right, data);
               }
           }
    
           return (node);                   //Return the new pointer to the caller
       }
    
    
       /** preOrderNonIterative() method
          * First, create a printPreorderIterative() that calls the preOrderIterative() method
        */
       public void printPreorderIterative()
       {
            preOrderIterative(root);
       }
    
       /**The preOrderIterative() method used to iterate through the tree
        * @param root
        */
       private void preOrderIterative(Node root)
       {
           Stack nodes = new Stack();
           nodes.push(root);
           Node currentNode;
           
           while (! nodes.isEmpty())
           {
               currentNode = (Node) nodes.pop();
               
               System.out.println("Node data: " + currentNode.data);
    
               Node right = currentNode.right;
               if (right != null)
                   nodes.push(right);
    
               //System.out.println("Node data: " + currentNode.data);
    
               Node left = currentNode.left;
               if (left != null)
                   nodes.push(left);  
           }
       }
    }

  2. #2
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    The method itself looks ok at first glance. Try to make a tree, write it down on paper, then check if it's working correctly.
    EDIT: I gave you code a run, and it seems to work fine.
    Last edited by m00nchile; 11-01-2010 at 07:07 PM.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  3. #3
    hansmoolman is offline Member
    Join Date
    Oct 2010
    Posts
    5
    Rep Power
    0

    Default

    Thanks for the reply, yeah I stepped through the code and it seems to be fine, but shouldnt the preOrder method output values in a ascending order? Eg. if you input 1,6,5,3 - should the output not be 1,3,5,6? My recursive preOrder method seems to do this ok.

  4. #4
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    If you input 1, 6, 5, 3, the BST you get should be this:
    Java Code:
      1
        \
         6
        /
       5
      /
    3
    Preorder is root, left right, so the output should be 1, 6, 5, 3. Now, if you'd change the input to 1,6, 7, 3, you'd get this:
    Java Code:
      1
        \
         6
        /  \
       3    7
    Now the preorder traversal would be 1,6,3,7. The traversal that ouputs a BST in ascending order is inorder, not preorder.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  5. #5
    hansmoolman is offline Member
    Join Date
    Oct 2010
    Posts
    5
    Rep Power
    0

    Default

    Yeah that makes sense to me now thanks. I was going by a recursive preorder method that was given to us in class to compare my output too. Thanks again for clearing this up for me, much appreciated.

Similar Threads

  1. Help with while iterative procedure
    By SweetLD215 in forum New To Java
    Replies: 16
    Last Post: 10-20-2010, 07:54 AM
  2. Iterative help
    By Jnoobs in forum New To Java
    Replies: 5
    Last Post: 10-06-2010, 09:26 PM
  3. Replies: 4
    Last Post: 04-06-2009, 04:54 AM
  4. Iterative Algorithms
    By Zosden in forum Algorithms
    Replies: 1
    Last Post: 07-05-2008, 07:29 AM
  5. Preorder Traversal problem...
    By tuckker in forum New To Java
    Replies: 3
    Last Post: 12-04-2007, 07:06 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •