JS从“深度优先”和“广度优先”遍历获取数据中某一属性值的集合

JS实现深度优先遍历和广度优先遍历

1、要求

• 获取以下数据结构中所有name属性值的集合。
• 数据的结构如下：

const myData = [
  {
      name: 'a',
      children: [
          { name: 'b', children: [{ name: 'e' }] },
          { name: 'c', children: [{ name: 'f' }] },
          { name: 'd', children: [{ name: 'g' }] },
      ]
  },
  {
      name: 'a2',
      children: [
          { name: 'b2', children: [{ name: 'e2' }] },
          { name: 'c2', children: [{ name: 'f2' }] },
          { name: 'd2', children: [{ name: 'g2' }] },
      ],
  }
]

2、实现

2.1、深度优先遍历

• 思路：先深拷贝数据>>>内部创建一个deep函数，通过for…in…来判断所有键（或项）的值是否为数组或对象>>>如果值为数组或对象，则将该值作为遍历的数组或对象递归调用。如果不是，则检查该键（项）是否为name，是则放入到result数组中。
• 程序如下：

function deepTraversal(data) {
	const temp = JSON.parse(JSON.stringify(data));
	const result = [];
	function deep(list) {
		//只有list不为null时才执行
		if (list) {
			for (let key in list) {
				//如果list[key]的值是对象或数组，则继续深度遍历
				//数组、对象或null的typeof结果都为object。此处也可以用constructor来判断
				if (typeof list[key] === "object") {
					deep(list[key]);				
				} else {
					//如果不是数组也不是对象，则分析key是否为name
					if (key === "name") {
						result.push(list[key])
					}
				}
			}
		} return;
	}
	deep(temp);
	return result
}
console.log(deepTraversal(myData));

• 输出结果：
  ["a", "b", "e", "c", "f", "d", "g", "a2", "b2", "e2", "c2", "f2", "d2", "g2"]

2.2、广度优先遍历

• 思路：先深拷贝数据>>>>创建trans空数组（用来保存每次得到的下一级节点），wide函数(用来分析哪个子节点的值是否为数组或函数)>>>只要trans不为空，则会继续分析下一级节点
• 程序如下：

function wideTraversal(data) {
	const temp = JSON.parse(JSON.stringify(data));
	const result = [];
	const trans = [];	//保存过渡用到的子节点
	function wide(list) {
		if (list) {
			//每递归一次（表示遍历了某个子节点），遍历完则移除该节点
			trans.shift();
			for (let key in list) {
				//分析值是否为对象或数组
				if (typeof list[key] === "object") {
					trans.push(list[key]);
				} else {
					if (key === "name") {
						result.push(list[key])	
					}
				}
			}
		}
		// 如果过渡数组中有项，则会遍历该数组，并递归调用wide
		if (trans) {
			trans.forEach(child => {
				wide(child);
			})
		}
	}
	wide(temp);
	return result
}
console.log(wideTraversal(myData));

• 运行结果：
  ["a", "a2", "b", "c", "d", "b2", "c2", "d2", "e", "f", "g", "e2", "f2", "g2"]

3、 总结

• 网上有很多更好用的方法，也是从深度和广度两个方面遍历数据或节点树。这两个方法，我是通过思考和实践写出来了。
• 优点：相对比较容易理解。缺点：代码量确实比网上的方法要大一半。
• 自学前端半年，萌新入门，欢迎各位技术大拿提出意见和指教。