優(yōu)雅的使用javascript遞歸畫一棵結(jié)構(gòu)樹示例代碼

更新時間：2019年09月22日 14:48:23 作者：徐小夕

這篇文章主要給大家介紹了關(guān)于如何優(yōu)雅的使用javascript遞歸畫一棵結(jié)構(gòu)樹的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用javascript具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧

遞歸和尾遞歸

簡單的說，遞歸就是函數(shù)自己調(diào)用自己，它做為一種算法在程序設(shè)計語言中廣泛應用。其核心思想是把一個大型復雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解。一般來說，遞歸需要有邊界條件、遞歸前進階段和遞歸返回階段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

但是作為一個合格的程序員，我們也因該知道，遞歸算法相對常用的算法如普通循環(huán)等，運行效率較低。因此，應該盡量避免使用遞歸，除非沒有更好的算法或者某種特定情況，遞歸更為適合的時候。在遞歸調(diào)用的過程當中系統(tǒng)為每一層的返回點、局部量等開辟了棧來存儲，遞歸次數(shù)過多容易造成棧溢出等。

這個時候，我們就需要用到尾遞歸，即一個函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾，對于尾遞歸來說，由于只存在一個調(diào)用記錄，所以永遠不會發(fā)生"棧溢出"錯誤。

舉個例子，我們來實現(xiàn)一下階乘，如果用普通的遞歸，實現(xiàn)將是這樣的：

function factorial(n) {
 if (n === 1) return 1;
 return n * factorial(n - 1);
}

factorial(5) // 120

最多需要保存n個調(diào)用棧，復雜度 O(n)，如果我們使用尾遞歸：

function factorial(n, total) {
 if (n === 1) return total;
 return factorial(n - 1, n * total);
}

factorial(5) // 120

此時只需要保存一個調(diào)用棧，復雜度 O(1) 。通過這個案例，你是否已經(jīng)慢慢理解其精髓了呢？接下來我將介紹幾個常用的遞歸應用的案例，并在其后實現(xiàn)本文標題剖出的樹的實現(xiàn)。

遞歸的常用應用案例

1. 數(shù)組求和

對于已知數(shù)組arr，求arr各項之和。

function sumArray(arr, total) {
 if(arr.length === 1) {
  return total
 }
 return sum(arr, total + arr.pop())
}

let arr = [1,2,3,4];
sumArray(arr, arr[1]) // 10

該方法給函數(shù)傳遞一個數(shù)組參數(shù)和初始值，也就是數(shù)組的第一項，通過迭代來實現(xiàn)數(shù)組求和。

2. 斐波那且數(shù)列

斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學上，斐波那契數(shù)列以如下被以遞推的方法定義：F(1)=1，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在現(xiàn)代物理、準晶體結(jié)構(gòu)、化學等領(lǐng)域，斐波納契數(shù)列都有直接的應用。接下來我們用js實現(xiàn)一個求第n個斐波那契數(shù)的方法：

// 斐波那契數(shù)列
function factorial1 (n) {
 if(n <= 2){
  return 1
 }
 return factorial1(n-1) + factorial1(n-2)
}

// 尾遞歸優(yōu)化后
function factorial2 (n, start = 1, total = 1) {
 if(n <= 2){
  return total
 }
 return factorial2 (n -1, total, total + start)
}

由尾遞歸優(yōu)化后的函數(shù)可以知道，每一次調(diào)用函數(shù)自身，都會將更新后的初始值和最終的結(jié)果傳遞進去，通過回溯來求得最終的結(jié)果。

3. 階乘

階乘在上文以提到過，如想回顧，請向上翻閱。

4. 省市級聯(lián)多級聯(lián)動

省市級聯(lián)多級聯(lián)動的方法本質(zhì)是生成結(jié)構(gòu)化的數(shù)據(jù)結(jié)構(gòu)，在element或antd中都有對應的實現(xiàn)，這里就不做過多介紹了。

5. 深拷貝

深拷貝的例子大家也已經(jīng)司空見慣了，這里只給出一個簡單的實現(xiàn)思路：

function clone(target) {
 if (typeof target === 'object') {
  let cloneTarget = Array.isArray(target) ? [] : {};
  for (const key in target) {
   cloneTarget[key] = clone(target[key]);
  }
  return cloneTarget;
 } else {
  return target;
 }
};

6. 爬梯問題

一共有n個臺階，每次只能走一個或兩個臺階，問要走完這個臺階，一共有多少種走法。

