The cause of

Binary tree is almost a required knowledge point in the interview process, most of the description process is through C, C++, JAVA, Python and other languages to achieve, here with JS language to achieve the next similar function, front-end, nodeJS direction and full stack direction of students can be referred to.

The sample

All of the following implementations are based on the following binary tree example:

As shown in the figure, the process uses the binaryTree library. The code is as follows:

const BinaryTree = require('binarytree');

let binaryTree = new BinaryTree('F');
let bNode = binaryTree.insert('B'.'left', binaryTree.root);
let aNode = binaryTree.insert('A'.'left', bNode);
let dNode = binaryTree.insert('D'.'right', bNode);
let cNode = binaryTree.insert('C'.'left', dNode);
let eNode = binaryTree.insert('E'.'right', dNode);
let gNode = binaryTree.insert('G'.'right', binaryTree.root);
let iNode = binaryTree.insert('I'.'right', gNode);
let hNode = binaryTree.insert('H'.'left', iNode);
Copy the code

DFS

Deep traversal has three traversal methods: preorder, middle order and post order. The recursive method is very easy to understand. The code is as follows:

Preorder traversal: root node –> left subtree –> right subtree

function preorderDFS(root) {
  const nodeList = [];
  preorder(root, nodeList)
  return nodeList;

  function preorder(root, nodeList) {
    if(root ! = =null) { nodeList.push(root.data) preorder(root.left, nodeList); preorder(root.right, nodeList); }}}Copy the code

In order traversal: left subtree -> root -> right subtree

function inorderDFS(root) {
  const nodeList = [];
  inorder(root, nodeList);
  return nodeList;

  function inorder(root, nodeList) {
    if(root ! = =null) { inorder(root.left, nodeList); nodeList.push(root.data); inorder(root.right, nodeList); }}}Copy the code

Post-order traversal: left subtree -> right subtree -> root

function postorderDFS(root) {
  const nodeList = [];
  postorder(root, nodeList);
  return nodeList;

  function postorder(root, nodeList) {
    if(root ! = =null) {
      postorder(root.left, nodeList);
      postorder(root.right, nodeList);
      nodeList.push(root.data)
    }
  }
}
Copy the code

BFS

You need a queue, and the root node joins the queue first. The queue performs the exit operation, the exit element has the left child to enter the queue, does not care, has the right child to enter the queue, does not care. Then continue until the queue is empty.

function BFS(root) {
  const q = [root];
  const nodeList = [];
  while (q.length > 0) {
    const node = q.pop();
    nodeList.push(node.data);
    if(node.left ! = =null) q.unshift(node.left);
    if(node.right ! = =null) q.unshift(node.right);
  }
  
  return nodeList;
}
Copy the code

Snake print

The printing sequence is shown in the figure:

Similar to BFS, but different. You can think like BFS. Nodes printed first at the previous layer have children printed after the next layer, and their children need to be stored on the stack according to the idea. The printing order of the left and right children is opposite between the front and back layers. Therefore, we need two rules to implement this. One rule stores the order of the odd layer nodes in the stack: first the left child and then the right child; the other rule stores the order of the even layer nodes in the stack: first the right child and then the left child. Suppose lrStack stores the odd layer nodes and rlStack stores the even layer nodes:

  1. The root node F is the first layer, the odd layer. Therefore, the lrStack is labeled F
  2. LrStack calls all elements, that is, F calls, and since the next layer is an even number of layers, calls are placed in the rlStack in the order of the right child and the left child
  3. RlStack calls all elements B –> G, because the next layer is an odd number of layers, so the lrStack is called in the order of left child and right child
  4. LrStack calls all elements I –> D –> A, because the next layer is an even number of layers, so in order of right children, left children into the rlStack
  5. RlStack calls all elements C –> E –> H, because the next layer has no data, end

The code is as follows:

function printBintryTree(root) {
  const lrStack = [];
  const rlStack = [];
  lrStack.push(root);
  while(lrStack.length > 0 || rlStack.length > 0) {
    if (lrStack.length > 0 && rlStack.length === 0) {
      while (lrStack.length > 0) {
        const tNode = lrStack.pop();
        console.log(tNode.data);
        if(tNode.right ! = =null) {
          rlStack.push(tNode.right);
        }
        if(tNode.left ! = =null) { rlStack.push(tNode.left); }}}if (rlStack.length > 0 && lrStack.length === 0) {
      while (rlStack.length > 0) {
        const tNode = rlStack.pop();
        console.log(tNode.data);
        if(tNode.left ! = =null) {
          lrStack.push(tNode.left);
        }
        if(tNode.right ! = =null) {
          lrStack.push(tNode.right);
        }
      }
    }
  }
}
Copy the code

Sample call

// Serpentine print
printBintryTree(binaryTree.root); // F B G I D A C E H
// Breadth traversal
console.log(BFS(binaryTree.root)); // ['F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'H']
// Deep traversal
console.log(preorderDFS(binaryTree.root)); // ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']
console.log(inorderDFS(binaryTree.root)); // ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
console.log(postorderDFS(binaryTree.root)); // ['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'];
Copy the code