An introduction to the tree

What is a tree

A tree is a data structureCopy the code

Common classifications of trees

Binary tree binary equilibrium tree binary search tree red black treeCopy the code

The characteristics of the tree

Trees generally have a root, connected to the root is the trunk; The trunk splits into many branches, which continue to divide into smaller branches; At the end of the branch are leaves;Copy the code

Depth-first traversal (DFS)

        let tree = [
          {
            label: 'a'.children: [{label: 'b'.children: [{label: 'd'
                  },
                  {
                    label: 'e'}]}, {label: 'c'.children: [{label: 'f'}]}]Copy the code
    /* Use recursion */
    function deepSearch (tree) {
     for (var i = 0; i < tree.length; i++) {
       console.log(tree[i].label)
       if (tree[i].children) {
         deepSearch(tree[i].children)
       }
     }
   }
       /* Instead of using recursion, the idea of using a stack requires that the data structure is given directly to an object */
  function deepSearch1(tree) {
   let nodes = [] // Save all nodes in sequence
   if (tree) {
     let stack = [] // Define a stack
     stack.push(tree) // The original tree push
     while(stack.length ! =0) {
       let item = stack.pop() / / out of the stack
       console.log(item, 'item') nodes.push(item) children=item&&item.children? item.children:[];for(let i = children.length - 1; i >= 0; i--) { // The element at the top of the stack goes off first, so the following children are pushed first
         stack.push(children[i]) // The child node is pushed}}console.log(nodes, 'nodes') // abdecf
     console.log(stack,'stack')}}Copy the code

Breadth-first traversal (BFS)

    Breath First Search (Breath First Search) */
    let tree = [
      {
        label: 'a'.children: [{label: 'b'.children: [{label: 'd'
              },
              {
                label: 'e'}]}, {label: 'c'.children: [{label: 'f'}]}]function breathSearch(tree) {
      let nodes = []
      let quene = tree // Create a queue to store the data in order
      for (var i = 0; i < quene.length; i++) {
        console.log(quene[i])
        nodes.push(quene[i])
        quene = quene[i].children ? quene.concat(quene[i].children): quene
      }
      console.log(nodes, 'nodes') // abcdef
    }
    breathSearch(tree)
Copy the code

conclusion

Depth-first traversal uses the recursive, stack (fifin, last out) idea, while breadth-first traversal uses the queue (fifin, first out) idea