Binary Tree Traverse Java Source Code

22
January

Binary Tree Traverse Java Source Code

Written by I Made Krisna. 1 comment Posted in: Programming, Tutorial
Tagged with algorithm, bfs, binary, breadth, code, data, first, inorder, java, levelorder, open, postorder, preorder, search, source, structure, travese, tree

Traverse is a method for looking the elements of a tree. In this case, it will be Binary Search Tree traverse, it also can be implemented on ordinary binary tree because the concepts of traverse still same. You can use or just look the example of tree (Binary Search Tree) here [Binary Search Tree Java Source Code].

PreOrder Traversal. This kind of traverse use “Look, go Left, go Right” on each nodes or elements of a tree. And will be give result as [F B A D C E G I H] Let’s look at Java Programming Language implementation of this traverse…

    private void printPreOrder(BinaryTreeNode start){
        if (start == null) return;
        System.out.print(start.getInfo()+" ");
        printPreOrder(start.leftChild);
        printPreOrder(start.rightChild);
    }

InOrder Traversal. This kind of traverse use “go Left, Look, go Right” on each nodes or elements of a tree. This traverse can produce sorted result if used on Binary Search Tree. [A B C D E F G H I]

    private void printInOrder(BinaryTreeNode start){
        if (start == null) return;
        printInOrder(start.leftChild);
        System.out.print(start.getInfo()+" ");
        printInOrder(start.rightChild);
    }

PostOrder Traversal. This kind of traverse use “go Left, go Right, Look” on each nodes or elements of a tree. And the result is : [A C E D B H I G F]

    private void printPostOrder(BinaryTreeNode start){
        if (start == null) return;
        printPostOrder(start.leftChild);
        printPostOrder(start.rightChild);
        System.out.print(start.getInfo()+" ");
    }

LevelOrder Traversal. This is the last travesal, also known with “BFS” or “Breadth First Search”. It start from the root and expanding per level from left to right. so the result is : [F B G A D I C E H]. When implementing this kind of traverse, we need help from Queue Data Structure, in this case i will use Generic LinkedList from Java, because Queue from Java didn’t implemented yet (still interface class).

    private void printLevelOrder(){
        java.util.LinkedList<BinaryTreeNode> queue = new java.util.LinkedList<BinaryTreeNode>();
        queue.addLast(this.root);
        while (queue.size() > 0){
            BinaryTreeNode first = queue.removeFirst();
            System.out.print(first.getInfo()+" ");
            if (first.leftChild != null) queue.addLast(first.leftChild);
            if (first.rightChild != null) queue.addLast(first.rightChild);
        }
    }