The root is the first node to be visited in preorder. After we visit this node we must traverse the left subtree and then return to traverse the right subtree. To enable the return to the right subtree, we save a pointer to the root of this right subtree on a stack provided the right subtree is not empty. When we are traversing the left subtree of the root, its root is visited a pointer to its nonempty right subtree is saved on the stack, and we proceed to traverse its left subtree. When we are done with the traversal of the left subtree, we move into its right subtree (if it is nonempty) or into the right subtree of the nearest ancestor that has a nonempty right subtree. This is done by removing the right subtree root pointer from the top of the stack.
The stack never contains two pairs that correspond to nodes on the same level. When we reach a leaf the stack contains pointers to nonempty right subtrees of nodes on the path from the root to that leaf. So the stack space needed as well as the overall space needed by the traversal is O(h) where his the height of the binary tree that is being traversed. Notice that when a left-skewed binary tree is traversed nothing is added to the stack.
1.
1 package chapter12Tree; 2 3 import dataStructures.ArrayStack; 4 import dataStructures.BinaryTreeNode; 5 6 public class IterativePreorderTraversal 7 { 8 /** visit method that prints the element in the node */ 9 public static void visit(BinaryTreeNode t) 10 {System.out.print(t.element + " ");} 11 12 /** preorder traversal */ 13 public static void preOrder(BinaryTreeNode t) 14 { 15 ArrayStack stack = new ArrayStack(10); 16 BinaryTreeNode currentNode = t; 17 while (true) 18 {// traverse subtree rooted at currentNode in preorder 19 20 // is subtree empty 21 if (currentNode == null) 22 // yes it is, get a subtree to traverse from the stack 23 try 24 { 25 currentNode = (BinaryTreeNode) stack.pop(); 26 } 27 catch (Exception e) 28 {// no untraversed subtrees left 29 return; 30 } 31 32 // first visit the root of the subtree 33 visit(currentNode); 34 35 // save pointer to right subtree for future traversal 36 if (currentNode.rightChild != null) 37 stack.push(currentNode.rightChild); 38 39 // move into left subtree 40 currentNode = currentNode.leftChild; 41 } 42 } 43 }
2.
1 /** a stack class that uses a one-dimensional array */ 2 3 package dataStructures; 4 5 import java.util.EmptyStackException; 6 import utilities.*; 7 8 public class ArrayStack implements Stack 9 { 10 // data members 11 int top; // current top of stack 12 Object [] stack; // element array 13 14 // constructors 15 /** create a stack with the given initial capacity 16 * @throws IllegalArgumentException when initialCapacity < 1 */ 17 public ArrayStack(int initialCapacity) 18 { 19 if (initialCapacity < 1) 20 throw new IllegalArgumentException 21 ("initialCapacity must be >= 1"); 22 stack = new Object [initialCapacity]; 23 top = -1; 24 } 25 26 /** create a stack with initial capacity 10 */ 27 public ArrayStack() 28 {this(10);} 29 30 // methods 31 /** @return true iff stack is empty */ 32 public boolean empty() 33 {return top == -1;} 34 35 36 /** @return top element of stack 37 * @throws EmptyStackException when the stack is empty */ 38 public Object peek() 39 { 40 if (empty()) 41 throw new EmptyStackException(); 42 return stack[top]; 43 } 44 45 /** add theElement to the top of the stack */ 46 public void push(Object theElement) 47 { 48 // increase array size if necessary 49 if (top == stack.length - 1) 50 stack = ChangeArrayLength.changeLength1D(stack, 2 * stack.length); 51 52 // put theElement at the top of the stack 53 stack[++top] = theElement; 54 } 55 56 /** remove top element of stack and return it 57 * @throws EmptyStackException when the stack is empty */ 58 public Object pop() 59 { 60 if (empty()) 61 throw new EmptyStackException(); 62 Object topElement = stack[top]; 63 stack[top--] = null; // enable garbage collection 64 return topElement; 65 } 66 67 /** test program */ 68 public static void main(String [] args) 69 { 70 int x; 71 ArrayStack s = new ArrayStack(3); 72 // add a few elements 73 s.push(new Integer(1)); 74 s.push(new Integer(2)); 75 s.push(new Integer(3)); 76 s.push(new Integer(4)); 77 78 79 // delete all elements 80 while (!s.empty()) 81 { 82 System.out.println("Top element is " + s.peek()); 83 System.out.println("Removed the element " + s.pop()); 84 } 85 } 86 }
3.
1 /** class for nodes used in a binary tree */ 2 3 package dataStructures; 4 5 public class BinaryTreeNode 6 { 7 // package visible data members 8 public Object element; 9 public BinaryTreeNode leftChild; // left subtree 10 public BinaryTreeNode rightChild; // right subtree 11 12 // constructors 13 public BinaryTreeNode() {} 14 15 public BinaryTreeNode(Object theElement) 16 {element = theElement;} 17 18 public BinaryTreeNode(Object theElement, 19 BinaryTreeNode theleftChild, 20 BinaryTreeNode therightChild) 21 { 22 element = theElement; 23 leftChild = theleftChild; 24 rightChild = therightChild; 25 } 26 27 // accessor methods 28 public BinaryTreeNode getLeftChild() {return leftChild;} 29 public BinaryTreeNode getRightChild() {return rightChild;} 30 public Object getElement() {return element;} 31 32 // mutator methods 33 public void setLeftChild(BinaryTreeNode theLeftChild) 34 {leftChild = theLeftChild;} 35 public void setRightChild(BinaryTreeNode theRightChild) 36 {rightChild = theRightChild;} 37 public void setElement(Object theElement) 38 {element = theElement;} 39 40 // output method 41 public String toString() 42 {return element.toString();} 43 }
4.
1 /** Change the length of an array by creating 2 * a new array of the desired length and copying 3 * elements from the old array to the new one. */ 4 package utilities; 5 6 import wrappers.*; 7 import java.lang.reflect.*; 8 9 public class ChangeArrayLength 10 { 11 /** Change the length of the 1D array a. 12 * @param n number of elements in a 13 * @param newLength new length of array 14 * @return array of length newLength with a[0:n-1] copied into it */ 15 public static Object [] changeLength1D(Object [] a, 16 int n, int newLength) 17 { 18 // make sure new length is adequate 19 if (n > newLength) 20 throw new IllegalArgumentException 21 ("new length is too small"); 22 23 // allocate a new array of desired length and same type 24 Object [] newArray = (Object []) Array.newInstance 25 (a.getClass().getComponentType(), newLength); 26 27 // copy from old space to new space 28 System.arraycopy(a, 0, newArray, 0, n); 29 30 return newArray; 31 } 32 33 /* Change the length of a 1D array with a.length elements */ 34 public static Object [] changeLength1D(Object [] a, int newLength) 35 {return changeLength1D(a, a.length, newLength);} 36 37 /** test program */ 38 public static void main(String [] args) 39 { 40 // create an array of length 4 41 MyInteger [] x = {new MyInteger(10), 42 new MyInteger(11), 43 new MyInteger(12), 44 new MyInteger(13)}; 45 46 // output 47 System.out.println("Array length is " + x.length); 48 System.out.print("The elements are "); 49 for (int i = 0; i < 4; i++) 50 System.out.print(x[i] + " "); 51 System.out.println(); 52 53 // increase array length to 8 54 x = (MyInteger []) changeLength1D(x, 8); 55 56 // add two elements to x 57 for (int i = 4; i < 6; i++) 58 x[i] = new MyInteger(10 + i); 59 60 // output 61 System.out.println("Array length is " + x.length); 62 System.out.print("The elements are "); 63 for (int i = 0; i < 6; i++) 64 System.out.print(x[i] + " "); 65 System.out.println(); 66 67 // increase length to 10 68 x = (MyInteger []) changeLength1D(x, 6, 10); 69 70 // add four elements to x 71 for (int i = 6; i < 10; i++) 72 x[i] = new MyInteger(10 + i); 73 74 // output 75 System.out.println("Array length is " + x.length); 76 System.out.print("The elements are "); 77 for (int i = 0; i < 10; i++) 78 System.out.print(x[i] + " "); 79 System.out.println(); 80 81 // reduce length to 5 retaining only first 3 elements 82 x = (MyInteger []) changeLength1D(x, 3, 5); 83 84 // output 85 System.out.println("Array length is " + x.length); 86 System.out.print("The elements are "); 87 for (int i = 0; i < 4; i++) 88 System.out.print(x[i] + " "); 89 System.out.println(); 90 } 91 }