Write Java programs that use recursive and non-recursive functions to traverse the given binary tree in(a) Preorder(b) Inorder and(c) Postorder.
class Node { Object data; Node left; Node right; Node( Object d ){ data = d; } } class BinaryTree{ Object tree[]; int maxSize; java.util.Stack<Node> stack = new java.util.Stack<Node>(); BinaryTree( Object a[], int n ){ maxSize = n; tree = new Object[maxSize]; for( int i=0; i<maxSize; i++ ) tree[i] = a[i]; } public Node buildTree( int index ){ Node p = null; if( tree[index] != null ){ p = new Node(tree[index]); p.left = buildTree(2*index+1); p.right = buildTree(2*index+2); }return p; } //Recursive methods public void recursiveInorder(Node p){ if( p != null ){ recursiveInorder(p.left); System.out.print(p.data + " "); recursiveInorder(p.right); } } public void recursivePreorder(Node p){ if( p != null ){ System.out.print(p.data + " "); recursivePreorder(p.left); recursivePreorder(p.right); } } public void recursivePostorder(Node p){ if( p != null ){ recursivePostorder(p.left); recursivePostorder(p.right); System.out.print(p.data + " "); } } //Non-Recursive methods public void nonRecursiverecursivePreorder(Node p){ if(p == null ){ System.out.println("Tree is empty"); return; } stack.push(p); while( !stack.isEmpty() ){ p = stack.pop(); if( p != null ){ System.out.print(p.data + " "); stack.push(p.right); stack.push(p.left); } } } public void nonRecursiverecursiveInorder(Node p){ if(p == null ){ System.out.println("Tree is empty"); return; } while( !stack.isEmpty() || p != null ){ if( p != null ){ stack.push(p); p = p.left; } else{ p = stack.pop(); System.out.print(p.data + " "); p = p.right; } } } public void nonRecursiverecursivePostorder(Node p){ if(p == null ){ System.out.println("Tree is empty"); return; } Node tmp = p; while( p != null ){ while( p.left != null ){ stack.push(p); p = p.left; } while( p != null && (p.right == null || p.right == tmp )){ System.out.print(p.data + " "); tmp = p; if( stack.isEmpty() ) return; p = stack.pop(); } stack.push(p); p = p.right; } } } class BinaryTreeExample{ public static void main(String args[]){ Object arr[] = {'E', 'C', 'G', 'A', 'D', 'F', 'H',null,'B', null, null, null, null,null, null, null, null, null, null}; BinaryTree bt = new BinaryTree( arr, arr.length ); Node root = bt.buildTree(0); System.out.println("Recursive Binary Tree Traversals:"); System.out.print("recursiveInorder: "); bt.recursiveInorder(root); System.out.println(); System.out.print("recursivePreorder: "); bt.recursivePreorder(root); System.out.println(); System.out.print("recursivePostorder: "); bt.recursivePostorder(root); System.out.println(); System.out.println(); System.out.println("Non-recursive Binary Tree Traversals:"); System.out.print("recursiveInorder: "); bt.nonRecursiverecursiveInorder(root); System.out.println(); System.out.print("recursivePreorder: "); bt.nonRecursiverecursivePreorder(root); System.out.println(); System.out.print("recursivePostorder: "); bt.nonRecursiverecursivePostorder(root); } }
Ads