DFT and BFT

This is a good video resource about the theory behind it.
http://www.youtube.com/watch?v=zLZhSSXAwxI

For tree and graph.

DFT: drills down the linked nodes, process the far most not reached nodes the first, then going back for more not reached nodes from last node. stack is naturally exploited to track the nodes that need go back to revisit. it's done when there's no node in the stack. complete of a node's process is done by confirming there's no not visited neighbors.

BFT: have a current processed node, then track the current node's neighbor in a queue for further process. it's done when no node in the queue. Complete of a node's process is done by confirming there's no not visited neighbors.

Both of them require a mechnism to mark the visited nodes. set in java is good data structure for doing this. You can tell if the node is visited the same time you add it to the set.


Tree is special form of graph, the algorithm can be modified to not check if a node is visited.

In tree's case, for DFT, you can do
preorder: root,left,right
inorder : left, root, right
post order :left, right, root

traversal.


Recursive call is realized by stack mechanism and it can be converted to use stack to implement.

Some examples:

package tree;

public class TreeNode {
String val;
TreeNode left;
TreeNode right;

public TreeNode(String value){
this.val=value;
}
}


package tree;

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

public class Excercise {
static TreeNode aTree = new TreeNode("root");
static void prepareATree(){
TreeNode l = new TreeNode("0.left");
TreeNode r = new TreeNode("0.right");
aTree.left = l;
aTree.right = r;
l.left = new TreeNode("1.left");
l.right = new TreeNode("1.right");
r.left = new TreeNode("2.left");
r.right = new TreeNode("2.right");
r.right.right = new TreeNode("3.right");

}
/**
* @param args
*/
public static void main(String[] args) {
prepareATree();
// System.out.println(findHeight(aTree));
// System.out.println(findMaxNodeNumber(aTree));
// System.out.println(findMinNodeNumber(aTree));
// findShortestPath(aTree);
BFTraversal(aTree);
DFTraversal_PreOrder(aTree);
DFTraversal_InOrder(aTree);
DFTraversal_PostOrder(aTree);
}

//maximum edges between root and it's leafs
public static int findHeight(TreeNode root){
if (root==null)return -1;
//+1 is the calculation. for any none null child level, this will be added one up
return Math.max(findHeight(root.left), findHeight(root.right))+1;
}
//find a number of nodes on the height
public static int findMaxNodeNumber(TreeNode root){
if (root==null)return 0;
return Math.max(findMaxNodeNumber(root.left), findMaxNodeNumber(root.right))+1;
}

public static int findMinNodeNumber(TreeNode root){
if (root==null)return 0;
return Math.min(findMinNodeNumber(root.left), findMinNodeNumber(root.right))+1;
}
//analysis: check it layer by layer and identify out a first node that has no child. breadth first traversal
//in order to travel back 
public static void findShortestPath(TreeNode root){
TreeNode curNode;
if (root == null) return;
if(root.left==null && root.right==null){
System.out.println(root.val);
return;
}
Queue tmpQ = new LinkedList();
if(root.left!=null)
tmpQ.add(root.left);
if (root.right!=null)
tmpQ.add(root.right);
System.out.println(root.val);//visit the current node
while(!tmpQ.isEmpty()){
curNode = tmpQ.remove();//remove from head. queue is add to tail, remove from head
if(curNode.left!=null)
tmpQ.add(curNode.left);
if(curNode.right!=null)
tmpQ.add(curNode.right);
if (curNode.left==null && curNode.right==null){
System.out.println("final node:"+curNode.val);
break;
}
System.out.println(curNode.val);
}
}
public static void BFTraversal(TreeNode root){
TreeNode curNode;
if (root == null) return;
if(root.left==null && root.right==null){
System.out.println(root.val);
return;
}
Queue tmpQ = new LinkedList();
if(root.left!=null)
tmpQ.add(root.left);
if (root.right!=null)
tmpQ.add(root.right);
//using printing out as a way of access
System.out.println(root.val);//visit the current node
while(!tmpQ.isEmpty()){
curNode = tmpQ.remove();//remove from head. queue is add to tail, remove from head
//add the current node's children after the current layer's nodes
//we are lining up the nodes here
if(curNode.left!=null)
tmpQ.add(curNode.left);
if(curNode.right!=null)
tmpQ.add(curNode.right);

System.out.println(curNode.val);
}
}
public static void DFTraversal_PreOrder(TreeNode root){
if(root==null)return;
//this is to access the node
System.out.println(root.val);
DFTraversal_PreOrder(root.left);
DFTraversal_PreOrder(root.right);

}
public static void DFTraversal_PostOrder(TreeNode root){
if(root==null)return;
//this is to access the node
DFTraversal_PreOrder(root.left);
DFTraversal_PreOrder(root.right);
System.out.println(root.val);
}
public static void DFTraversal_InOrder(TreeNode root){
if(root==null)return;
//this is to access the node
DFTraversal_InOrder(root.left);
System.out.println(root.val);
DFTraversal_InOrder(root.right);

}
}