The introduction

Different with before we introduce linear structure, today we introduce a nonlinear structure: tree, the contents of the tree is more, including BST tree and AVL tree, Trie tree, this part will be released in succession in the next few chapters, this chapter will introduce the basis of the tree and binary tree will content, before starting this section, please think about the following contents:

  • What is a tree?
  • How do you calculate the height of a tree?
  • What is a binary tree?
  • What is a balanced binary tree?
  • How do I represent a binary tree in code?
  • What is the pre-order, middle-order, post-order traversal of a binary tree? How to do that?
  • Can nan be realized by recursion and iteration?

Enter the content of this section 👇

A, trees,

Unlike the linear structure we introduced above, a tree is a nonlinear structure.

Graph:

It follows:

  • There is only one root node, and no node is an empty tree
  • In addition to the root node, each node has and has only one parent node
  • No closed loop can be formed between nodes

This is a tree!

A tree has several concepts:

  • Nodes with the same parent are called siblings
  • Depth of node: The number of edges experienced from the root node to the node
  • Height of node: the longest path from node to leaf node
  • Tree height: The height of the root node

B, C, and D are called brother nodes. The height of node B is 2, the depth of node B is 1, and the height of the tree is 3

highly

The height of the tree is calculated by:

Each node value in the following figure represents the height of the current node:

Binary, binary tree

A binary tree with a maximum of two children (a tree with a maximum of two forks 🤦♀️) :

Graph:

Balanced binary tree

In a binary tree, the height difference between the left and right subtrees of each node cannot be greater than 1, which is called a balanced binary tree.

In addition, there are full binary trees, complete binary trees and so on:

  • Full binary tree: a binary tree in which every node except leaf has left and right cotyledons and leaves are at the lowest level
  • Complete binary tree: the depth of the tree is H, except for the h layer, the number of nodes of all other layers (1-H-1) reaches the maximum number, and all nodes of the H layer are continuously concentrated on the left

How to represent a binary tree in code

1. Chain storage

Binary tree storage is simple. In a binary tree, we see that each node contains three parts:

  • Val of the current node
  • Left child node left
  • The right child is right

So we can define each node as:

function Node(val) {
    // Save the current node key
    this.val = val
    // refers to the left child node
    this.left = null
    // point to the right child node
    this.right = null
}
Copy the code

A binary tree can be formed by connecting the root nodes with left and right Pointers to form a tree.

function BinaryTree() {
  let Node = function (val) {
    this.val = val
    this.left = null
    this.right = null
  }
  let root = null
}
Copy the code

2. Array storage method (for complete binary tree)

Here is a complete binary tree,

If we store the root node at position I =1, its left child is 2i = 2 and its right child is 2i+1 = 3.

If we choose node B I =2, its parent node is I /2 = 1, its left child node 2i=4, and its right child node 2i+1=5.

By analogy, we find that all nodes satisfy these three relations:

  • The node at position I, whose parent is at positioni/2
  • Its left child2i
  • Its right child2i+1

Therefore, if we store the complete binary tree in an array (stored from subscript 1), we can find the parent nodes of any node by subscript. Thus, the complete binary tree can be constructed completely. So that’s array storage.

Array storage saves memory by eliminating the need to create left and right Pointers for each node.

Five, binary tree traversal

The traversal of binary trees can be divided into:

  • The former sequence traversal
  • In the sequence traversal
  • After the sequence traversal

The so-called before, middle and after are just the order of roots, which can also be called first root traversal, middle root traversal and after root traversal

1. Preorder traversal

For any node in the binary tree, print that node first, then its left subtree, and finally its right subtree

2. Middle order traversal

For any node in the binary tree, print its left subtree first, then the node, and finally the right subtree

3. Back-order traversal

For any node in the binary tree, print its left subtree first, then its right subtree, and finally the node

4. Code implementation (fore-order traversal as an example)

Therefore, traversing the binary tree is also a recursive process, such as pre-order traversal, traversing the root node first, then the left subtree of the root, and finally the right subtree; When traversing the left subtree of the root node, first traverses the root node of the left subtree, then the left subtree of the left subtree, and then the right subtree of the left subtree… .

