This is the fifth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

preface

  • La la la, du and you meet again, today du and you are going to talk about the topic is binary tree three traversal ways in the code of the similarities and differences.
  • Objects involved: binary tree
  • Contents involved:(1)The former sequence traversal(2)In the sequence traversal(3)After the sequence traversal(4) How to visually understand traversal mode
  • Code involvedRecursive code and iterative code
  • Focus on: Find a framework that works for all three traversal methods

The body of the

  • First, let’s write down the following three traversal results of the binary tree:

  • Sequential traversal: [1,2,4,5,3,6]

  • Middle order traversal: [4,2,5,1,3,6]

  • Post-order traversal: [4,5,2,6,3,1]

  • Note: speak a few very image of the example, you can quickly hand out these three traversal order (here is an example of a very nice blog, feel very suitable for small white, the original link small du on the bottom, need readers can go to see, this blogger than small du much more powerful)

  • 1. Preorder traversal

    • Forewalk, you can think of it as starting at the root, going counterclockwise, going through all the nodes
    • Preemptive traversal of recursive code 
      var preorderTraversal = function(root) { let res = []; // Const traversal = (root01)=>{// If the current node is null, if(root01 == null) return; Res.push (root01.val); // This path ends and needs to be retraced. Traversal (root01.left); Traversal of the left child (root01.right); } traversal(root); return res; // Return value};Copy the code
    • Small du explain it a little bit, looking at the code, we know that as long as meet elements, will print it (this is stored), and then entered into his left subtree, the recursive call continuously, such as the left subtree is null, the recursive start back up one layer, each layer returns, and then entered into his right subtree, into the right subtree, We enter the left subtree of the right subtree first, and so on. When everything is found, the level of the recursive function is reduced to 1. Here we verify that the traversal order above is correct,butThis is just an idea. You can’t assume that the traversal order is necessarily thisIteration codeIn the,There are no steps 9 or 10.

  • 2. Middle order traversal

    • Middle order traversal, you can think of it this way, projecting all the nodes vertically at the bottom,For example,, we set up a two-dimensional coordinate system, the horizontal axis is x, the vertical axis is y, move the above graph to the coordinate system, the projection on the x axis is the result of the middle order traversal, this should be much faster than one number.
    • Does it make sense to look at the picture? Hey hey hey, learn to go, small du is very hope readers will see one eye, refueling!!
    • In order to traverse recursive code 
      var inorderTraversal = function(root) {
       let res = [];//要返回的数组
       const  traversal = (root01)=>{//es6中的箭头函数
            if(root01 == null) return ;
            traversal(root01.left);
            res.push(root01.val);
            traversal(root01.right);
        }
        traversal(root);
        return res;
 };
Copy the code
    • Middle-order traversal is basically the same as pre-order traversal, except that the printing position is placed in the middle, which is why it is called middle-order traversal.

  • 3. Back-order traversal

    • You can think of this as a bunch of grapes, and we specifyYou can only pick one grape at a time, you can't be greedy, and the rule is to pick grapes from left to right (that is, traverse the left subtree first and then traverse the right subtree). Now look at the grape picking process below, do you feel that the sequence traversal is actually that thing

    • Post-order traversal of recursive code

      var postorderTraversal = function(root) { let res = []; // Const traversal = (root01)=>{if(root01 == null) return; Traversal (root01.left); // Switch traversal(root01.left); Traversal (root01.right); // Traversal (root01.right); // Traverse the right subtree res.push(root01.val); // Left and right subtree traversal is left in the middle! } traversal(root); return res; };Copy the code

    • Now look at the recursive code, you will find that the code of the three of them should be so similar, small du I do not know wrong, happy thinking: that IF I will be a, that the other two not also take pinch le, hey hey hey.

  • 4. Recursive code summary

    • Taken together, we can see that the recursion code of the three is very similar, so it’s no wonder that people only ask once when they ask (the other two are easy to follow).

    • Doodle tells us about the differences between the codes

      • Small du confidently say:(1)The printing position is different, one in the front, one in the middle and one at the end.
      • (2)They recursively call the functions in the same order (please draw this for the reader and draw it yourself, you can not draw it, you can look at the code, except the push position is different).
      • Small du Nannan said: And then nothing.

    • Now come a frame and use it directly in the future!

      var postorderTraversal = function(root) { let res = []; // Const traversal = (root01)=>{if(root01 == null) return; Traversal at @key1 (root01.left); // traversal at @key1 (root01.left); Traversal @key2 traversal(root01.right); Traversal (root)} traversal(root); return res; };Copy the code

    • Preemptive traversal: Write print or store code at @key1

    • Middle-order traversal: Write print or store code at @key2

    • Postorder traversal: Write print or store code at @key3

  • 5. Iteration code summary

    • Sequential traversal:

      var preorderTraversal = function(root) { let res = []; Let stack = []; let stack = []; / / encountered in the process of circulation of node information while (root | | stack. The length) {while (root) {res. Push (root. Val); // Will encounter print, here is the store oh stack.push(root); // The node also needs to remember how to find its right child. root = root.left; } let node = stack.pop(); Root = node.right; } return res; };Copy the code

    • Middle-order traversal:

      var inorderTraversal = function(root) { let res = []; // Let stack = []; / / we are used to store encountered in the process of traverse of elements / / root = = null and stack length = = 0 exit (circulation) while (root | | stack. The length) {while (root) {/ / the current element is cycle stack.push(root); // Push the current element to the stack, not the value, but the entire current element root = root.left; } // This element has no left child, so we should print the element let node = stack.pop(); // Return this element and push res.push(node.val); // Push the value of this element into the stack to be returned root = node.right; } return res; // Iterate over the right child of the element. // Return final result};Copy the code

    • Post-order traversal:

      var postorderTraversal = function(root) { let res = []; // Let stack = []; / / encountered in the process of traverse of element nodes while (root | | stack. The length) {while (root) {res. Unshift (root. Val); // Insert stack.push(root); // Insert stack. root = root.right; } let node = stack.pop(); root = node.left; } return res; };Copy the code

    • The difference between them is small du in the previous several articles have been explained one by one, readers confused welcome to read. Hey hey hey (doodle will put the link at the bottom of the article), now go straight to the frame

      var preorderTraversal = function(root) { let res = []; Let stack = []; let stack = []; / / encountered in the process of circulation of node information while (root | | stack. The length) {while (root) {/ / @ @ key1, key2 place stack. Push (root); // The node also needs to remember how to find its right child. root = root.left; } let node = stack.pop(); @key3 root = node.right; @key3 root = node. } return res; };Copy the code

    • Preemptive traversal: Write print or store code at @key1

    • Middle-order traversal: Write print or store code at @key3

    • Postorder traversal: Write storage code at @key2

      • note:
        • (1). We can’t print directly here, because we areThe node is found backwards
        • (2). Need to change the code,The first placeThe root =root.leftTo the root =root.right
        • (3).In the second placeThe root =node.rightTo the root =node.left

At the end

  • So far, the three traversal methods of binary trees are perfect. Thank you for reading.
  • Article more words, small du will inevitably hand shake (Gnome male -"(Welcome your criticism and correction.
  • It is not easy to create, so Du spent all his time on it this weekend (-wuwuwu......), Sunday night 23:32 to finish, so if readers still feel good, can give duLike, comment, follow a wave of supportLittle du will keep on trying.
  • If the reader wants to let small du to write a certain aspect of the content, welcome to comment, small du will try to do (if really can’t, that small du can only admit mistake).
  • In the end, I wish you all a good read this article, we will see you next time.

Slip slip slip...

The attachment

  • Binary tree forward traversal juejin.cn/post/702968…

  • Sequential traversal in a binary tree

    • The recursive version juejin. Cn/post / 702748…
    • Iterative version juejin. Cn/post / 702774…

  • Binary tree post order traversal juejin.cn/post/702911…

  • The article example reference blog.csdn.net/chinesekobe…