定义一颗树，JS中常见的树形数据结构如下，children属性对应的是子树
let tree = [
{
id: '1',
name: '节点1',
children: [
{
id: '1-1',
name: '节点1-1'
}
]
},
{
id: '2',
name: '节点2',
children: [
{
id: '2-1',
name: '节点2-1'
},
{
id: '2-2',
name: '节点2-2',
children: [
{
id: '2-2-1',
name: '节点2-2-1'
}
]
}
]
},
{
id: '3',
name: '节点3'
}
]
二、深度优先遍历（DFS）
1、递归实现
function treeIterator(tree, func) {
tree.forEach((node) =>{
func(node)
node.children &&treeIterator(node.children, func)
})
}
实现逻辑简述：定义treeIterator函数，传入tree（树）和func（回调函数）两个参数，遍历tree数组，执行回调函数，如果当前节点存在children，则递归调用。
函数调用验证：调用treeIterator函数，传入上文定义好的树结构数组，打印出每个节点的name值。
treeIterator(tree, (node) =>{
console.log(node.name)
})
控制台打印结果如下：
2、循环实现
function treeIterator(tree, func) {
let node, curTree = [...tree]
while ((node = curTree.shift())) {
func(node)
node.children &&curTree.unshift(...node.children)
}
}
实现逻辑简述：
（1）定义node作为当前节点，curTree为传入的树（不影响原数组tree）；
（2）执行while循环，curTree数组第一个元素从其中删除，并返回第一个元素赋值给node；
（3）①执行回调函数；②如果当前节点存在子树，则追加到curTree数组的开头，继续执行循环，直到curTree没有元素为止。
函数调用验证：参考上述递归实现验证，方式和结果一致。
三、广度优先遍历（BFS）
function treeIterator(tree, func) {
let node, curTree = [...tree]
while ((node = curTree.shift())) {
func(node)
node.children &&curTree.push(...node.children)
}
}
实现逻辑简述：和上述深度优先遍历的循环实现差不多。区别在于如果当前节点存在子树，则追加到list数组的末尾。
求 1-100 的和
1,1,2,3,5,8,13,21,34,55,89...求第 n 项
JS 递归 假如楼梯有 n 个台阶，每次可以走 1 个或 2 个台阶，请问走完这 n 个台阶有几种走法
原理: clone(o) = new Object返回一个对象
1、很多时候可以用递归代替循环，可以理解为递归是一种特殊的循环，但通常情况下不推荐这样做。
2、递归一般是在函数里面把函数自己给调用一遍，通过每次调用改变条件，来结束循环。
3、递归在数据格式一致，在数据层级未知的情况下，比普通的遍历更有优势。
4、递归在异步的时候，更容易理解，且更容易实现，因为可以在异步的回调里面，调用自己来实现每次都能拿到异步的结果再进行其他操作。
5、递归实现的快速排序比普通遍历实现的排序效率更好。
<!DOCTYPE >
<html>
<head>
<meta content="" charset="utf-8">
<title>函数的递归调用</title>
</head>
<body>
<script>
//递归的概念:自己调用自己
//注意:使用递归的时候必须有一个结束标志,否则会报内存溢出的错误 Maximum call stack size exceeded
/* 1.案例一:求1，2，3...n 的和 */
function fn(n){
if(n===1){
return 1
}
return n+fn(n-1)
}
//console.log(fn(3))
/* 2.案例二：求1,2,3...到n的阶乘 */
function getFactorial(n){
if(n===1){
return 1
}
return n * getFactorial(n-1)
}
//console.log(getFactorial(3))
/* 案例三：斐波那契数列 *///第n个数等于前两个数的和，除第一个数跟第二个树外：如1,1,2,3,5,8,11,19,30...
function getNFibonacciSequence(n){
if(n===1 || n===2){
return 1
}
return getNFibonacciSequence(n-1)+getNFibonacciSequence(n-2)
}
console.log(getNFibonacciSequence(4))
</script>
</body>
</html>
