本文目录

1. 回顾数组本篇使用的五个方法
2. 深度优先遍历 (递归方法) 思路+代码
3. 深度优先遍历 (非递归方法) 思路+代码
4. 广度优先遍历 (非递归方法) 思路+代码

虽然刚好举的例子是二叉树，但是几个叉都能遍历哈，因为遍历思路和叉数没关系

需求：遍历root拿到所有的 'name' 值

var root = {
      name: 'A',
      children: [
        { 
          name: 'B1',
          children: [
            { 
              name: 'C1',
              children: [
                { 
                  name: 'D',
                  children: [
                        { 
                            name: 'D1' ,
                            children: [{name: 'F1 '},{name: 'F2'}]
                        }, 
                        { name: 'D2' }
                  ]
                }
              ]
            }
          ]
        },
        {
          name: 'B2',
          children: [ {name: 'C2' }, { name: 'C3' } ]
        }
      ]
    }

image.png

1. 首先回顾下本篇用到的数组的5个方法

方法	参数	作用	返回值
arr.unshift(1)	要插入的值	向数组头部插入一个值	新数组length
arr.shift()	无	从数组头部取出一个值	取出的值
arr.push(1)	要放入的值	向数组尾部放入一个值	新数组length
arr.pop()	无	从数组尾部取出一个值	取出的值
arr.reverse()	无	反转数组的值

2. 深度优先遍历 (递归方法) => 前序遍历

前序遍历: 根节点--> 左节点 --> 右节点

let arr = [];     // 存放遍历得到的 'name' 的值
function traverseTree(node) {
  if (!node) {
    return;
  }
  arr.push(node.name)
  if (node.children && node.children.length > 0) {
    node.children.map(item => this.traverseTree(item))  // 递归调用该函数
  }
  return arr
}
traverseTree(root);

3. 深度优先遍历 (非递归方法) 思路+代码 => 前序遍历

思路:
1：声明一个数组用于存放所有的节点;
2：通过循环依次从数组stack头部拿一个节点进行遍历；
3：若其有子节点，则将其子节点(即tmpNode)放入stack队头；
4：若其无子节点，则再次进入while循环;

function traverseTree2(node) {
  if (!node) {
    return;
  }
  let stack = [];     // 用于存放所有待处理节点
  let arr = [];         // 存放遍历后的结果
  let tmpNode;     //当前正在被处理的节点
  stack.push(node);
  while (stack.length) {
    tmpNode = stack.shift(); // !!
    arr.push(tmpNode.name)
    if (tmpNode.children && tmpNode.children.length) {
      tmpNode.children.reverse().map(item => stack.unshift(item))  // !!广度和深度唯一的区别在这里
    }
  }
  return arr
}

广度优先遍历 (非递归方法) 思路+代码 => 按层遍历

思路:
与深度优先唯一不同点是遍历当前节点时，若其有子节点时, 则将其子节点放于stack的尾部；

function traverseTree3(node) {
  if (!node) {
    return;
  }
   let stack = [];     // 用于存放所有待处理节点
  let arr = [];         // 存放遍历后的结果
  let tmpNode;     //当前正在被处理的节点

  stack.push(node);
  while (stack.length) {
    tmpNode = stack.shift();   // !!
    // 当前节点的'name'属性放进arr
    arr.push(tmpNode.name);
    if (tmpNode.children && tmpNode.children.length) {
      tmpNode.children.map(item => stack.push(item)) // !!
    }
  }
  return arr;
}