Using JS to implement binary tree traversal algorithm example code

Preface

In computer science, tree is a widely used abstract data type (ADT), which is a type of non-linear data structure. Trees are widely used in the computer field, especially binary trees.

Tree related concepts:

• Node: Each element is called a node
• Tree root: root node
• Degree: The number of child nodes a node contains is called the degree of the node.
• Leaf node: a node with degree 0

1. Binary Tree

Concept: A tree in which each node contains at most two subtrees is called a binary tree.

1.1. Traversing a binary tree

There are two kinds of traversal for binary trees: depth traversal and breadth traversal. There are three traversal methods for depth traversal: pre-order, in-order and post-order. Breadth traversal is a level traversal, traversing layer by layer in order.

The main ideas of the four traversals are:

• Preorder: visit the root first, then visit the left subtree, and finally visit the right subtree, DLR.
• In-order: visit the left subtree first, then the root, and finally the right subtree, LDR.
• Postorder: visit the left subtree first, then the right subtree, and finally the root, LRD.
• Breadth: Traverse layer by layer in order.

For example, a+b*(cd)-e/f, the expression is represented by a binary tree:

Traverse them separately:

• Preamble: -+a*b-cd/ef
• In order: a+b*cde/f
• Postscript: abcd-*+ef/-
• Breadth: -+/a*efb-cd

1.2. Use js to represent binary tree

We use js objects to represent binary trees. The object has three properties: left, value, and right, which are the left subtree, value, and right subtree respectively. The above example a+b*(cd)-e/f can be represented like this using js.

var tree = {
    value: '-',
    left: {
        value: '+',
        left: {
            value: 'a'
        },
        right:
            value: '*',
            left: {
                value: 'b'
            },
            right:
                value: '-',
                left: {
                    value: 'c'
                },
                right:
                    value: 'd'
                }
            }
        }
    },
    right:
        value: '/',
        left: {
            value: 'e'
        },
        right:
            value: 'd'
        }
    }
}

1.3 Pre-order traversal algorithm

Preface: There are two methods. The first one is very simple, which is to use recursion directly.

function preOrder(treeNode) {
  if(treeNode) {
    console.log(treeNode.value); // Printing out means visiting this node preOrder(treeNode.left);
    preOrder(treeNode.right);
  }
}

The algorithm is very simple. First, traverse the root node, then recursively traverse the left subtree. After traversing the left subtree, recursively traverse the right subtree.

The second non-recursive traversal

function preOrder(treeNode) {
  if(treeNode) {
    var stack = [treeNode]; //Push the binary tree into the stack while (stack.length !== 0) {
      treeNode = stack.pop(); // Get the top of the stack document.getElementById('text').appendChild(document.createTextNode(treeNode.value)); // Visit the node if(treeNode.right) stack.push(treeNode.right); // Push the right subtree into the stack if(treeNode.left) stack.push(treeNode.left); // Push the left subtree into the stack }
  }
}

The second is to use the idea of ​​a stack. As we all know, a stack is a first-in, last-out data structure. We first push the root node into the stack, then take the top of the stack, visit the root node, and push the right and left subtrees into the stack respectively. The right side must be pushed into the stack first because we have to visit from the left first, so the right subtree is pushed into the stack first, and then we loop to take out the stack until the stack is empty.

1.4. In-order traversal algorithm

In-order recursive algorithm:

function InOrder(treeNode) {
    if(treeNode) {
        InOrder(treeNode.left);
        document.getElementById('text').appendChild(document.createTextNode(treeNode.value));
        InOrder(treeNode.right);
    }
}

The same idea as the pre-order recursive algorithm, but the location of the visited nodes is different

Second type:

function InOrder(node) {
  if(node) {
    var stack = []; // Create an empty stack // If the stack is not empty or the node is not empty, loop through while (stack.length !== 0 || node) { 
      if (node) { //If the node is not empty stack.push(node); //Push the node into the stack node = node.left; //Use the left subtree as the current node } else { //The left subtree is empty, that is, there is no left subtree node = stack.pop(); //Take the node out document.getElementById('text').appendChild(document.createTextNode(node.value));
          node = node.right; //Use the right node as the current node}
    }
  }
}

The idea of ​​the non-recursive in-order algorithm is to push the current node into the stack, then traverse the left subtree, if the left subtree exists, keep pushing it into the stack until the left subtree is empty, visit the previous node, and then push the right subtree into the stack.

1.5. Post-order traversal algorithm

The first one: recursive traversal algorithm

function postOrder(node) {
    if (node) { //Judge whether the binary tree is empty postOrder(node.left); //Recursively traverse the left subtree postOrder(node.right); //Recursively traverse the right subtree document.getElementById('text').appendChild(document.createTextNode(node.value));
    }
}

Second: non-recursive traversal algorithm

