Binary tree definition

A binary tree is a tree structure that has the following characteristics:

  • Each node has at most two subtrees, that is, no node with a degree greater than 2 (degree is the number of direct subnodes of the tree node).
  • The subtrees of a binary tree have left and right subtrees, and their order cannot be arbitrarily reversed

What does a binary tree do?

The BST that Babel builds at compile time is a binary tree, the DIff in vue, and the virtual DOM, all of which are dependent on binary trees. Binary tree power is far more than this, the use of binary tree before the order traversal display directory structure, the use of binary tree sequence traversal to achieve expression tree, in the compiler is very useful, the use of binary tree subsequent traversal to achieve the calculation of directory files and information. In a word, binary tree on the computer field can be said to be everywhere, skilled use of binary tree, improve the efficiency of the program, improve the readability of the program, so many advantages, quickly learn ah

Binary tree traversal

In general, there are four ways to traverse a binary tree

  • Fore-order traversal: parent -> left -> right subtree
  • Middle order traversal: left subtree -> parent -> right subtree
  • Back-order traversal: left subtree -> right subtree -> parent
  • Hierarchical traversal: accesses all nodes of the current layer layer by layer, from top to bottom and left to right

Chestnuts, as shown


Previous traversal result: ABDHIECFG

Middle order traversal result: HDIBEAFCG

Subsequent traversal result: HIDEBFGCA

Hierarchy traversal: ABCDEFGHI

JS binary tree expression

“node“

function TreeNode(val) {
     this.val = val;
     this.left = this.right = null;
}
Copy the code

“Convert the above image to a tree in JS:“

var tree = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
            left: {
                val: "H",
                left: null,
                right: null
            },
            right: {
                val: "I",
                left: null,
                right: null
            }
        },
        right: {
            val: "E",
            left: null,
            right: null
        }
    },
    right: {
        val: "C",
        left: {
            val: "F",
            left: null,
            right: null
        },
        right: {
            val: "G",
            left: null,
            right: null
        }
    }
}
Copy the code

Through the calendar calculation method

Generally speaking, tree traversal can be divided into recursive traversal and non-recursive traversal. The advantage of recursive traversal is that the code is simple and easy to understand, but the disadvantage is that the execution efficiency is low. Non-recursive traversal is just the opposite, efficient, but large amount of code, difficult to understand. The following three recursive traversal methods are introduced. In fact, they can also be used as templates. The essence of many problems about binary trees still lies in traversal.

The recursive traversal

“Sequential traversal (recursion) :“

Function preOrder(root) {if(root) {console.log(root.value) PreOrder (root.left) preOrder(root.right)}}Copy the code

“Middle order traversal (recursive) :“

function inOrder(root) {
    if(root) {
        inOrder(root.left)
        console.log(root.val)
        inOrder(root.right)
     }
}
Copy the code

“Post-order traversal (recursion) :“

function postOrder(root) {
    if(root) {
        postOrder(root.left)
        postOrder(root.right)
        console.log(root.val)
     }
}
Copy the code

Test the binary tree defined above

PreOrder (tree) // ABDHIECFG inOrder (tree) // HDIBEAFCG postOrder (tree) // HIDEBFGCACopy the code

As expected, by the way, the above three recursive traversals are implemented using the system stack.

Non-recursive traversal

Next, I’ll introduce non-recursive methods, which may be harder to understand than recursion, but will be easier to write if you get to the core

“Sequential traversal (non-recursive) :“

