Ps: This part of the video can be seen in B zhan and Zhihu

1, the introduction

2. Depth-first traversal – DFS

  • So how do we do depth-first traversal?

  • The above code will try to implement
Var tree = {val: 'a', children: [{val: 'b', children: []}, {val: 'd', children: []}, {val: 'e', children: [], } ], }, { val: 'c', children: [{ val: 'f', children: [] }, { val: 'g', children: Var DFS = function (root) {console.log(root.val); ForEach ((child) => {// DFS (child) // DFS (child) // DFS (child) // DFS (child) // DFS (child) // Root.children. ForEach (DFS)} var test = DFS (tree)Copy the code
  • The traversal results are predictable

3. Breadth First traversal, short for BFS

  • How do I do this?

  • Note that the tree here is the tree above
Var tree = {val: 'a', children: [{val: 'b', children: []}, {val: 'd', children: []}, {val: 'e', children: [], } ], }, { val: 'c', children: [{ val: 'f', children: [] }, { val: 'g', children: Var BFS = function (root) {if(! Root) {return 0} // 1, create queue const q = [root] while (q.length) {// 2, create queue const q = [root] while (q.length) {// 2, create queue const n = q.hift () console.log(n.val) // ForEach ((child) => {q.pool. forEach((child) => {q.pool. forEach((child) => {q.pool. forEach((child) => {q.pool. pool. forEach((child) => {q.pool. pool. forEach((child) => {q.pool. pool. q.push(n.right) } } // test var test = bfs(tree)Copy the code
  • The results are predictable, and predictability is a good trend

4. Binary tree

5. Binary tree preordering (preordering) traversal

  • This part is so important that it’s easy to show separately

  • Without further ado, let me show you the code

  • Don’t worry let’s just build a binary tree so that we can show you all three ways of traversing

  • (I really cut wood and sharpen knives)

  • Plant (create) a binary tree create a file binary tree.js

const bt = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null,
    },
    right: {
      val: 5,
      left: null,
      right: null,
    },
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: {
      val: 7,
      left: null,
      right: null,
    },
  },
};

// module.exports = bt;

Copy the code
  • This is a very simple model but let me draw it just so you can see it

  • Use it and implement a sequential traversal
<! -- Introduce the new binary tree because this is an HTML file --> <! Const bt = require('./ binary tree.js ') --> <script SRC ="./3" Js "></script> <script> var pre = function (root) {return if (! root) { return; } console.log(root.val) pre(root.left) pre(root.right)} var test = pre(bt) </script>Copy the code
  • The results were very nice as expected

5. Order traversal in binary tree

  • I’m sure you’re not quite up to it so let’s look at middle order traversal

  • This process will be obvious when the code is demonstrated
<! -- Introduce the new binary tree because this is an HTML file --> <! Const bt = require('./ binary tree.js ') --> <script SRC ="./3" </script> <script> var ino = function (root) {if (! root) { return } ino(root.left) console.log(root.val) ino(root.right) } //test var test = ino(bt) </script>Copy the code
  • The results were predictable

  • That’s good. So at this point you’ve learned the way forward and middle traversal

6, binary tree after order traversal

  • So without further ado let’s go to the code and show you
<! -- Introduce the new binary tree because this is an HTML file --> <! Const bt = require('./ binary tree.js ') --> <script SRC ="./3" </script> <script> var bed = function (root) {if (! root) { return } bed(root.left) bed(root.right) console.log(root.val) } // test var test = bed(bt) </script>Copy the code
  • The expected outcome is well under our control

  • It’s time to go for a spin.

7. Sequential traversal of non-recursive versions using stacks

  • The title also says the non-recursive versionInterviewing is especially important to learn
  • How does the code show how to solve the problem?
<! -- Introduce the new binary tree because this is an HTML file --> <! Const bt = require('./ binary tree.js ') --> <script SRC ="./3" Js "></script> <script> /* var pre = function (root) {// var pre = function (root) {return if (! root) { return; } console.log(root.val) pre(root.left) pre(root.right)} */ // var pre = function (root) {if (! root) { return; } var stack = [root] while (stack.length) {var n = stack.pop() console.log(n.val) // Var test = pre(bt); var test = pre(bt); var test = pre(bt); </script>Copy the code
  • Sequential traversal is the equivalent of reading from front to back and the results are predictable

8. Mid-order traversal of non-recursive versions using stacks

  • Do you remember the middle order traversal?
  • If you don’t remember, just look up
<! -- Introduce the new binary tree because this is an HTML file --> <! Const bt = require('./ binary tree.js ') --> <script SRC ="./3" /* var ino = function (root) {if (! Root) {return} ino(root.left) console.log(root.val) ino(root.right)} */ // {return} / / root) the new stack const stack = [] / / var p = new pointer root while (stack. The length | | p) {while (p) {/ / left nodes to be included in the stack Stack.push (p) p = p. lift} // Access the root node const n = stack.pop() console.log(n.val) // Put the right node on the stack p = n.light}} //test var test =  ino(bt) </script>Copy the code

9. Post-order traversal of non-recursive versions using stacks

  • One trick that we found was that the subsequent iteration of the traversal recursion looked something like thisLeft -- "right --" root
Var bed = function (root) {if (! root) { return } bed(root.left) bed(root.right) console.log(root.val) }Copy the code
  • The version of the sequential traversal looks like thisRoot -- "left --" right
Var pre = function (root) {return if (! root) { return; } console.log(root.val) pre(root.left) pre(root.right) }Copy the code
  • The trick is toReverse the post-traversal and reuse the pre-traversal code
<! -- Introduce the new binary tree because this is an HTML file --> <! Const bt = require('./ binary tree.js ') --> <script SRC ="./3" Var bed = function (root) {// if (! Root) {// return //} // bed(root.left) // bed(root.right) // console.log(root.val) //} // non-recursive var bed = function (root) { if (! Root) {return} // Create two new stacks const stack = [root] const outputStack = [] while (stack.length) {// Access the root node const n = Stack.pop () // the root node is placed in the outputStack outputstack.push (n) // the left node is pushed and the right node is pushed. While (outputstack.length) {var n = outputstack.pop () console.log(n.val)}} // test var  test = bed(bt) </script>Copy the code

10 and summary

  • The first sequence traversalRoot -- "left --" rightNotice that the roots are left to right in a non-recursive stack
  • In the sequence traversalLeft -- "root --" right
  • After the sequence traversalLeft -- "right --" rootNote the use of sequential traversal multiplexing

  • You can have a cappuccino with the author here. Welcome