Binary Tree

Breadth First Scan

Define Binary Tree:

public class BTree {
 BTree left;
 BTree right;
 String id;
 
 public BTree(String id){
  this.id = id;
 }
 
 public BTree Left(){
  return this.left;
 }
 
 public BTree Right(){
  return this.right;
 }
 
 public void setLeaves(BTree left, BTree right){
  this.left = left;
  this.right = right;
 }
 
 public String toString(){
  return this.id;
 }
}

Tree mothods

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class TreeMethod {

 /**
  * Breadth First Traversal
  */
 public static void BFT(BTree root){
  Queue<BTree> queue = new LinkedList<BTree>();
  if(root != null ){   
   queue.offer(root);
  }
  
  BTree node = null;
  while( (node = queue.poll()) != null ){   
   System.out.print(node + " ");
   
   if( node.Left() != null )
    queue.offer(node.Left());
   if( node.Right() != null )
    queue.offer(node.Right());
  }
 }
 
 
 /**
  * Pre Order Traversal
  */
 public static void PreOrder(BTree root){
  if( root == null ){
   return;
  } 
  
  System.out.print(root + " ");
  // traverse left node
  PreOrder(root.Left());
  //traverse right node
  PreOrder(root.Right());
 }
 
 /**
  * Pre Order Traversal without recursion
  */
 public static void PreOrder_NoRecursion(BTree root){
  Stack<BTree> stack = new Stack<BTree>();
  stack.push(root);
  BTree node = null;
  while( !stack.isEmpty() && (node=stack.pop()) != null ){
   System.out.print(node + " ");
   if( node.Right() != null )
    stack.push(node.Right());
   if( node.Left() != null )
    stack.push(node.Left());
  }
 }
 
 /**
  * In Order Traversal
  */
 public static void InOrder(BTree root){
  if( root == null ){
   return;
  }
  // traverse left node
  InOrder(root.Left());

  System.out.print(root + " ");

  //traverse right node
  InOrder(root.Right());
 }
 
 /**
  * In Order Traversal without recursion
  */
 public static void InOrder_NoRecursion(BTree root){
  Stack<BTree> stack = new Stack<BTree>();
  while( root!=null || !stack.isEmpty() ){
   // traverse along the left child till meet the end
   while( root != null ){
    stack.push(root);
    root = root.Left();
   }
   
   root = stack.pop();   
   System.out.print(root + " ");
   
   // start traversal from the right child
   root = root.Right();
  }
 }
 
 /**
  * Post Order Traversal
  */
 public static void PostOrder(BTree root){
  if( root == null ){
   return;
  }
  // traverse left node
  PostOrder(root.Left());

  //traverse right node
  PostOrder(root.Right()); 
  
  System.out.print(root + " ");
 }
 
 /**
  * Post Order Traversal without recursion
  */
 public static void PostOrder_NoRecursion(BTree root){
  Stack<BTree> stack = new Stack<BTree>();
  BTree pre = null;
  while( root!=null || !stack.isEmpty() ){
   // traverse along the left child till meet the end
   while( root != null ){
    stack.push(root);
    root = root.Left();
   }
    
   root = stack.pop();
   while( root.Right() == null || root.Right() == pre ){
    System.out.print(root + " ");    
    pre = root;
    if( stack.isEmpty() ) {
     return;
    }
    root = stack.pop();
   }
   
   stack.push(root);
   root = root.Right();
  }
 }
}

turn a binary tree into a double linked list

public static  void Tree2DLinkedList(BTree root) { 
  if( root == null) {
   return;
  }
  Tree2DLinkedList(root.left);
  if( tail != null ){
   tail.right = root;   
  }
  
  if( head == null ){
   head = root;
  }
  root.left = tail;
  tail = root;
  
  Tree2DLinkedList(root.right);  
 }
 
 static BTree head;
 static BTree tail;

Test method:

public class TestTree {

 /**
  * @param args
  */
 public static void main(String[] args) {
  /**
   *            A
   *          /   \
   *         B     C
   *        / \      \
   *       D   E      F
   *          / \
   *         G   H
   */
  BTree A = new BTree("A");
  BTree B = new BTree("B");
  BTree C = new BTree("C");
  BTree D = new BTree("D");
  BTree E = new BTree("E");
  BTree F = new BTree("F");
  BTree G = new BTree("G");
  BTree H = new BTree("H");

  A.setLeaves(B, C);
  B.setLeaves(D, E);
  E.setLeaves(G, H);
  C.setLeaves(null, F);
  
  System.out.print("Breadth First Traversal: ");
  TreeMethod.BFT(A);
  System.out.println();
  
  System.out.print("Preorder Traversal: ");
  TreeMethod.PreOrder(A);
  System.out.println(); 
  
  System.out.print("Preorder Traversal with no recursion: ");
  TreeMethod.PreOrder_NoRecursion(A);
  System.out.println();
  
  System.out.print("Inorder Traversal: ");
  TreeMethod.InOrder(A);
  System.out.println(); 
  
  System.out.print("Inorder Traversal with no recursion: ");
  TreeMethod.InOrder_NoRecursion(A);
  System.out.println();
  
  System.out.print("Postorder Traversal: ");
  TreeMethod.PostOrder(A);
  System.out.println(); 
  
  System.out.print("Postorder Traversal with no recursion: ");
  TreeMethod.PostOrder_NoRecursion(A);
  System.out.println();

  System.out.println("Building double linked list:"）；
  TreeMethod.Tree2DLinkedList(A);
  tail = TreeMethod.tail;
  while( tail != null ){
   System.out.print(tail + " ");
   tail = tail.left;
  }
  System.out.println();
  head = TreeMethod.head;
  while (head != null ){
   System.out.print(head + " ");
   head = head.right;
  }
 }
}

Result:

Breadth First Traversal: A B C D E F G H
Preorder Traversal: A B D E G H C F
Preorder Traversal with no recursion: A B D E G H C F
Inorder Traversal: D B G E H A C F
Inorder Traversal with no recursion: D B G E H A C F
Postorder Traversal: D G H E B F C A
Postorder Traversal with no recursion: D G H E B F C A
Building double linked list F C A H E G B D
D B G E H A C F