js广度遍历生成树,树的定义

JavaScript07

js广度遍历生成树,树的定义,第1张

先序，后序，中序针对二叉树。

深度、广度针对普通树。深度遍历：从树根开始扫描，顶层扫描完了，从一层最左（也可以右）面的结点往下层扫描，直到下层已无结点，这时所有靠最左（右）的结点全部扫描完毕，从树梢往上退一层，看这层旁有无兄弟结点，有的话还是一样从最左（右）边开始扫描，这是个递归概念，利用这一方法来遍历整棵树。广度遍历：从树根开始扫描，顶层扫描完了，扫描一层的所有结点，扫描二层的所有结点，，扫描最底层的结点。

深度优先遍历DFS

自定义：深度单线游走，从根走完最后一个节点，在游走兄弟节点，走完兄弟的所有子节点，循环之。

     递归算法：

function deepFirstSearch(node, nodeList = []) {

  if (node) {

    nodeList.push(node)

    var children = node.children

    for (var i = 0i <children.lengthi++)

      //每次递归的时候将 需要遍历的节点 和 节点所存储的数组传下去

      deepFirstSearch(children[i], nodeList)

  }

  return nodeList

}

非递归算法：

function deepFirstSearch(node) {

  var nodes = []

  if (node != null) {

    var stack = []

    stack.push(node)

    while (stack.length != 0) {

      var item = stack.pop()

      nodes.push(item)

      var children = item.children

      for (var i = children.length - 1i >= 0i--)

        stack.push(children[i])

    }

  }

  return nodes

}

广度优先遍历(BFS)

自定义：从根开始 层层推进 走完一层 走下一层 （犹如爬楼，走完一层的楼梯，继续下一层的楼梯）

递归算法：（容易栈溢出）

function breadthFirstSearch(node) {

  var nodes = []

  var i = 0

  if (!(node == null)) {

    nodes.push(node)

    breadthFirstSearch(node.nextElementSibling)

    node = nodes[i++]

    breadthFirstSearch(node.firstElementChild)

  }

  return nodes

}

非递归算法：（推荐）

function breadthFirstSearch(node) {

  var nodes = []

  if (node != null) {

    var queue = []

    queue.unshift(node)

    while (queue.length != 0) {

      var item = queue.shift()

      nodes.push(item)

      var children = item.children

      for (var i = 0i <children.lengthi++)

        queue.push(children[i])

    }

  }

  return nodes

}