Implementation of depth first and breadth first traversal of binary tree

The realization of depth first and breadth first traversal of binary tree

What is a binary tree

Binary tree is a tree storage structure , A tree that meets the following two conditions is a binary tree .

1. It's an ordered tree .
2. The degree of each node cannot exceed 2
   

The degree of a tree refers to the node subtree , That is to say, the subtree of each node of a binary tree cannot be more than 2.
Java Implementation of binary tree structure in

class TreeNode {
    
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {
    }
     TreeNode(int val) {
     this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
    
         this.val = val;
         this.left = left;
         this.right = right;
     }
}

Each node of the binary tree saves its own data and child nodes , In fact, it is a recursive structure , Therefore, it is very simple to use recursive method to obtain the data of binary tree . The traversal of binary trees is mainly divided into two kinds , Depth-first traversal （Depth First Search） And breadth first traversal （Breadth First Search）.

Depth first traversal of binary tree

Depth first traversal of a binary tree is to access the binary tree from a certain layer according to a certain order , After accessing all nodes of the current layer, enter the next layer , According to the order of the root node in the traversal process , Depth first traversal is divided into preorder traversal , Middle order traversal and post order traversal .

1. The first sequence traversal
   Preorder traversal is to visit the root node first , Then visit the left and right nodes respectively to traverse the binary tree .
   
   For a binary tree in the figure above , Its preorder traversal order is A,B,D,E,F,G,C,H, First visit A node , Then access its left node B, Again because B It is also the root node of its subtree , So visit its left node , This is the order above .
   use Java There are mainly two ways to realize preorder traversal: stack and recursion , The following middle sequence and post sequence will also be implemented in these two ways .
   Java Recursive way to achieve preorder traversal ：

public void firstSearch(TreeNode root){
    
        if(root!=null){
    
            System.out.println(root.val);
            firstSearch(root.left);
            firstSearch(root.right);
        }
    }

Very simple code , There's no need to explain
Java Stack way to achieve preorder traversal ：

public void firstSearch2(TreeNode root){
    
        Stack<TreeNode> stack=new Stack<>();
        while(root!=null||stack.size()>0){
    
            if(root!=null){
    
                System.out.println(root.val);
                stack.push(root);
                root=root.left;
            }else{
    
                TreeNode pop = stack.pop();
                root=pop.right;
            }

        }
    }

First create a stack , Then access the data of the root node , Finally, push it onto the stack and take out its left child node as the value of the next cycle , If the current root node is found to be null, It means that the left node of the previous node is null, Then pop it from the stack and take its right child node as the value of the next cycle , Until there are no elements in the stack .

2. In the sequence traversal
   The middle order traversal of a binary tree is to traverse first left, then root, and finally right nodes .
   

For the binary tree in the figure above , Its middle order traversal method is E,D,F,B,G,A,C,H.
Java Recursive way to achieve sequence traversal ：

public void firstSearch3(TreeNode root){
    
        if(root!=null){
    
            firstSearch3(root.left);
            System.out.println(root.val);
            firstSearch3(root.right);
        }
    }

It's still very simple , Just change the execution order of the code , It turns into traversing the left node first , Then output the root node , Finally, output the right node .
Java Stack way to achieve sequence traversal ：

public void firstSearch4(TreeNode root){
    
        Stack<TreeNode> stack =new Stack<>();
        while(root!=null||stack.size()>0){
    
            if(root!=null){
    
                stack.push(root);
                root=root.left;
            }else{
    
                TreeNode pop = stack.pop();
                System.out.println(pop.val);
                root=pop.right;
            }
        }
    }

It is no different from the method of preorder traversal , Just like recursion, it's just the code order of exchange , When all the left child nodes are pushed into the stack , Pop up traversal again , and
3. After the sequence traversal
The middle order traversal of binary tree is to traverse the root node from left to right .

This is also the binary tree , According to the way of post order traversal, the result is ,E,F,D,G,B,H,C,A.
Java Recursive way to achieve subsequent traversal

public void firstSearch5(TreeNode root){
    
        if(root!=null){
    
            firstSearch5(root.left);
            firstSearch5(root.right);
            System.out.println(root.val);
        }
    }

Java Stack to achieve subsequent traversal

public void firstSearch7(TreeNode root){
    
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode pre = null;
            stack.push(root);
            while(!stack.isEmpty()){
    
                TreeNode curr = stack.peek();
                if((curr.left == null && curr.right == null) ||
                        (pre != null && (pre == curr.left || pre == curr.right))){
    
                    // If the left and right child nodes of the current node are empty or the last accessed node is the child node of the current node , The current node is out of the stack 
                    System.out.println(curr.val);
                    pre = curr;
                    stack.pop();
                }else{
    
                    if(curr.right != null) stack.push(curr.right); // First press the right node on the stack 
                    if(curr.left != null) stack.push(curr.left);   // Then put the left node on the stack 
                }
            }
    }

The implementation of post order traversal stack is more complex than the first two , Because it requires us to pop the root node out of the stack and not access it when it has a right node , Finally, visit it . In the first half of the code, it is the same idea as the middle order traversal , First find the leftmost child node , The difference is , When we play the stack, we judge every time , Whether its right node is empty and whether its right node was accessed last time , If this condition is not met, we will store it in the stack , Take its right node as the next node , Access it after accessing its left and right nodes .

Traversing a binary tree first

The breadth first traversal of binary tree is from top to bottom , Traverse the binary tree layer by layer ,

For the binary tree in the above figure , Its breadth first traversal result is A,B,C,D,G,H,E,F.
Java Queue way to achieve the breadth first traversal of binary tree ：

public void firstSearch8(TreeNode root){
    
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
    
            queue.add(root);
        }
        while(!queue.isEmpty()){
    
            TreeNode remove = queue.remove();
            System.out.println(remove.val);
            if(remove.left!=null){
    
                queue.add(remove.left);
            }
            if(remove.right!=null){
    
                queue.add(remove.right);
            }
        }
    }

It's simple , Using the idea of queue first in first out , After accessing the root node, put its next child node at the end of the queue , After traversing this layer in this way , Then you can visit the next level node .

Then the main ways of traversing binary trees are introduced , In error , Welcome to point out