import java.util.Stack;
public class TreeTraversal {
public static void preOrderTraversal(TreeBNode root) {
if (null != root) {
System.out.print(root.data + " ");
preOrderTraversal(root.leftChild);
preOrderTraversal(root.rightChild);
}
}
public static void preOrderWithoutRec(TreeBNode root) {
Stack s = new Stack<>();
if (null == root) {
return;
}
else {
s.push(root);
while (!s.isEmpty()) {
TreeBNode temp = s.pop();
System.out.print(temp.data + " ");
if (temp.rightChild != null) {
s.push(temp.rightChild);
}
if (temp.leftChild != null) {
s.push(temp.leftChild);
}
}
}
}
public static void inOrderTraversal(TreeBNode root) {
if (null != root) {
inOrderTraversal(root.leftChild);
System.out.print(root.data + " ");
inOrderTraversal(root.rightChild);
}
}
public static void INOrderWithoutREC(TreeBNode root){
if ( null == root){
return;
}else{
Stack st = new Stack();
boolean completed = false;
TreeBNode current = root;
while(!completed){
if(null!=current){
st.push(current);
current = current.leftChild;
}else{
if(st.isEmpty()){
completed = true;
}else{
current = st.pop();
System.out.print(current.data+" ");
current = current.rightChild;
}
}
}
}
}
public static void postOrderTraversal(TreeBNode root) {
if (null != root) {
postOrderTraversal(root.leftChild);
postOrderTraversal(root.rightChild);
System.out.print(root.data + " ");
}
}
public static void postOrderWithoutRecu(TreeBNode root) {
Stack s = new Stack<>();
Stack s1 = new Stack<>();
s.push(root);
while(!s.isEmpty()) {
TreeBNode temp = s.pop();
s1.push(temp);
if(temp.leftChild!=null) {
s.push(temp.leftChild);
}
if(temp.rightChild!=null) {
s.push(temp.rightChild);
}
}
while(!s1.isEmpty()) {
System.out.print(s1.pop().data+" ");
}
}
public static void main(String a[]) {
TreeBNode root = new TreeBNode(10);
root.leftChild = new TreeBNode(20);
root.rightChild = new TreeBNode(30);
root.leftChild.leftChild = new TreeBNode(40);
root.leftChild.rightChild = new TreeBNode(50);
root.rightChild.leftChild = new TreeBNode(60);
root.rightChild.rightChild = new TreeBNode(70);
System.out.println("------Preorder----");
preOrderTraversal(root);
System.out.println("");
System.out.println("----pre without Recu");
preOrderWithoutRec(root);
System.out.println();
System.out.println("");
System.out.println("----------postOrder--------");
postOrderTraversal(root);
System.out.println();
System.out.println("---post without Rec");
postOrderWithoutRecu(root);
System.out.println("");
System.out.println("---In Order--");
inOrderTraversal(root);
System.out.println("");
System.out.println("---In Order REC---");
INOrderWithoutREC(root);
}
}
Comments
Post a Comment