DFS与BFS的递归与迭代实现

问题

我们经常需要遍历这样一种菜单结构：

对应的数据结构如下：

let list = [{
  text: "A",
  children: [{text: "A1", children: null}, {text: "A2", children: null}]
}, {
  text: "B",
  children: [
    {
      text: "B1",
      children: [
        {text: "B11", children: [{
          text: "B111",
          children: null,
        }, {
          text: "B1112",
          children: null,
        }]}, 
        {text: "B12", children: null}]
    },
    {
      text: "B2",
      children: [{text: "B21", children: null}, {text: "B22", children: null}]
    },

  ]
}, {
  text: "C",
  children: null,
}, {
  text: "D",
  children: [{text: "D1", children: null}, {text: "D2", children: null}]
}];

 

这里给出几种实现代码：

实现

1.递归DFS

/* dfs recursive */
function dfsRecursion(list) {
  let result = [];
  for(let i=0; i<list.length; ++i) {
    result.push(list[i].text);
    if(list[i].children) {
      result.push(...dfs(list[i].children));
    }
  }
  return result;
}

 

2.迭代DFS

这里是使用栈来实现的,这里有个问题，这样会修改原来的list，如果是JSON安全的话，

可以先存一份副本：JSON.parse(JSON.stringify(list));然后再进行相应的处理

/* 
  dfs iteration
  注意这种方式会修改原数组 
*/
function dfsIteration (list) {
  let result = [];
  for(let i=0; i<list.length; ++i) {
    result.push(list[i].text);
    if(list[i].children) {
      list.splice(i+1, 0, ...list[i].children);
    } 
  }
  return result;
}

或者这样来实现

/*
  dfs iteration with stack
*/
function dfsIterationWithStack (list) {
  let result = [];
    stack = [];
  for(let i=0; i<list.length; ++i) {
    result.push(list[i].text);
    if(!list[i].children) {
      continue;
    } else {
      stack.push(...list[i].children.reverse());
    }
    let popItem;
    while(stack.length != 0) {
      popItem = stack.pop();
      result.push(popItem.text);
      popItem.children && stack.push(...popItem.children.reverse());
    }
  }
  return result;
}

 

3.递归BFS 

/* bfs recursive */
function bfsRecursion(list) {
  let result = [];
  let children = [];
  for(let i=0; i<list.length; ++i) {
    result.push(list[i].text);
    if(list[i].children) {
      children.push(...list[i].children);
    }
  }
  if(children.length != 0) {           
    return [...result, ...bfs(children)]
  } else {
    return result;
  }
}

 

4.迭代BFS

使用数组收集每一层的元素，直到为空，也可称之为层序遍历。

/* 
  bfs iteration
  使用队列来实现BFS 
*/
function bfsIteration (list) {    
  let result = [],
    children = [];
  while(list.length != 0) {
    for(let i=0; i<list.length; ++i) {
      result.push(list[i].text);
      if(list[i].children) {
        children.push(...list[i].children);
      }
    }
    list = children;
    children = [];
  }
  return result;
}

完