BFS and DFS

BFS And DFS

• BFS：(Breadth-First-Search ) Breadth first search , Using queue implementation , Look for the shortest path

• DFS：(Depth-First-Search) Depth-first search , Use recursion to implement , Quick discovery of bottom nodes

BFS：

DFS：

In the tree BFS And DFS

BFS application ： Sequence traversal of trees ： queue

public class BinarySearchTree<T extends Comparable<T>> {
    
    // The node of the tree 
    class Node {
    
        // Content of node 
        private T val;
        // Left child node 
        private Node left;
        // Right child node 
        private Node right;

        public Node(T val) {
    
            this.val = val;
        }
    }

	// Sequence traversal  ( breadth-first )
    public List<T> layerOrder() {
    
        List<T> list = new ArrayList<>();
        if (root != null) {
    
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
    
                // Take the first element from the queue 
                Node node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
    
                    queue.offer(node.left);
                }
                if (node.right != null) {
    
                    queue.offer(node.right);
                }
            }
        }
        return list;
    }
}

DFS： Depth first , Middle order traversal of trees （ And preface , In the following order ）

	// In the sequence traversal 
    public List<T> middleOrder() {
    
        // Store the values traversed from the tree 
        List<T> res = new ArrayList<>();
        // Use recursive traversal 
        middleOrder(root, res);
        // Returns a collection of elements in the storage tree 
        return res;
    }

    // In the sequence traversal   recursive 
    private void middleOrder(Node root, List<T> res) {
    
        // Recursion to the end 
        if (root == null) {
    
            return;
        }
        // Recursive operation 
        // First traverse the left tree , Re traversal root, Then traverse the right tree 
        middleOrder(root.left, res);
        res.add(root.val);
        middleOrder(root.right, res);
    }

In the picture BFS and DFS

To be added …