[tree for Java] #data structure #tree #bfs #dfs

BreadthFirsSearch.java

import java.util.*;

public class BreathFirstSearch {
  public static bfs(Node tree) {
    // using queue for BFS algorithm
    Queue<Node> queue = new LinkedList<>();
    
    // enqueue root
    queue.add(tree);
    
    while (queue.size() > 0) {
      Node node = queue.poll();
      
      System.out.println(node.value);
      
      if (node.left != null)
        queue.add(node.left);
      
      if (node.right != null)
        queue.add(node.right);
    }
  }
  
  public static void main(String[] argc) {
    // assuming we've already created the tree;
    Node tree;
    
    bfs(tree);
  }
}

CreateTree.java

import java.util.Queue;

class Node {
  public int value;
  public Node left;
  public Node right;
  
  Node(int value) {
    this.value = value;
    left = null;
    right = null;
  }
}

public class CreateTree {
  
  // using BFS to insert a node
  public static void insertTree(Node tree, int value) {
    Queue<Node> queue = new LinkedList<>();
    
    // enqueue root
    queue.add(tree);
    
    while (queue.size() > 0) {
      Node node = queue.poll();
      
      if (node.left == null) {
        node.left = new Node(value);
        break;
      } else if (node.right == null) {
        node.right = new Node(value);
        break;
      }
      
      // scan children
      queue.add(node.left);
      queue.add(node.right);
    }
    
    public static void main(String[] argc) {
      int[] a = {1, 1, 3, 5, 7, 9, 11};
      
      // create the binary tree
      Node tree = new Node(a[0]);
      
      for (int i = 1 ; i < a.length ; i++) {
        insertTree(tree, a[i]);
      }
    }
  }
}

DepthFirstSearchInorder.java

public class DepthFirstSearchInorder {
  public static void inorder(Node tree) {
    Stack<Node> stack = new Stack<Node>();
    Node node = tree;
    
    while (true) {
      if (node != null) {
        // left part
        stack.add(node);
        node = node.left;
      } else {
        if (stack.size() == 0)
          break;
        
        Node n = stack.pop();
        
        // output the result
        System.out.println(n.x);
        
        // right part
        node = n.right;
      }
    }
  }
  
  public static void inorder_recursive(Node tree) {
    if (tree == null)
      return;
    
    inorder_recursive(tree.left);
    System.out.println(n.x); // output the result
    inorder_recursive(tree.right);
  }
  
  public static void main(String[] argc) {
    Node tree;
    
    inorder(tree);
    inorder_recursive(tree);
  }
}

DepthFirstSearchPostorder.java

public class DepthFirstSearchPostorder {
  // because post-order is too complicated, so we just use recursive to solve the problem
  public static void postorder_recursive(Node tree) {
    if (tree == null)
      return;
   
    postorder_recursive(tree.left);
    postorder_recursive(tree.right);
    System.out.println(tree.x);
  }
  
  public static void main(String[] argc) {
    Node tree;
    
    postorder_recursive(tree);
  }
}

DepthFirstSearchPreorder.java

public class DepthFirstSearchPreorder {
  public static void preorder(Node tree) {
    Stack<Node> stack = new Stack<Node>();
    stack.add(tree);
    
    while (true) {
      if (stack.size() == 0)
        break;
      
      Node node = stack.pop();
      
      // output the result
      System.out.println(node.x);
      
      if (node.right != null)
        stack.add(node.right);
      if (node.left != null)
        stack.add(node.left);
    }
  }
  
  public static void preorder_recursive(Node tree) {
    if (tree == null)
      return;
    
    System.out.println(tree.x);
    preorder_recursive(tree.left);
    preorder_recursive(tree.right);
  }
  
  public static void main(String[] argc) {
    Node tree;
    
    preorder(tree);
  }
}