catalogue
[write before]
Today, I have made some understanding and summary of breadth first traversal and depth first traversal. Here is a learning note for further learning. For knowledge points and ideas, refer to articles such as links, and you can directly see the original blog post: Breadth first traversal and depth first traversal of trees，Java implementation of binary tree depth first traversal and breadth first traversal algorithm example
1. Breadth first traversal
1.1 principle
The English abbreviation is BFS, that is, bread FirstSearch.
It takes breadth as the priority and searches layer by layer, just like the spread of virus infection. In terms of process inspection, the nodes of each layer are accessed in turn, and after accessing one layer, they enter the next layer, and each node can only be accessed once.
Breadth first traversal of the tree requires a Queue to store node objects. The Queue is characterized by first in first out.
First insert the left node and then the right node into the queue, so that leaving the queue is to first insert the left node and then the right node.
1.2 code example
(1) Tree node: TreeNode
//Tree node
package MySearchMethod;
public class TreeNode{
Integer val;
TreeNode left;
TreeNode right;
public TreeNode(Integer val){
this.val = val;
left = null;
right = null;
}
}(2) Binary tree: BinaryTree
//Constructing binary tree
package MySearchMethod;
public class BinaryTree<T> {
private TreeNode root;
BinaryTree(){
root = null;
}
public void insertTreeNode(Integer val){
if(root == null){
root = new TreeNode(val);
return;
}
TreeNode currentNode = root;
while(true){
if(val.compareTo(currentNode.val) > 0){
if(currentNode.right == null){
currentNode.right = new TreeNode(val);
break;
}
currentNode = currentNode.right;
}else {
if(currentNode.left == null){
currentNode.left = new TreeNode(val);
break;
}
currentNode = currentNode.left;
}
}
}
public TreeNode getRoot(){
return root;
}
}
(3) Breadth first traversal:
Note: the traversal method below should also be applicable to other trees, not just binary trees. To be studied.
/**
* Breadth first traversal, non recursive
*/
package MySearchMethod;
import java.util.LinkedList;
import java.util.Queue;
public class BreadthFirstSearch {
public static void main(String[] args){
BinaryTree<Integer> tree = new BinaryTree<>();
tree.insertTreeNode(35);
tree.insertTreeNode(20);
tree.insertTreeNode(15);
tree.insertTreeNode(16);
tree.insertTreeNode(29);
tree.insertTreeNode(28);
tree.insertTreeNode(30);
tree.insertTreeNode(40);
tree.insertTreeNode(50);
tree.insertTreeNode(45);
tree.insertTreeNode(55);
System.out.println("Depth first algorithm (non recursive):");
breadthSearch(tree.getRoot());
}
public static void breadthSearch(TreeNode root){
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
TreeNode currentNode;
while(!queue.isEmpty()){
currentNode = queue.poll();
System.out.print(currentNode.val + " ");
if(currentNode.left != null){
queue.offer(currentNode.left);
}
if(currentNode.right != queue){
queue.offer(currentNode.right);
}
}
}
}
Traversal result:
There is an error report of null pointer exception. The reason has not been found. To be supplemented.
Depth first algorithm (non recursive): 35 20 40 15 29 50 16 28 30 45 55 Exception in thread "main" java.lang.NullPointerException at MySearchMethod.BreadthFirstSearch.breadthSearch(BreadthFirstSearch.java:37) at MySearchMethod.BreadthFirstSearch.main(BreadthFirstSearch.java:27) Process finished with exit code 1
2. Depth first traversal
2.1 principle
The English abbreviation is DFS, namely Depth First Search.
In brief, the process is to go deep into each possible branch path to the point where it can no longer go deep, and each node Can only be accessed once.
Depth first traversal of each node requires the use of a stack data structure. Stack is characterized by first in and last out. The whole traversal process is as follows: first press the right node into the stack, and then press the left node, so that the left node is the first and then the right node out of the stack.
For each possible branch path, it can not be further deepened, and each node can only be accessed once. It should be noted that the depth first traversal of binary tree is special, which can be divided into pre order traversal, middle order traversal and post order traversal.
Here we first demonstrate the case of preorder traversal.
1.2 code example
(1) Tree node: TreeNode. Above, omitted.
(2) Binary tree: BinaryTree. Above, omitted.
(3) Depth first traversal:
Note: Here we first demonstrate the case of preorder traversal. Other conditions to be supplemented.
/**
* Depth first traversal, non recursive
*/
package MySearchMethod;
import java.util.Stack;
public class DepthFirstSearch {
public static void main(String[] args){
BinaryTree<Integer> tree = new BinaryTree<>();
tree.insertTreeNode(35);
tree.insertTreeNode(20);
tree.insertTreeNode(15);
tree.insertTreeNode(16);
tree.insertTreeNode(29);
tree.insertTreeNode(28);
tree.insertTreeNode(30);
tree.insertTreeNode(40);
tree.insertTreeNode(50);
tree.insertTreeNode(45);
tree.insertTreeNode(55);
System.out.println("Preorder traversal of depth first algorithm (non recursive):");
depthSearch(tree.getRoot());
}
public static void depthSearch(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode currentNode;
while (!stack.isEmpty()){
currentNode = stack.pop();
System.out.print(currentNode.val + " ");
if(currentNode.right != null){
stack.push(currentNode.right);
}
if(currentNode.left != null){
stack.push(currentNode.left);
}
}
}
}
Traversal result:
Preorder traversal of depth first algorithm (non recursive): 35 20 15 16 29 28 30 40 50 45 55 Process finished with exit code 0