So, the core code is:

// Go through the core code
var preOrderTraverseNode = (node) = > {
    if(node) {
        // Start the root node
        result.push(node.val)
        // Then traverse the left subtree
        preOrderTraverseNode(node.left)
        // Walk through the right subtree again
        preOrderTraverseNode(node.right)
    }
}
Copy the code

The complete code is as follows:

The recursive implementation
// preorder traversal
var preorderTraversal = (root) = > {
    let result = []
    var preOrderTraverseNode = (node) = > {
        if(node) {
            // Start the root node
            result.push(node.val)
            // Then traverse the left subtree
            preOrderTraverseNode(node.left)
            // Walk through the right subtree again
            preOrderTraverseNode(node.right)
        }
    }
    preOrderTraverseNode(root)
    return result
};
Copy the code

Since we can use recursion, can we also use iteration to implement Nan?

Iteration implement

Using the stack to record the traversal process, in fact, recursion uses the call stack, so here we can use the stack to simulate the recursive process

  • First the root is pushed
  • Push the root node off the stack and put the root node value into the result array
  • And then we go through the left subtree and the right subtree, because the stack is first in and then out, so we push the right subtree first, and then the left subtree
  • Continue to unstack (left subtree is unstacked)… .

Cycle out of the stack and iterate on the stack until the stack is empty and iterate is complete

// preorder traversal
const preorderTraversal = (root) = > {
    const list = [];
    const stack = [];
    
    // When the root node is not empty, push the root node to the stack
    if(root) stack.push(root)
    while(stack.length > 0) {
        const curNode = stack.pop()
        // The first step is to access the root node
        list.push(curNode.val)
        
        // We print the left subtree first, then the right subtree
        // So the right subtree is added first, then the left subtree
        if(curNode.right ! = =null) {
            stack.push(curNode.right)
        }
        if(curNode.left ! = =null) {
            stack.push(curNode.left)
        }
    }
    return list
}
Copy the code
Complexity analysis:

Space complexity: O(n)

Time complexity: O(n)

So far, we have realized the pre-order traversal of binary tree, try to think about how to realize the middle order traversal of binary tree.

Leetcode94: Middle order traversal of binary tree

Given a binary tree, return its middle-order traversal.

Example:

Input:1.null.2.3]
   1
    \
     2
    /
   3Output:1.3.2]
Copy the code

Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?

Please submit your answers to javascript-Algorithms. Here we have submitted a series of articles and titles about Algorithms used on the front end. Welcome to Star. If you feel good, give it a thumbs up at 😊

Seven, past wonderful

  • Front-end advanced algorithm 6: queue, double-ended queue, sliding window and matching algorithm
  • Front-end advanced algorithm: common algorithm problems and perfect problem solutions
  • Video interview uHF online programming questions, enough to handle most companies
  • 10 questions and 10 answers, with a quick introduction to front-end algorithms
  • Front-end advanced Algorithm 5: Fully read the stack structure used by the front-end (+ LeetCode
  • Front-end advanced algorithm 4: Linked lists are so simple
  • Front-end advanced algorithm 3: Learning the LRU algorithm from the browser cache elimination strategy and Vue’s keep-alive
  • Bottle jun front-end advanced algorithm camp first week summary
  • Front-end advanced algorithm 2: JavaScript array from Chrome V8 source code
  • Front-end advanced algorithm 1: How to analyze and count the execution efficiency and resource consumption of algorithms?

The first phase of the front-end algorithm training camp is free to join

Scan code to join the front-end algorithm training camp, from 0 to 1 to build a complete data structure and algorithm system!

Here, I not only introduce algorithms, but also combine algorithms with various front-end areas, including browsers, HTTP, V8, React, Vue source code, and so on.

Here, you can learn a big factory algorithm (Ali, Tencent, Baidu, byte, etc.) or leetcode every day, Aquarius will solve it the next day!

Scan code into the camp to learn! If the number of two-dimensional code has reached the upper limit, you can scan the bottom two-dimensional code, in the public number “front-end bottle jun” reply “algorithm” automatically pull you into the group learning