算法系列-多叉树的遍历

const root = {
  data: 'A',
  children: [
    {
      data: 'B',
      children: [
        {
          data: 'E'
        },
        {
          data: 'F',
          children: [
            {
              data: "I"
            }
          ]
        }
      ]
    }, 
    {
      data: 'C'
    }, 
    {
      data: 'D',
      children: [
        {
          data: 'G',
          children: [
            {
              data: 'J'
            },
            {
              data: 'K'
            }
          ]
        },
        {
          data: 'H'
        }
      ]
    }
  ]
}
复制代码

const deepFirstSearch = (node) => {
  const children = node.children;
  console.log(node.data)
  if (children) {
    // 遍历子节点递归
    for (let i = 0, len = children.length; i < len; i++) {
      deepFirstSearch(children[i])
    }
  }
}
复制代码

const deepFirstSearch = (node) => {
  // 利用栈实现
  const stack = [node]
  while(stack.length) {
    // 出栈
    const curNode = stack.pop()
    console.log(curNode.data)
    // 遍历子节点压入栈中
    const children = curNode.children
    if (children) {
      // 得注意这边的顺序是反向的
      // 左边的节点后进栈才能先出栈
      for (let len = children.length, i = len - 1; i >= 0; i--) {
        stack.push(children[i])
      }
    }
  }
}
复制代码

const widthFirstSearch = (nodes) => {
  // 按层遍历的核心就是提前提取下次遍历的节点
  const nextChildren = []
  // 可以加个判断 这样就可以直接以根节点作为入参了
  nodes = Array.isArray(nodes) ? nodes : [nodes]
  // 加判断结束递归
  if (nodes.length === 0) return
  // 访问当前层次节点并提取下层节点
  for (let i = 0, len = nodes.length; i < len; i++) {
    console.log(nodes[i].data)
    if (nodes[i].children) {
      nextChildren.push(...nodes[i].children)
    }
  }
  // 递归下层次
  widthFirstSearch(nextChildren)
}
复制代码

const widthFirstSearch2 = (node) => {
  // 按层次遍历的非递归使用队列实现
  const list = [node]
  // 访问当前节点的同时往队列添加子节点以待下层遍历访问
  for (let i = 0; i < list.length; i++) {
    const curNode = list[i]
    console.log(curNode.data)
    if (curNode.children) {
      list.push(...curNode.children)
    }
  }
}
复制代码