n =1; result = 1 --> 1
n =2; result = 2 --> 11 2
n =3; result = 3 --> 111 12 21
...
如果第一步走1個臺階，由以上規(guī)律可以發(fā)現(xiàn)剩下的臺階有n-1種走法；
如果第一步走2個臺階，由以上規(guī)律可以發(fā)現(xiàn)剩下的臺階有n-2種走法；
則一共有fn(n-1) + fn(n-2) 種走法
function steps(n) {
 if(n <= 1) {
  return 1
 }
 return steps(n-1) + steps(n-2)
}

7. 對象數(shù)據(jù)格式化

這道題是本人曾經(jīng)面試阿里的一道筆試題，問題是如果服務器返回了嵌套的對象，對象鍵名大小寫不確定，如果統(tǒng)一讓鍵名小寫。

let obj = {
 a: '1',
 b: {
  c: '2',
  D: {
   E: '3'
  }
 }
}
轉(zhuǎn)化為如下：
let obj = {
 a: '1',
 b: {
  c: '2',
  d: {
   e: '3'
  }
 }
}

// 代碼實現(xiàn)
function keysLower(obj) {
 let reg = new RegExp("([A-Z]+)", "g");
 for (let key in obj) {
  if (obj.hasOwnProperty(key)) {
   let temp = obj[key];
   if (reg.test(key.toString())) {
    // 將修改后的屬性名重新賦值給temp，并在對象obj內(nèi)添加一個轉(zhuǎn)換后的屬性
    temp = obj[key.replace(reg, function (result) {
     return result.toLowerCase()
    })] = obj[key];
    // 將之前大寫的鍵屬性刪除
    delete obj[key];
   }
   // 如果屬性是對象或者數(shù)組，重新執(zhí)行函數(shù)
   if (typeof temp === 'object' || Object.prototype.toString.call(temp) === '[object Array]') {
    keysLower(temp);
   }
  }
 }
 return obj;
};

具體過程和思路在代碼中已經(jīng)寫出了注釋，感興趣可以自己研究一下。

我們這里使用node來實現(xiàn)刪除一個目錄，用現(xiàn)有的node API確實有刪除目錄的功能，但是目錄下如果有文件或者子目錄，fs.rmdir && fs.rmdirSync 是不能將其刪除的，所以要先刪除目錄下的文件，最后再刪除文件夾。

function deleteFolder(path) {
 var files = [];
 if(fs.existsSync(path)) { // 如果目錄存在
  files = fs.readdirSync(path);
  files.forEach(function(file,index){
   var curPath = path + "/" + file;
   if(fs.statSync(curPath).isDirectory()) { // 如果是目錄，則遞歸
    deleteFolder(curPath);
   } else { // 刪除文件
    fs.unlinkSync(curPath);
   }
  });
  fs.rmdirSync(path);
 }
}

9. 繪制分形圖形

通過遞歸，我們可以在圖形學上有更大的自由度，但是請記住，并不是最好的選擇。

我們可以借助一些工具和遞歸的思想，實現(xiàn)如上的分形圖案。

10. 扁平化數(shù)組Flat

數(shù)組拍平實際上就是把一個嵌套的數(shù)組，展開成一個數(shù)組，如下案例：

let a = [1,2,3, [1,2,3, [1,2,3]]]
// 變成
let a = [1,2,3,1,2,3,1,2,3]
// 具體實現(xiàn)
function flat(arr = [], result = []) {
  arr.forEach(v => {
    if(Array.isArray(v)) {
      result = result.concat(flat(v, []))
    }else {
      result.push(v)
    }
  })
  return result
}

flat(a)

當然這只是筆者實現(xiàn)的一種方式，更多實現(xiàn)方式等著你去探索。

用遞歸畫一棵自定義風格的結(jié)構(gòu)樹

通過上面的介紹，我想大家對遞歸及其應用已經(jīng)有一個基本的概念，接下來我將一步步的帶大家用遞歸畫一棵結(jié)構(gòu)樹。

效果圖：

該圖形是根據(jù)目錄結(jié)構(gòu)生成的目錄樹圖，在很多應用場景中被廣泛使用，接下來我們就來看看他的實現(xiàn)過程吧：

const fs = require('fs')
const path = require('path')
// 遍歷目錄/生成目錄樹
function treeFolder(path, flag = '|_') {
  var files = [];
  
  if(fs.existsSync(path)) {
    files = fs.readdirSync(path);
    files.forEach(function(file,index){
      var curPath = path + "/" + file;
      if(fs.statSync(curPath).isDirectory()) { // recurse
        // obj[file] = treeFolder(curPath, {});
        console.log(flag, file)
        treeFolder(curPath, '  ' + flag)
      } else {
        // obj['--'] = file
        console.log(flag, file)
      }
    })
    // return obj
  }
}

treeFolder(path.resolve(__dirname, './test'))

test為我們建的測試目錄，如下：