Visualization of depth First Traversal (DFT)

Depth first traversal, brush the question of friends should be very familiar with, difficult is not difficult, but it still takes some effort to understand. There are two ways to realize depth-first traversal: recursion and non-recursion. Here we use the visual Angle to explain the former one: recursive depth-first traversal.

Why do you want to do this in a visual way? Because people are visual animals, if I tell you binary tree or stack, I believe you will have the following graph in your mind:

Instead of the following code:

// binary tree
class Node {
  constructor(value, leftChild, rightChild) {
    this.value = value
    this.leftChild = leftChild
    this.rightChild = rightChild
  }
}

// stack
const stack = new Array()
stack.push(1)
var topItem = stack.pop()
Copy the code

Therefore, human beings are visual animals, and it is often better to explain problems in the way of graphic visualization, which is why I write this paper.

Results show

In order to visually explain the depth-first traversal algorithm, the author wrote a simple web page with the following functions:

• The user can edit the binary tree for deep traversal
• An implementation of the JavaScript version is provided on the web page
• Click on theStart DFTButton, and the user will see what the algorithm usesBinary tree 和 The stackWill be dynamically displayed in the page, you can intuitively see the code during the process of data changes

The page is still being optimized, so let’s see what it looks like so far:

Online demo:

Ssthouse. Making. IO/visual – expl…

It can be seen that the webpage simulates the dynamic change process of binary tree and stack in deep search:

• The node currently traversed in the binary tree becomesred;
• The node pushed into the stack isgray;
• Nodes that pop on the stack becomeredAnd then disappear;

The upper left corner of the page is the binary tree data of the initial traversal. Users can modify the binary tree data and start the visual depth-first traversal process again.

The depth-first traversal implementation version of javascript is at the bottom left of the page for your reference.

Introduction to depth-first traversal

Before visualization, let’s take a quick look at the code that implements depth-first search:

export class Dft {
  constructor(rootNode, stepCallback) {
    this.rootNode = rootNode
    this.stepCallback = stepCallback
  }

  start() {
    if (!this.rootNode || !this.stepCallback) {
      return
    }
    const stack = [this.rootNode]
    while(stack.length ! = =0) {
      const curNode = stack.pop()
      console.log(`current node: ${curNode.value}`)
      curNode.childrenNodes.forEach(element= > {
        stack.push(element)
      })
    }
  }
}

export class Node {
  constructor(value, childrenNodes = []) {
    this.value = value
    this.childrenNodes = childrenNodes
  }
}
Copy the code

It’s not a long code, so let’s go through it step by step.

First we create a stack const stack = [this.rootnode] and put the rootNode on the stack.

Next, a while statement breaks out of the loop if the stack is empty, which means we’ve walked through the entire tree.

In the loop, we pop the node at the top of the stack and print it out to show that we’ve walked through it. We then push all the children of that node onto the stack, which ensures that the next point we traverse will be the children of that node. Repeat the loop, and finally we can see that each node of the binary tree is printed in the order of deep search:

current node: 1
current node: 4
current node: 7
current node: 6
current node: 2
current node: 5
current node: 3
Copy the code

For those of you who are familiar with the stack, you can probably see how this works.

However, for those of you who are not familiar with stack usage and still don’t have an intuitive understanding of how this code works, let’s take a look at how this code works in a more intuitive way.

Visual explanation

First, push the root node onto the stack:

Then we enter the while loop, which pops the top node and pushes its children onto the stack:

As can be seen, depth-first traversal takes advantage of the first-in-last-out feature of the stack, so that for each node, after traversing the node, its child nodes will be traversed next, thus completing depth-first traversal:

The last

In this paper, the visualization of binary tree and stack is the UI component encapsulated by the author himself. Only a simple call can show the data structure in the code in a visual way on the page.

Personally, I think this kind of data structure visualization may be helpful to explain the code, if you also have this requirement, please let me know in the comments below, I can package these UI components for the convenience of people who need to use.

The source code is here. Welcome to Fork & Star

Github.com/ssthouse/vi…

To continue to understand the D3. Js | | data visualization?

Here is my D3.js, Github address for data visualization, welcome to Start & fork :tada:

D3-blog

If you like it, check out the link below:)

Making the home page

Zhihu column

The Denver nuggets

Welcome to follow my official account: