树的图示

根（root）树的主干

要点
1.dom
2.选择器
3.json
4.虚拟dom
5.文本查找和输入提示

树的遍历

树的查找

树的路径

基于class 和 tag 的简单css选择器

//  树的创建和递归
// 如果一个 二叉树，他的左边总比 右边小，那么他就是一个有序树列
class Tree {
  constructor(v, children) {
    this.v = v
    this.children = children || null
  }
}
const tree = new Tree(10, [new Tree(5), new Tree(3, [new Tree(7), new Tree(11)]), new Tree(2)])
// 树的遍历 （先序）
function tree_transverse (tree) {
  // console.log(tree.v)
  tree.children && tree.children.forEach(tree_transverse)
}
tree_transverse(tree) // 10 5 3 7 11 2  这里是深度优先原则
// 树的遍历 （后序）
function tree_transverse_l (tree) {
  tree.children && tree.children.forEach(tree_transverse_l)
  // console.log(tree.v) // 每次都迭代到叶子节点才可以做一次打印
}
tree_transverse_l(tree) // 5 7 11 3 2 10 
// 树的遍历 （中序）
function tree_transverse_m (tree, ord = 0) {
  let transversed = false
  if (!tree.children) {
    console.log(tree.v)
    return
  }
  tree.children.forEach((child, i) => {
    if (i === ord) {
      transversed = true
      console.log(tree.v);
    }
    tree_transverse_m(child, ord)
  })
  !transversed && console.log(tree.v) // 每次都迭代到叶子节点才可以做一次打印
}
// tree_transverse_m(tree, 0) // 10 5 3 7 11 2 
// tree_transverse_m(tree, 1) // 5 10 7 3 11 2
// tree_transverse_m(tree, 2) // 5 7 11 3 10 2
// tree_transverse_m(tree, 3) // 5 7 11 3 2 10 
// 树的遍历 （回调）
function tree_transverse_back (tree, ord = 0, callback) {
  let transversed = false
  if (!tree.children) {
    callback(tree.v)
    return
  }
  tree.children.forEach((child, i) => {
    if (i === ord) {
      transversed = true
      callback(tree.v);
    }
    tree_transverse_back(child, ord)
  })
  !transversed && callback(tree.v) // 每次都迭代到叶子节点才可以做一次打印
}

全排列

[1, 2, 3, 4] 的所有排列组合

// [1,2,3,4]的所有排列组合
// 怎么先取出1，在取出 234 ，然后取出2 在取出 134那
const A = [1, 2, 3, 4]
// A.slice(0, 1)// 取出第0项
// A.slice(2)// 取值第2项及以后
// A.slice(0, 1).concat(A.slice(2)) // 然后可以继续向上相加
function perm (A) {
  if (A.length === 1) { return [A] }
  return [].concat(...A.map((a, i) => {
    // [2,3,4]
    return perm(A.slice(0, i).concat(A.slice(i + 1))).map(p => [a].concat(p))
  }
  ))
}
console.log(perm(A))
// 基于交换，因为上面的虽然出结果了，但是slice 和 concat 需要把数组重复拷贝
// 所以优化就把一个数组里，[1,2,3,4]->[4,1,2,3]->[1,2,3,4]->[1,4,3,2]
// 就是一个数组的内部交换 ，然后在还原在交换

手写一个节点选择器

function* transverse (node) {
  yield node
  if (node.children) {
    const children = [...node.children]
    for (let i = 0; i < children.length; i++) {
      yield* transverse(children[i])
    }
  }
}

function get_range (x) {
  const m = x.match(/\[(.*)\]/)
  if (m) {
    return (arr) => arr.slice(...m[1].split(':').filter(x => !!x))
  }
}

// .box img 
// [{className:'.box'},{tagName:'img'}]
function parse_selection_expr (expr) {
  return expr.split(' ').map(x => {
    const range = get_range(x)
    if (x[0] === '.') {
      return { className: x.substr(1), range }
    } else {
      return { tagName: x, range }
    }
  })
}
function is_ancestor (node1, node2) {
  let p = node2
  while (p) {
    if (p === node1) { return true }
    p = p.parentNode
  }
  return false
}

function selector (node, path) {
  if (path.length === 0) {return [node]}
  const p = path.shift()
  let nodes = []
  if (p.className) {
    nodes = [...document.getElementsByClassName(p.className)].filter(v => is_ancestor(node, v))
  } else if (p.tagName) {
    nodes = [...transverse(node)].filter(n => n.tagName === p.tagName)
  }
  p.range && (nodes = p.range(nodes))
  return [].concat(...nodes.map(node => selector(node, [...path])))
}

深度遍历

1.访问根节点。
2.对根节点的children挨个进行深度优先遍历。

const tree = {
  val: 'a',
  children: [{
    val: 'b',
    children: [
      {
        val: 'd',
        children: []
      },
      {
        val: 'e',
        children: []
      }
    ]
  },
  {
    val: 'c',
    children: [
      {
        val: 'f',
        children: []
      },
      {
        val: 'g',
        children: []
      }
    ]
  }]
}

/**
 * 
  算法口诀：  
  1.访问根节点。
  2.对根节点的children挨个进行深度优先遍历。
*/
const dfs = (root) => {
  console.log(root.val);
  if(!root.children) return
  root.children.forEach(dfs);
}

dfs(tree)

广度遍历

1.新建一个队列，把根节点入队。
2.把队头出队并访问。
3.把队头的children挨个入队。
4.重复第二、三步，直到队列为空。

const tree = {
  val: 'a',
  children: [{
    val: 'b',
    children: [
      {
        val: 'd',
        children: []
      },
      {
        val: 'e',
        children: []
      }
    ]
  },
  {
    val: 'c',
    children: [
      {
        val: 'f',
        children: []
      },
      {
        val: 'g',
        children: []
      }
    ]
  }]
}

/**
 * 
 * 算法口诀：
1.新建一个队列，把根节点入队。
2.把队头出队并访问。
3.把队头的children挨个入队。
4.重复第二、三步，直到队列为空。 
 */
const bfs = (root) => {
  const q = [root];
  let all = [];
  while (q.length > 0) {
    const n = q.shift();
    n.children.forEach((child) => {
      q.push(child);
    });
  }
  console.log(all)
}

bfs(tree)

全栈算法

0204树

树的图示

树的遍历

树的查找

树的路径

基于class 和 tag 的简单css选择器

全排列

深度遍历

广度遍历

二叉树每层的最大值

二叉树每次最左边的值