Binomial tree traversal refers to the non-repeated access to all nodes in the binomial tree, mainly refers to the non-empty binomial tree, for the empty binomial tree is the end of the return.

The traversal of a binary tree is divided into

  • Depth first traversal

  • Preorder traversal: root node -> left subtree -> right subtree (left and right root), some are called: preorder traversal

  • In order traversal: left subtree -> root node -> right subtree (left root right)

  • After order traversal: left subtree -> right subtree -> root node (left and right roots)

  • Breadth first traversal

  • Hierarchy traversal:

Binary tree – priority traversal of depth – Diagram

Depth first, before, in, after traversal order, is to combine [root left and right], move the root position, root left and right, left and right root, but even though I can write the code, I still don’t understand the relationship between the root left and right and traversal, where is the thread head, especially in the middle order traversal left and right root,

The illustration by blogger YuXi_0520 is probably the most understandable I’ve seen. Here is a copy of the picture

Sequential traversal (DLR)

You can imagine a first order traversal, where the little guy starts at the root of the tree and goes around the periphery of the tree, and the order that he goes through the nodes is the order that the first order traversal takes place

Let’s take a look at the animation, run with the little guy twice, and remember, run around the perimeter

Preorder traversal result: ABDHIEJCFKG

Binary tree preorder traversal – JS code implementation

Recursive implementation – binary tree first order traversal

Root-left-right recursion

Check whether the root node is null. If it is null, return NULL. Otherwise, take the value of the node, and then take the value of the left node and the right node

