This is the seventh day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.

preface

“The colours of August are of gold, bright and precious; The colours of August are brewed with sunshine, fragrant and brilliant.”

In the future, I wish you to adjust yourself to the best state, slowly work hard, slowly get better

define

A binary tree is an ordered tree whose node degree is less than 2. It is one of the simplest and most important trees.

The recursion of binary tree is defined as: binary tree is an empty tree, or a non-empty tree composed of a root node and two non-intersecting left and right subtrees called roots respectively; The left subtree and the right subtree are both binary trees

Binary tree as a very basic but very important data structure, in some scenarios or more important. So the importance of binary trees is self-evident.

Here’s an example:

var binaryTree = {
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4
    }
  },
  right: {
    value: 3,
    left: {
      value: 5,
      left: {
        value: 7
      },
      right: {
        value: 8
      }
    },
    right: {
      value: 6
    }
  }
}
Copy the code

The recursive traversal

The first sequence traversal

Access root – > traverse the left subtree – > traverse the right subtree;

var preListRec = []; Var preOrderRec = function(node) {if (node) {preListRec. Push (node.value); PreOrderRec (node.left); PreOrderRec (node.right); // preOrderRec(node.right); }} preOrderRec(tree); console.log(preListRec)Copy the code

In the sequence traversal

Traverse the left subtree – > access root – > traverse the right subtree;

var inListRec = []; Var inOrderRec = function(node) {if (node) {inOrderRec(node.left); InListRec. Push (node.value); InOrderRec (node.right); }} inOrderRec(tree); console.log(inListRec);Copy the code

After the sequence traversal

Traversing the left subtree – > traversing the right subtree – > access root;

var postListRec = []; Var postOrderRec = function(node) {if (node) {postOrderRec(node.left); // Recursively traverse the left subtree postOrderRec(node.right); PostListRec. Push (node.value); }} postOrderRec(tree); console.log(postListRec);Copy the code

Non-recursive traversal

Breadth first traversal

Breadth-first traversal starts at the first level (root) of the binary tree and starts from the top to the bottom. Nodes are accessed from left to right in the same layer

Implementation principle:

Using arrays to simulate queues, you first queue the root node. When the queue is not empty, execute the loop: take out a node of the queue, if the node has a left subtree, then the left subtree of the node is stored in the queue; If the node has a right subtree, the right subtree of the node is queued

var breadthList = []; Var breadthTraversal = function(node) {if (node) {var que = [node]; Var que = []; que.push(node); while (que.length ! == 0) {// Check whether the queue is empty. Node = que. Shift (); String breadthList.push(node.value); string breadthList.push(node.value); If (node.left) que. Push (node.left); If (node.right) que. Push (node.right); // Put the right subtree in the queue if it exists}}} breadthTraversal(tree); console.log(breadthList);Copy the code

conclusion

If this post helped you, feel free to like 👍 and follow ⭐️

If there are any mistakes in this article, please correct them in the comments section 🙏🙏.