function preOrder(root) {
   if(! root) {return false} // Stop if the root node is empty
    let stack = [] // Initialization stack, used to store already accessed nodes, easy to trace back
    let p = root // Assign the root node to p
   while(stack.length || p) { // the stack is not empty or p is not empty
 if(p) { // When p is not empty, go straight to the left, remembering to visit the node first and then push the node  console.log(p.val)  stack.push(p)  p = p.left  }  else { // When p is empty, take the last node you passed and go right  p = stack.pop()  p = p.right  }  } } Copy the code

“Middle-order traversal (non-recursive) :“

function inOrder(root) {
   if(! root) {return false} // Stop if the root node is empty
    let stack = [] // Initialization stack, used to store already accessed nodes, easy to trace back
    let p = root // Assign the root node to p
   while(stack.length || p) { // the stack is not empty or p is not empty
 if(p) { // When p is not empty, go straight to the left. This is the difference from the previous traversal  stack.push(p)  p = p.left  }  else { // When p is empty, take the last node you passed and go right  p = stack.pop()  console.log(p.val)  p = p.right  }  } } Copy the code

I don’t know if you noticed, it’s almost the same as the previous sequence, but the difference is when to access the node. The front order is to press the stack and then access, the middle order is to press the stack first, and then access out of the stack.

“Post-order traversal (non-recursive)“

Many people think that the subsequent traversal is the most difficult. Indeed, if you write it in the order of left -> right -> root, it will involve the judgment of the access state of the node, which will be more complicated. But I’m not going to do that, I want you to be able to write down the middle order and the back order as soon as you’ve mastered pre-order traversal and non-recursion. Trust me, ok? My idea is this: “The order of backward traversal is left -> right -> root, right? So if I first traversal in the way of root -> right -> left, and then invert the result, it becomes left -> right -> root.” Most importantly, if you iterate root -> right -> left, you’re going to iterate pretty much the same way, just changing a line or two. Here is the code that follows the above thread

function postOrder(root) {
   if(! root) {return false} // Stop if the root node is empty
    let stack = [] // Initialization stack, used to store already accessed nodes, easy to trace back
    let result = [] // Save the root -> right -> left access results, to the end of the reverse output
    let p = root // Assign the root node to p
 while(stack.length || p) { // the stack is not empty or p is not empty  if(p) { // When p is not empty, go straight to the right, remember to visit the node first and then push the node  result.push(p.val) // If the value of the node is pushed on the stack, the output of the whole stack will be inverted  stack.push(p)  p = p.right / / right  }  else { // When p is empty, take the last node that passes through and go left  p = stack.pop()  p = p.left  }  }  result.reverse().forEach(val= > console.log(val)) // Reverse the output, this is the result of the order traversal } Copy the code

You see, this is much easier, the main idea is still pretty much the same as the previous iteration, with a stack to store the results

Okay, now for the last one, hierarchical traversal. There is no recursion for hierarchical traversal, we maintain access in layer order through an array of simulated queues. The root node is first queued. When the queue is not empty, the body of the loop is executed: the first node of the queue is taken out. If the node has a left subtree, the left subtree of the node is put into the queue. If the node has a right subtree, the right subtree of the node is queued. The loop then continues until the queue is empty.

Level traversal

function floorOrder(root) {
   if(! root) {return false} // Stop if the root node is empty
    let queue = [] // Initialize the queue
    queue.push(root) // The root node joins the queue
    while(queue.length) { // If the queue is not empty, the loop body continues
 let p = queue.shift() // take the first node of the queue and assign it to p. Note that the queue length has been reduced by 1 since the queue exit  console.log(p.val)  if(p.left) { // if the left node of p is not empty, the queue is joined  queue.push(p.left)  }  if(p.right) { // If the right node of p is not empty, the queue is joined  queue.push(p.right)  }  }  } Copy the code

conclusion

Binary tree are introduced in this definition, characteristics, USES, node data structure before and after the sequence of the recursive non-recursive algorithm, and hierarchical calendar calculation method, your friend can take the algorithm implementation whether to run the result is right, if where there is not the right place, eager to friends can leave a message under the feedback, thanks! Personally, for the above introduction to the way of traversal, can be used as a template to remember, do not understand can be used to simulate the implementation of the algorithm, painting painting you may understand! Binary tree traversal is the basis of binary tree correlation algorithm, we must be skilled, come on together!

My personal website: www.jianfengke.com/

This article is formatted using MDNICE