Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money

Hello everyone, I am quick-frozen fish 🐟, a front end of water system 💦, like colorful whistle 💐, continuous sand sculpture 🌲, I am a good brother of the next door Cold grass Whale, I just started to write an article. If you like my article, you can follow ➕ to like it, inject energy into me, and grow with me

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

The quality of writing instructions will directly affect the performance of the program, and instructions are composed of data structure and algorithm, so the design of data structure and algorithm basically determines the quality of the final program.

In addition, when reading the source code, the lack of understanding of algorithms and data structures makes it difficult to understand why the author wrote the way he did.

In today’s environment, algorithms have become an indispensable skill for front-end engineers. If we want to move beyond being application engineers writing business code, we need to understand algorithms and data structures.

Of course, learning is also focused, as the front end we do not need to fully grasp the algorithm like back-end development, some of the more partial, not practical type and solution method, as long as a little understanding.

What is a binary tree? 👋

  • Each node in the tree can have a maximum of two child nodes.

  • Object is commonly used to simulate binary trees in JS.

    const binaryTree={
  val:1.left: {cal:2.left:null.right:null
  },
  right: {val:3.left:nnull,
    right:null}}Copy the code

Binary tree sequential traversal algorithm formula

  • accessThe rootnode
  • For the rootOn the leftSubtrees are traversed in order
  • For the rootrightSubtrees are traversed in order

Binary tree sequential traversal source 🦀

Here we use the stack data structure to simulate our recursive operation, the main need is that the stack is last in first out, so pay attention to the order when pushing the stack

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,}}};const preorder=(root) = >{
if(! root){return}
  const stack=[root];
  while(stack.length){
    const n=stack.pop();
    console.log(n.val);
    if(n.right)stack.push(n.right)
    if(n.left)stack.push(n.left)  
  }
}
preorder(bt)//1 2 4 5 3 6 7
Copy the code

Formula for sequential traversal in binary trees

  • For the rootOn the leftSubtrees are traversed in order
  • accessThe rootnode
  • For the rootrightSubtrees are traversed in order

Binary tree sequence traversal source 🦀

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,}}};const inorder=(root) = >{
    if(! root){return; }const stack=[];
    let p=root;
    while(stack.length||p){
        while(p){
            stack.push(p)
            p=p.left
        }
        const n=stack.pop();
        console.log(n.val);
        p=n.right
    }
}

inorder(bt)//4 2 5 1 6 3 7
Copy the code

Binary tree backorder traversal calculation formula

  • For the rootOn the leftSubtrees are traversed in order
  • For the rootrightSubtrees are traversed in order
  • accessThe rootnode

Binary tree after sequence traversal source 🦀

The roots are traversed from right to left, and then printed in reverse order

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,}}};const postorder = (root) = > {
    if(! root) {return; }
    const outputStack = [];
    const stack = [root];
    while (stack.length) {
        const n = stack.pop();
        outputStack.push(n);
        if (n.left) stack.push(n.left);
        if (n.right) stack.push(n.right);
    }
    while(outputStack.length){
        const n = outputStack.pop();
        console.log(n.val); }}; postorder(bt)//4
Copy the code

Conclusion 🌞

So fish fish LeetCode algorithm article after the first sequence of binary tree traversal (non-recursive version) will be over, although the front end of algorithm requires no backend is high, but the algorithm is based programming, program = data structure ➕ algorithm, there is no shortcut to this thing, so the algorithm can only write more practice, more summary, the purpose of the article is very simple, It is to urge myself to complete algorithm practice and summarize and output, it is not important whether the dish is dish or not, but I love 🔥, I like that everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.