本文目錄

1. 回顧數(shù)組本篇使用的五個(gè)方法
2. 深度優(yōu)先遍歷 (遞歸方法) 思路+代碼
3. 深度優(yōu)先遍歷 (非遞歸方法) 思路+代碼
4. 廣度優(yōu)先遍歷 (非遞歸方法) 思路+代碼

雖然剛好舉的例子是二叉樹，但是幾個(gè)叉都能遍歷哈，因?yàn)楸闅v思路和叉數(shù)沒關(guān)系

需求：遍歷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. 首先回顧下本篇用到的數(shù)組的5個(gè)方法

2. 深度優(yōu)先遍歷 (遞歸方法) => 前序遍歷

前序遍歷: 根節(jié)點(diǎn)--> 左節(jié)點(diǎn) --> 右節(jié)點(diǎn)

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))  // 遞歸調(diào)用該函數(shù)
  }
  return arr
}
traverseTree(root);

3. 深度優(yōu)先遍歷 (非遞歸方法) 思路+代碼 => 前序遍歷

思路:
1：聲明一個(gè)數(shù)組用于存放所有的節(jié)點(diǎn);
2：通過(guò)循環(huán)依次從數(shù)組stack頭部拿一個(gè)節(jié)點(diǎn)進(jìn)行遍歷；
3：若其有子節(jié)點(diǎn)，則將其子節(jié)點(diǎn)(即tmpNode)放入stack隊(duì)頭；
4：若其無(wú)子節(jié)點(diǎn)，則再次進(jìn)入while循環(huán);

function traverseTree2(node) {
  if (!node) {
    return;
  }
  let stack = [];     // 用于存放所有待處理節(jié)點(diǎn)
  let arr = [];         // 存放遍歷后的結(jié)果
  let tmpNode;     //當(dāng)前正在被處理的節(jié)點(diǎn)
  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))  // !!廣度和深度唯一的區(qū)別在這里
    }
  }
  return arr
}

廣度優(yōu)先遍歷 (非遞歸方法) 思路+代碼 => 按層遍歷

思路:
與深度優(yōu)先唯一不同點(diǎn)是遍歷當(dāng)前節(jié)點(diǎn)時(shí)，若其有子節(jié)點(diǎn)時(shí), 則將其子節(jié)點(diǎn)放于stack的尾部；

function traverseTree3(node) {
  if (!node) {
    return;
  }
   let stack = [];     // 用于存放所有待處理節(jié)點(diǎn)
  let arr = [];         // 存放遍歷后的結(jié)果
  let tmpNode;     //當(dāng)前正在被處理的節(jié)點(diǎn)

  stack.push(node);
  while (stack.length) {
    tmpNode = stack.shift();   // !!
    // 當(dāng)前節(jié)點(diǎn)的'name'屬性放進(jìn)arr
    arr.push(tmpNode.name);
    if (tmpNode.children && tmpNode.children.length) {
      tmpNode.children.map(item => stack.push(item)) // !!
    }
  }
  return arr;
}