编程知识 cdmana.com

JavaScript data structure and algorithm learning notes "tree"

Introduction to tree

  • An abstract model of hierarchical data
  • Common trees in front-end work include : DOM Trees 、 Cascade selection ( Provincial and urban three levels , date ...)、 Tree control ...
  • JS There are no trees in the forest , But you can use Object and Array Building tree , as follows :

    {
      value: " Anhui Province ",
      label: 'anhui',
      children: [
        {
          value: " Hefei ",
              label: 'hefei',
          children: [
            {
              value: " Baohe district ",
                    label: 'baohe',
              children: null
          },
            {
              value: ' Lakeside area ',
              label: 'binghu',
              children: null
            }
          ]
        },
        {
           {
            value: " Anqing City ",
            label: 'anqing',
            children: [
              {
                value: " Yuexiu District ",
                label: 'yuexiu',
                children: null
              }
            ]
          },
        }
      ]
    }
    • Common operations of trees : depth / Breadth Traverse first 、 First in order to traverse

Depth and breadth first traversal

1. Depth-first traversal : Search the branches of the tree as deep as possible

image-20201223205523031

Algorithm formula :

  • Access the root node
  • For the root node children Depth first traversal one by one

Code 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.map((child)=> dfs(child))
  root.children.map(dfs)
}
//  Perform depth first traversal functions 
dfs(tree)
//  After execution, output in turn : a b d e c f g

2. Breadth first traversal : First visit the node closest to the root node

image-20201223205608813

Algorithm formula

  • Create a new queue , Put the root node in the queue
  • Get the team leader out of the team and interview
  • Take the leader of the team children Join the team one by one
  • Repeat the second 、 The three step , Until the queue is empty

Code 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 bfs = (root) => {
  // step1:  Create a new queue 
  let queue = []
  // step2:  Put the root node in the queue 
  queue.push(root)
  while(queue.length > 0) {
    // step3:  Take out the team leader and interview 
    let n = queue.shift()
    console.log(n.val)
    // step4:  Take the leader of the team  children  Join the team one by one and repeat the above steps 
    n.children.map(child=> {
      queue.push(child)
    })
  }
}
//  Perform breadth first traversal functions 
bfs(tree)
//  Output... In sequence :a b c d e f g

3. Traversal of binary tree in the first middle and then order

  • Binary tree concept :

    Each node in the tree can have at most two child nodes ;

    stay JS Zhongtong common Object To simulate a binary tree

    Code emulation

    // 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;

The first sequence traversal

image-20201224100004922

Algorithm formula

  • Access the root node
  • The left subtree of the root node is traversed in order
  • First traverse the right subtree of the root node

Code practice

const bt = require('./bt')
const preOrder = (root) => {
  if(!root) return
  console.log(root.val)
  preOrder(root.left)
  preOrder(root.right)
}
//  perform 
preOrder(bt)
//  Output... In sequence :1 2 4 5 3 6 7

In the sequence traversal

image-20201224101445115

Algorithm formula

  • The left subtree of the root node is traversed in the middle order
  • Access the root node
  • The right subtree of the root node is traversed in the middle order

Code practice

const bt = require('./bt')

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

inOrder(bt)
//  Output... In sequence  4 2 5 1 6 3 7

After the sequence traversal

image-20201224102218265

Algorithm formula

  • The left subtree of the root node is traversed posteriorly
  • The right subtree of the root node is traversed posteriorly
  • Access the root node

Code practice

const bt = require('./bt')
const postOrder = (root) => {
  if(!root) return
  postOrder(root.left)
  postOrder(root.right)
  console.log(root.val)
}
postOrder(bt)
//  Output... In sequence :4 5 2 6 7 3 1

版权声明
本文为[Captain Timothy]所创,转载请带上原文链接,感谢
https://cdmana.com/2020/12/20201224104311384C.html

Scroll to Top