1. The tree

1.1 What is a tree?

  • A kind oflayeredAbstract model of data
  • Common trees in front-end work include: DOM tree, cascading selection, tree controls…

  • There are no trees in JS, but you can build trees with Object and Array
{
    value: 'guangdong'.label: 'guangdong'.children: [{value: 'guangzhou'.label: 'guangzhou'}, {value: 'shenzhen'.label: 'shenzhen',}}]Copy the code

1.2 Common Tree operations

  • Depth/breadth first traversal
  • Middle first and then order traversal

2. Depth and breadth first traversal

2.1 What is Depth/breadth first traversal

  • Deep mail traversal: Search as deep a branch of the tree as possible.
  • Breadth-first traversal: Visits the node closest to the following node first.

2.2 Depth first Traversal (DFS) algorithm formula

  • Accessing the root node
  • Children of root node are traversed depth-first one by one.

2.2.1 Depth first traversal (DFS) implementation

const tree = {
    val: 'a'.children: [{val: 'b'.children: [{val: 'd'.children: []}, {val: 'e'.children[],}],}, {val: 'c'.children: [{val: 'f'.children: []}, {val: 'g'.children: [],}],}],};const dfs = (root) = > {
    console.log(root.val);
    // root.children.forEach(child=>{dfs(child)})
    root.children.forEach(dfs);
};

dfs(tree);
Copy the code

2.3 Breadth-first traversal (BFS) algorithm formula

  • Create a queue and queue the root node
  • Take the team leader out of the team and visit
  • Put the children in the team one by one
  • Repeat steps 2 and 3 until the queue is empty

2.3.1 Breadth-first traversal (BFS) implementation

const bfs = (root) => { const q = [root]; while (q.length > 0) { const n = q.shift(); console.log(n.val); n.children.forEach(child => { q.push(child); }); }}; bfs(tree);Copy the code

3. Middle and then order traversal of binary tree

3.1 What is a binary tree

  • Each node in the tree has at most two child nodes
  • Object is usually used to simulate binary trees in JS
{
    val: 1.left: {},
    right: {}}Copy the code

Create a binary tree (BT)

  • This will be used in the code demo below
// bt.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

3.2 Algorithm formula of preorder[Root-left-right]

  • Accessing the root node
  • For the root nodeOn the leftSubtrees are traversed in order
  • For the root noderightSubtrees are traversed in order

const bt = require('./bt');

const preorder = (root) = > {
    if(! root) {return; }
    console.log(root.val);
    preorder(root.left);
    preorder(root.right);
};

preorder(bt);
Copy the code

3.3 Inorder algorithm formula[left-root-right]

  • Middle order traversal of the left subtree of the root node
  • Accessing the root node
  • Middle order traversal is performed on the right subtree of the root node

const bt = require('./bt');

const inorder = (root) = > {
    if(! root) {return; }
    inorder(root.left);
    console.log(root.val);
    inorder(root.right);
};

inorder(bt);
Copy the code

3.4 Postorder algorithm formula[left-right-root]

    1. A post-order traversal of the left subtree of the root node is performed
    1. A post-order traversal is performed on the right subtree of the root node
    1. Accessing the root node

// postorder.js
const bt = require('./bt');

const postorder = (root) = > {
    if(! root) {return; }
    postorder(root.left);
    postorder(root.right);
    console.log(root.val);
};
postorder(bt);
Copy the code