function postOrder(node) {
    if (node) { //Judge whether the binary tree is emptyvar stack = [node]; //Push the binary tree into the stackvar tmp = null; //Define cache variableswhile (stack.length !== 0) { //If the stack is not empty, loop throughtmp = stack[stack.length - 1]; //Save the top value of the stack in tmpif (tmp.left && node !== tmp.left && node !== tmp.right) { //If there is a left subtree, node !== tmp.left && node !== tmp.right is to avoid repeatedly pushing the left and right subtrees into the stackstack.push(tmp.left); //Push the left subtree node into the stack} else if (tmp.right && node !== tmp.right) { //If the node has a right subtreestack.push(tmp.right); //Push the right subtree into the stack} else {
                document.getElementById('text').appendChild(document.createTextNode(stack.pop().value));
                node = tmp;
            }
        }
    }
}

A tmp variable is used here to record the last popped and pushed nodes. The idea is to push the root node and the left tree into the stack first, then take out the left tree, push the right tree, take it out, and finally take the root node.

The following is the process of traversing the previous binary tree using this algorithm

stack tmp node print initial: - null -
Round 1: -+ - -
Round 2: -+a + -
Round 3: -+ a a a
Round 4: -+* + a
Round 5: -+*b * a
Round 6: -+* b b b
Round 7: -+*- * b
Round 8: -+*-c - b
Round 9: -+*- c c c
Round 10: -+*-d - c
Round 11: -+*- d d d
Round 12: -+* - - -
Round 13: -+ * * *
Round 14: - + + +
Round 15: -/-+
Round 16: -/e / +
Round 17: -/ e e e
Round 18: -/f / e
Round 19: -/ f f f
Round 20: - / / /
Round 21: - - -

Result: abcd-*+ef/-

1.6. Layer-by-layer traversal algorithm

function breadthTraversal(node) {
    if (node) { //Judge whether the binary tree is emptyvar que = [node]; //Put the binary tree into the queuewhile (que.length !== 0) { //Judge whether the queue is emptynode = que.shift(); //Take a node from the queuedocument.getElementById('text').appendChild(document.createTextNode(node.value)); //Save the value of the taken node to the arrayif (node.left) que.push(node.left); //If the left subtree exists, put the left subtree into the queueif (node.right) que.push(node.right); //If the right subtree exists, put the right subtree into the queue}
    }
}

Use an array to simulate a queue and first put the root node into the queue. When the queue is not empty, execute the loop: take out a node from the queue, if the node has a left subtree, store the left subtree of the node in the queue; if the node has a right subtree, store the right subtree of the node in the queue.

2. Algorithm Questions

1.1. Maximum depth of a binary tree

Given a binary tree, find its maximum depth.

The depth of a binary tree is the number of nodes on the longest path from the root node to the farthest leaf node.

For example, the following binary tree returns a depth of 3.

3
/ \
9 20
/ \
15 7

const tree = {
value: 3,
left: {
value: 9
},
right:
value: 20,
left: { value: 15 },
right: { value: 9 }
}
}

Recursive algorithm: The idea of ​​the recursive algorithm is very simple. First, get the deepest layer of the left subtree, then get the deepest layer of the right subtree, and the maximum value of them is the depth of the tree.

var maxDepth = function(root) {
  if (!root) {
    return 0;
  }
  const leftDeep = maxDepth(root.left) + 1;
  const rightDeep = maxDepth(root.right) + 1;
  return Math.max(leftDeep, rightDeep);
};
/*
maxDepth(root) = maxDepth(root.left) + 1 = 2
maxDepth(root.left) = maxDepth(root.left.left) + 1 = 1
maxDepth(root.left.left) = 0;

maxDepth(root) = maxDepth(root.right) + 1 = 3
maxDepth(root.right) = maxDepth(root.right.right) + 1 = 2
maxDepth(root.right.right) = maxDepth(root.right.right.right) + 1 = 1
maxDepth(root.right.right.right) = 0
*/

1.2. All paths of a binary tree

Given a binary tree, return all paths from the root node to a leaf node.

for example:

3
/ \
9 20
/ \
15 7

Returns: ['3->9', '3->20->15', '3->20->7']

Using recursive method:

var binaryTreePaths = function(root) {
  if (!root) return [];
  const res = [];
  function dfs(curNode, curPath) {
    if(!curNode.left && !curNode.right) {
      res.push(curPath);
    }
    if(curNode.left) {
      dfs(curNode.left, `${curPath}->${curNode.left.value}`)
    }
    if(curNode.right) {
      dfs(curNode.right, `${curPath}->${curNode.right.value}`)
    }
  }
  dfs(root, `${root.value}`);
  return res;
};

Summarize

This is the end of this article about using JS to implement a binary tree traversal algorithm. For more relevant JS binary tree traversal algorithm content, please search for previous articles on 123WORDPRESS.COM or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!