Results 1 to 5 of 5
Thread: Iterative Preorder
- 11-01-2010, 04:28 PM #1
Member
- Join Date
- Oct 2010
- Posts
- 5
- Rep Power
- 0
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); } } }
- 11-01-2010, 07:03 PM #2
Senior Member
- Join Date
- Feb 2010
- Location
- Ljubljana, Slovenia
- Posts
- 470
- Rep Power
- 10
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.
- 11-01-2010, 09:45 PM #3
Member
- Join Date
- Oct 2010
- Posts
- 5
- Rep Power
- 0
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.
- 11-02-2010, 12:28 AM #4
Senior Member
- Join Date
- Feb 2010
- Location
- Ljubljana, Slovenia
- Posts
- 470
- Rep Power
- 10
If you input 1, 6, 5, 3, the BST you get should be this:
Java Code:1 \ 6 / 5 / 3
Java Code:1 \ 6 / \ 3 7
Ever seen a dog chase its tail? Now that's an infinite loop.
- 11-02-2010, 02:29 PM #5
Member
- Join Date
- Oct 2010
- Posts
- 5
- Rep Power
- 0
Similar Threads
-
Help with while iterative procedure
By SweetLD215 in forum New To JavaReplies: 16Last Post: 10-20-2010, 07:54 AM -
Iterative help
By Jnoobs in forum New To JavaReplies: 5Last Post: 10-06-2010, 09:26 PM -
[SOLVED] Traverse database analogous to preorder traversal of graph
By coolFrenzi in forum Advanced JavaReplies: 4Last Post: 04-06-2009, 04:54 AM -
Iterative Algorithms
By Zosden in forum AlgorithmsReplies: 1Last Post: 07-05-2008, 07:29 AM -
Preorder Traversal problem...
By tuckker in forum New To JavaReplies: 3Last Post: 12-04-2007, 07:06 AM
Bookmarks