How is breadth-first traversal similar to traversal of a binary tree?

Breadth-first traversal is similar to level traversal of a binary tree. Breadth-first search starts from the root node and searches and traverses along the width of the tree, that is, it traverses hierarchically; it visits each layer sequentially from top to bottom, and in each layer, from left to right (or from Right to left) to access nodes, and after accessing one level, enter the next level until no nodes can be accessed.

Breadth First Search (actually a hierarchical traversal of a binary tree), also called breadth-first search or horizontal-first search, starts from the root node Begins a search traversal along the width of the tree.

Access each layer sequentially from top to bottom. In each layer, access nodes from left to right (or right to left). After visiting one layer, enter the next layer until until no node can be accessed.

The traversal order of the above binary tree is: ABCDEFG. Queues can be used to implement breadth-first search.

Breadth-first search algorithm:

Retains all nodes, takes up a lot of space; has no backtracking operation (i.e. no stacking or popping operations), and runs fast.

The breadth-first search algorithm generally needs to store all the nodes generated, and the storage space occupied is much larger than that of the depth-first search. Therefore, during programming, the issues of overflow and memory space saving must be considered. However, the breadth-first search method generally does not have backtracking operations, that is, push and pop operations, so it runs faster than depth-first search.

Example:

The process inspection is to visit each layer of nodes in sequence, and complete the visit to one layer Go to the next level, and each node can only be visited once. For the above example, the results of breadth-first traversal are: A, B, C, D, E, F, G, H, I (assuming that nodes in each layer are accessed from left to right).

Breadth-first traverse of each node requires the use of a queue (Queue) data structure. The characteristic of queue is first-in-first-out. In fact, double-ended queues can also be used. The difference is that the first position of the double-ended queue can be inserted and Pop up the node. The entire traversal process is as follows:

First insert the A node into the queue, queue(A);

Pop up the A node, and insert A's child nodes B and C into the queue. , at this time, B is at the head of the queue, C is at the end of the queue, queue (B, C);

Pop the B node and insert B's child nodes D and E into the queue. At this time, C is at the head of the queue. , E is at the end of the queue, queue (C, D, E);

Pop the C node, and insert the child nodes F, G, and H of C into the queue. At this time, D is at the head of the queue and H is at the end of the queue. The end of the queue, queue (D, E, F, G, H);

Pop the D node, D has no child nodes, at this time E is at the beginning of the queue, H is at the end of the queue, queue (E, F, G, H);

...Go down in sequence, and the final traversal is completed

The Java code is roughly as follows:

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ArrayList<Integer> wide(TreeNode root) {
        ArrayList<Integer> lists=new ArrayList<Integer>();
        if(root==null)
            return lists;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            lists.add(node.val);
		}
        return lists;
    }
}

For more related knowledge, please visit: PHP中文网!

The above is the detailed content of How is breadth-first traversal similar to traversal of a binary tree?. For more information, please follow other related articles on the PHP Chinese website!