Traversal of binary trees

The traversal of binary numbers mainly includes front, middle and back traversal and level traversal. Front, middle and back belong to DFS, and hierarchical traversal belongs to BFS. DFS can use stacks to simplify operations, and the tree itself is a recursive data structure, so recursion and stack are two key points for DFS.

The key point of BFS is to keep track of whether or not each layer is traversed. We can use an identifier to indicate the end of the current layer.

First of all, the position of the root node is changed, and the order of the left and right nodes is always left and right. For example, a forward traversal is the root in front, left and right. Middle order means roots in the middle, left roots in the right. Posterior means the roots are posterior, the left and right roots.

Examples of preceding code:

   function colorTraversal(tree){
       let stack = [['white',tree]];
       let res = [];
       while(stack.length>0) {const [color,node] = stack.pop();
           if(! node)continue;
           if(color==='white'){
               stack.push(['white',node.right])
               stack.push(['white',node.left])
               stack.push(['gray',node.val])
           }else{
               res.push(node)
           }
       }
       return res;
   }
Copy the code

The above is a pre-order traversal, as long as the stack push order can be slightly changed to achieve the middle order and post-order traversal; Middle order: first push the right tree, then push the current value, then push the left tree, and finally push the left tree.

For hierarchical traversal, change the stack structure to queue

   function colorTraversal(tree){
       let stack = [['white',tree]];
       let res = [];
       while(stack.length>0) {const [color,node] = stack.shift();
           if(! node)continue;
           if(color==='white'){
               stack.push(['gray',node.val])
               stack.push(['white',node.left])
               stack.push(['white',node.right])
           }else{
               res.push(node)
           }
       }
       return res;
   }
Copy the code