/** * @description =>1. Access the root node. 2. Access the left subtree. */ preOrderTraverse (node = this.tree) {// Traverse (node = this.tree) {let backs = [] // recurse,  function tempFunction (node) { if (node.data ! Node.leftchild && tempFunction(node.leftChild) == null) {// select the root node.push (node.data) from node.leftChild Node.rightchild && tempFunction(node.rightChild)}} tempFunction(node.rightChild) return back}Copy the code
Non-recursive – binary tree first order traversal

Take the value of the node, and then stack the left and right nodes

preOrderTraverse2 (node = this.tree) { let backs = [] if (! {return back} let queue = [node] while (queue.length) {// fetch the last node, Let root = queue.pop() backs.push(root.data) RightChild && queue. Push (root.rightChild) root.leftChild && queue. Push (root.leftChild)} return backs}Copy the code
Non-recursive – binary tree first order traversal

The following code should be easier to understand

If there’s a left node on the node, it’s valued, and it’s stored on the stack until no left node is a leaf, and then it’s on the right

preOrderTraverse3 (node = this.tree) { let backs = [] if (! node) { return backs } let currentNode = node let queue = [node] while (queue.length) { if(currentNode){ backs.push(currentNode.data) queue.push(currentNode) currentNode=currentNode.leftChild }else { currentNode = queue.pop()  currentNode = currentNode.rightChild } } return backs }Copy the code

In order traversal (LDR)

You can think of the order traversal as, you know, just projecting the tree right and left

Now let’s look at the animation of the projection process, which is actually written down in left and right order

Sequence traversal result: HDIBEJAFKCG

Binary tree order traversal -JavaScript code implementation

Recursive implementation – binary tree in order traversal
/** * @description traverse => left/right root * @param node {node} Traverse (node = this.tree) {// inOrderTraverse (node = this.tree) {// Array store traverse values let backs = Function tempFunction (node) {if (node.data! LeftChild && tempFunction(Node.leftChild) // Back. Push (node.data) // Back. Push (node.data) // Back. Node.rightchild && tempFunction(node.rightChild)}} tempFunction(node.rightChild) return back}Copy the code
Non-recursive implementation – order traversal in a binary tree
inOrderTraverse2(node){ let backs = [] if(! node){ return backs } let stack = [node] let currentNode = node while(stack.length){ if(currentNode){ stack.push(currentNode) currentNode = currentNode.leftChild }else { currentNode = stack.pop() backs.push(currentNode.data) currentNode = currentNode.rightChild } } }Copy the code

Post-order traversal (LRD)

Sequential traversal is like cutting grapes. We want to cut a bunch of grapes one by one (from left to right, cut the bottom leaves).

It is a circle around the outside of the tree. If you find a grape that can be cut with a pair of scissors (it must be a grape), cut it off, and the composition is the sequential traversal.

The sequence is the same as the previous sequence, but the following sequence is: recursion: first take the left leaf (if not, skip), then take the right leaf

The result of the sequential traversal is HIDJEBKFGCA

Binary tree subsequent traversal – implemented in JavaScript code

Recursive implementation – the binary tree is traversed later
/** * @description => left root right * 1. Access the left subtree. (First access the left subtree of the left subtree, then access the right subtree of the left subtree) * 2. Access the right subtree. (First access the left subtree of the right subtree, then access the right subtree of the right subtree) * 3. */ postOrderTraverse (node) {// Array store the number of traversals let backs = [] // recursion,  function tempFunction (node) { if (node.data ! == null) {node.leftChild && tempFunction(node.leftChild); RightChild = node.rightChild = node.rightChild = node.rightChild = node.rightChild = node.rightChild = node.rightChild = node.rightChild backs }Copy the code

Non-recursive implementation – binary tree traversal

postOrderTraverse2 (node){ let backs = [] if(! node){ return backs } let stack = [node] while(stack.length){ let currentNode = stack.pop() backs.push(currentNode.data)  currentNode.leftChild&&stack.push(currentNode.leftChild) currentNode.rightChild&&stack.push(currentNode.rightChild) } return backs }Copy the code
Non-recursive implementation of 2 – binary tree subsequent traversal
postOrderTraverse2 (node) { let backs = [] if (! node) { return backs } let stack = [] let currentNode = node while (stack.length||currentNode) { if (currentNode) { stack.push(currentNode) backs .unshift(currentNode.data) currentNode = currentNode.rightChild } else { let temp = stack.pop() currentNode = temp.leftChild } } return backs }Copy the code
Non-recursive implementation of 3 – binary tree subsequent traversal
postOrderTraverse3 (node) { let backs = [] if (! node) { return backs } let stack = [node] while (stack.length) { let currentNode = stack.pop() backs.unshift(currentNode.data) currentNode.leftChild && stack.push(currentNode.leftChild) currentNode.rightChild && stack.push(currentNode.rightChild) } return backs }Copy the code
Non-recursive implementation of 4 – binary tree subsequent traversal
postOrderTraverse4 (node) { let backs = [] if (! node) { return backs } let stack = [node] let currentNode = node let visitedNode = null while (stack.length) { if (currentNode) { stack.push(currentNode) currentNode = currentNode.leftChild } else { currentNode = stack[stack.length - 1] if (currentNode.rightChild && currentNode.rightChild ! == visitedNode) { currentNode = currentNode.rightChild } else { backs.push(currentNode.data) visitedNode = currentNode stack.pop() currentNode = null } } } return backs }Copy the code

Binary tree – breadth first traversal – Diagram

This is just sequential traversal

Sequence traversal

Sequence traversal is too easy, just write it down from left to right, layer by layer.

Sequence traversal result: ABCDEFGHIJK

Binary sequence traversal – Implemented in JavaScript code

/** * @description traverse => left/right root * @param node {node} Traverse (node = this.tree) {// inOrderTraverse (node = this.tree) {// Array store traverse values let backs = Function tempFunction (node) {if (node.data! LeftChild && tempFunction(Node.leftChild) // Back. Push (node.data) // Back. Push (node.data) // Back. Node.rightchild && tempFunction(node.rightChild)}} tempFunction(node.rightChild) return back}Copy the code

I don’t know if I can write preorder, middle order, posterior order, and hierarchical order with my eyes closed, but this is just a kind of image thinking for you to understand. In order to implement it in code, we need to understand the preorder, middle order and posterior traversal.

Really understand the three kinds of traversal

Remember the order we ran when we went through first and last? Run again in this order, which is to run a full circle around the outside of the tree.

So let’s understand what it really means to run around the perimeter: as you go through all the nodes, you go first to the left child, then to the right child.

Take a look. What do you find?

Did you notice that every node except the root node and the null node has three arrows pointing to it?

  • One is pointing to it from its parent,

  • One is from its left child pointing to it

  • One is pointing at it from its right child.

A node has three arrows pointing at it, which means each node has been passed through three times.

  • Once from its parent,

  • Once from its left child,

  • Once on the way back from its right child.

In fact, when we use a recursive algorithm to walk through a binary tree, whether it’s in order or in order, the program runs through all the nodes in that order.

The only difference between preorder and postorder is which of the three times that the node is accessed (output or print or do something else). It is a bit like Dayu who passed through his house three times when he was controlling the flood.

  • A preorder traversal is, as the name suggests, the first time you go through the node, you access it. That’s when the arrow comes from the parent node, it accesses it.

  • It’s the same as the name, which is the second time I go through this node, I call it. That’s when the arrow that came back from the left child visited it.

  • Post-order traversal, which means I’m accessing this node the third time I go through it. That’s when the arrow that came back from the right child visited it.

How about that? Does that make sense?

In fact, whether it is preorder or preorder, when running in the program is in the same order, each node through three times, the number of times to access the node, is called what order traversal.

With this concept in mind, it’s easy to look at the implementation code, which I’ll post and explain in the next blog post.

If the recursive divide and conquer is used to understand the relationship between the front, middle, and back traversal and the left and right root, it is to deal with the order of [front, middle, and back] corresponding to [left and right root, left and right root] for each child node at the lowest level according to the running diagram.

Binary tree before order, in order, after order traversal to find each other

Known binomial tree breadth first traversal – sequence traversal group, is can completely restore the binomial tree structure, but

Given a sort array of binary tree preorder, middle order and post order, it is impossible to find the structure of binary tree. However, knowing the preorder, middle order, and the middle order in the postorder and the preorder or postordinal number group can also restore binary tree, why can deduce the data structure of binary tree.

The preorder root node is first, and the subsequent root node is last. If the preorder or subsequent is known, the elements on both sides of the root node in the middle order are distributed as the left node and the right node elements of the root node. The specific operations are as follows:

Known before order, order traversal, after order traversal

  • Preorder traversal =ABGDECFH

  • In order traversal =GBEDAFCH

Steps to build a binary tree:

  1. According to the characteristics of preorder traversal, we know that the root node root is A;

  2. Order traversal of GBEDAFCH in observation. The left GBED of root node A must be the left subtree of root, and the right FCH must be the right subtree of root. At the same time, this is also the sequence of the left subtree and the right subtree;

  3. After we preorder traversal through the root node, we then preorder traversal through the left subtree, notice, preorder traversal, what does that mean? In the second step, we already know that the left subtree is BGDE (preorder traversal sequence). Therefore, we can get that the root of the left subtree is B, so in this step, we can get that the root of the left subtree is B;

  4. From the sequence of nodes traversed in step 2, find B, and find that there is only one G to the left of B, which means that the left subtree of B has only one leaf node. What about the right of B? We get that the right subtree of B has ED, and then if we look at the sequence that was preordered, we find that D comes before, that is, D was preordered, and then we get that E is the left subtree of D, with only one leaf. At this point, we can get the root and left subtree structure of the tree, as shown in Figure 1

  5. Then look right subtree, at the time of step 2 already know right subtree is FCH this three nodes, then look at the preorder traversal sequence, the first is C, then C is right subtrees of root node, look in the right subtree of sequence traversal for FCH, so F and H, respectively, is it the left child of tree and right subtree, therefore, the structure of the right subtree came out, the following figure 2

Known in order, after order traversal, before order traversal

  • In order traversal: GBEDAFCH

  • Post-order traversal: GEDBFHCA

Similarly, the steps are similar to those above. We need to find out the root node first. By the characteristics of the sequential traversal, the root node root is at the end, so the root node is A. Then follow the steps above to recursively solve the left and right subtrees.

Known before order, order after traversal, in order traversal

Given the preorder, middle order or middle order and posterior order can uniquely determine a binary tree, but given the preorder and posterior order can not uniquely determine a binary tree, the solution is not unique.

For detailed code related to the algorithm, see github.com/zhoulujun/a…

Reference article:

Understand the three kinds of binary tree traversal – preorder, middle order, postorder + sequence (easy to understand) blog.csdn.net/weixin_4403…

Js – binary tree data structure (binary heap) segmentfault.com/a/119000001… (Recommended reading – Understanding heapsort – heapize operations)

Binary tree fore-order, in order, after order traversal method blog.csdn.net/qq_34154570…

JavaScript binary tree traversal features: zhuanlan.zhihu.com/p/27307626 algorithm description and implementation

Js-binary tree algorithm implementation and traversal (update…) www.cnblogs.com/padding1015…

Binary tree traversal (before the order, in sequence, after the order, known before in order to in after sequence after sequence, known for former sequence) www.cnblogs.com/lanhaicode/…

Interview BAT gets killed by binary tree? 20 questions to help you win zhuanlan.zhihu.com/p/88361872 binary tree algorithm

Reprint the home station article “say thoroughly learn bad binary tree (3) : illustrations of the binary tree traversal algorithm steps and JS code”, please indicate the source: www.zhoulujun.cn/html/theory…