Monday 3 August 2015

Binary Tree Travesal in java

Binary Tree can have at most 2 child. To know about Tree please  click on Tree Introduction.
We can traversal binary tree using below 2 technique.
  1. DFS(Depth First Search): Depth-first traversal (Arkiletian traversal) is easily implemented via a stack
    1. Pre-Order
    2. Post Order
    3. In Order
  2. BFS (Breath First Search) is also known as level order in Tree. breadth-first traversal is easily implemented via a queue
Today, I am going to explain how DFS works in Tree. We have 2 approach to traversal tree using DFS is
1) Recursive Way,
2) Iterative Way.



Pre-Order:  is also known as DLR. First we have to traversal the root node then followed by left sub tree and then followed by right sub tree.Keep continue until tree has been traversed.

Lets take above tree dig, Where root is 1 and left child 2 and right is 3. First we traversal 1 then we have left sub tree. In left sub tree 2 becomes root and 5 becomes left sub tree of 2 . We have to keep traversal until each and every nodes of the tree has been traversed once.

O/P:  1,2,5,9,6,3,4,8,7,10




Sample BinaryTree Class:

public class BinaryDataTree<E> {
    private E data;
    private BinaryDataTree<E> left;
    private BinaryDataTree<E> right;
  
    public BinaryDataTree() {
    }
    public BinaryDataTree(E data) {
        this.data=data;
    }
    public E getData() {
        return data;
    }
    public void setData(E data) {
        this.data = data;
    }
    public BinaryDataTree<E> getLeft() {
        return left;
    }
    public void setLeft(BinaryDataTree<E> left) {
        this.left = left;
    }
    public BinaryDataTree<E> getRight() {
        return right;
    }
    public void setRight(BinaryDataTree<E> right) {
        this.right = right;
    }
}

Recursive Way:




 public void preOrderRecusriveWay(BinaryDataTree<Integer> root) {
   if (root == null) {
            return;
       }

     System.out.print(root.getData() + " ");
     preOrderIterativeWay(root.getLeft());
    preOrderIterativeWay(root.getRight());
}


 Iterative Way:

public void preOrderIterativeWay(BinaryDataTree<Integer> root) {
        Stack<BinaryDataTree<Integer>> s = new Stack<BinaryDataTree<Integer>>();
        if (root == null) {
            System.out.println("No Element In the Tree");
            return;
        }
        while (true) {
            while (root != null) {
                System.out.print(root.getData() + " ");
                s.push(root);
                root = root.getLeft();
            }
            if (s.isEmpty()) {
                break;
            }
            root = s.pop().getRight();
        }
    }



No comments:

Post a Comment