Traversing the binary tree:

Traversal is defined as patrolling the nodes of a binary tree along a search path so that each node is visited once and only once (also known as a tour)Copy the code

Traversal method:

To traverse the three components of a binary tree in turn is to traverse the entire binary treeCopy the code

L: traverses the left subtree D: accesses the root node R: traverses the right subtree If left and then right are specified, there are three ways to traverse the binary tree DLR ———— traverses the binary tree first (root) LDR ———— (root) traverses the binary tree LRD ———— (root) traverses the binary tree

Algorithm description of traversing binary tree:

Sequential traversal of the binary tree: if the binary tree is empty, then empty operation, otherwise (1) access the root node; (2) Traverse the left subtree in order first; (3) Sequential traversal of the binary tree in the right subtree first: if the binary tree is empty, then empty operation, otherwise (1) sequential traversal of the left subtree; (2) Access the root node; (3) Middle order traverses the right subtree and then traverses the binary tree: if the binary tree is empty, the operation is null; otherwise, (1) post-order traverses the left subtree; (2) The right subtree is traversed sequentially; (3) Access the root node

According to the recursive definition of binary tree, traversing left and right subtrees can be carried out “recursively” as traversing binary trees.

Let’s use JavaScript to achieve binary tree traversal

Given a binary tree object

var root = {  
   id: 1.left: {
        id: 2.left: {
            id: 4,},right: {id:5}},right: {
        id: 3.left: {
            id: 6
        },
        right: {
            id: 7}}}Copy the code

Recursion is sequential traversal

var res = []  

function DLR(root) {  

  if(root ! =null) {
      res.push(root.id)
      if(root.left) {
          DLR(root.left)
      }
      if(root.right) {
          DLR(root.right)
      }
  }
  return res
}  

console.log('Recursive sequential traversal', DLR(root))  
Copy the code

Sequential traversal in recursion

var res = []  

function LDR(root) {  

    if(root ! =null) {
        if(root.left) {
            LDR(root.left)
        }
        res.push(root.id)
        if(root.right) {
            LDR(root.right)
        }
    }
    return res
}  

console.log('Order traversal in recursion', DLR(root))  
Copy the code

Recursive order traversal

var res = []  

function LRD(root) {  

    if(root ! =null) {
        if(root.left) {
            LRD(root.left)
        }
        if(root.right) {
            LRD(root.right)
        }
        res.push(root.id)
    }
    return res
}  

console.log('Recursive order traversal', LRD(root))  
Copy the code

Having looked at the recursive traversal above, let’s compare the non-recursive binary tree traversal.

Non-recursive sequential traversal

Put the tree to be traversed into the arR array. After using the pop() method of the array, return the tree, extract the root of the tree, put the right subtree into the ARR, and then put the left subtree into the ARR (so that the pop will be left and then right), and then loop the above operation. Pop arR array, get the root, and then in the right subtree push ARr, the left subtree push arr... cycleCopy the code
function DLR(root) {  

    var res = [] , arr =[]
    if(root ! =null){
        arr.push(root)
    }
    while (arr.length > 0) {
        var temp = arr.pop()
        res.push(temp.id)
        if(temp.right){ // Put the right subtree first and then the left subtree
            arr.push(temp.right)
        }
        if(temp.left){
            arr.push(temp.left)
        }
    }
    return res
}  

console.log('Non-recursive sequential traversal', DLR(root))
Copy the code

Nonrecursive sequential traversal

I'm going to put everything on the left in arR and then output itCopy the code
function LDR(root) {  

    var res = [] , arr =[]
    while (true) {while(root ! =null){
            arr.push(root)
            root = root.left
        }
        // Terminating condition: the tree is finished
        if(arr.length===0) {
            break;
        }
        let temp = arr.pop()
        res.push(temp.id)
        root = temp.right
    }
    return res
}  

console.log('Non-recursive order traversal', LDR(root))
Copy the code

Non-recursive post-order traversal

It's going to be the root of right and left and then the other way aroundCopy the code
function LRD(root) {  

    var res = [] , arr =[]
    if(root ! =null){
        arr.push(root)
    }
    while (arr.length > 0) {
        var temp = arr.pop()
        res.push(temp.id)
        if(temp.left){
            arr.push(temp.left)
        }
        if(temp.right){
            arr.push(temp.right)
        }
    }
    return res.reverse()
}  

console.log('Non-recursive post-order traversal', LRD(root))Copy the code