摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法集合字典一遞歸學(xué)習(xí)樹離不開遞歸。先序遍歷的一種應(yīng)用是打印一個結(jié)構(gòu)化的文檔下面的圖描繪了先序遍歷方法的訪問路徑后序遍歷后序遍歷則是先訪問節(jié)點的后代節(jié)點，再訪問節(jié)點本身。

上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_集合&字典

學(xué)習(xí)樹離不開遞歸。

遞歸是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。遞歸通常涉及函數(shù)調(diào)用自身。

通俗的解釋：年級主任需要知道某個年級的數(shù)學(xué)成績的平均值，他沒法直接得到結(jié)果；年級主任需要問每個班的數(shù)學(xué)老師，數(shù)學(xué)老師需要問班上每個同學(xué)；然后再沿著學(xué)生-->老師-->主任這條線反饋，才能得到結(jié)果。遞歸也是如此，自己無法直接解決問題，將問題給下一級，下一級若無法解決，再給下一級，直到有結(jié)果再依次向上反饋。

我們常見的使用遞歸解決的問題，如下：

// 斐波拉契數(shù)列
function fibo(n) {
    if (n === 0 || n === 1) return n; // 邊界
    return fibo(n - 1) + fibo(n - 2);
}
// 階乘
function factorial(n) {
    if (n === 0 || n === 1) return 1; // 邊界
    return facci(n - 1) * n;
}

他們有共同的特點，也是遞歸的特點：

有邊界條件，防止無限遞歸

函數(shù)自身調(diào)用

以斐波拉契數(shù)列舉例，下面是n=6時斐波拉契數(shù)列的計算過程。

我們可以發(fā)現(xiàn)，這里面存在許多重復(fù)的計算，數(shù)列越大重復(fù)計算越多。

如何避免呢？利用緩存，將fib(n)計算后的值存儲，后面使用時，若存在直接取用，不存在則計算

（1）緩存Memoizer

const fibo_memo = function() {
  const temp = {0: 0, 1: 1}; // 需要用閉包緩存
  return function fib(n) {
      if (!(n in temp)) { // 緩存中無對應(yīng)數(shù)據(jù)時，向下計算查找
          temp[n] = fib(n - 1) + fib(n - 2);
      }
      return temp[n];
  }
}()

（2）遞推法（動態(tài)規(guī)劃）

動態(tài)規(guī)劃并不屬于高效遞歸，但是也是有效解決問題的一個方法。

動態(tài)規(guī)劃：從底部開始解決問題，將所有小問題解決掉，然后合并成一個整體解決方案，從而解決掉整個大問題；
遞歸：從頂部開始將問題分解，通過解決掉所有分解的小問題來解決整個問題；

使用動態(tài)規(guī)劃解決斐波那契數(shù)列

function fibo_dp(n) {
    let current = 0;
    let next = 1;
    for(let i = 0; i < n; i++) {
        [current, next] = [next, current + next];
    }
    return current;
}

（3）效率對比

const arr = Array.from({length: 40}, (_, i) => i);

// 普通
console.time("fibo");
arr.forEach((e) => { fibo(e); });
console.timeEnd("fibo");

// 緩存
console.time("fibo_memo");
arr.forEach((e) => { fibo_memo(e); });
console.timeEnd("fibo_memo");

// 動態(tài)規(guī)劃
console.time("fibo_dp");
arr.forEach((e) => { fibo_dp(e); });
console.timeEnd("fibo_dp");

// 打印結(jié)果【40】
fibo: 1869.665ms
fibo_memo: 0.088ms
fibo_dp: 0.326ms
// 當打印到【1000】時，普通的已溢出
fibo_memo: 0.370ms
fibo_dp: 16.458ms

總結(jié)：從上面的對比結(jié)果可知，使用緩存的性能最佳

一個樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點。每個節(jié)點都有一個父節(jié)點(除了頂部的第一個
節(jié)點)以及零個或多個子節(jié)點:

節(jié)點：樹中的每個元素都叫作節(jié)點；

根節(jié)點：位于樹頂部的節(jié)點叫作根節(jié)點；

內(nèi)部節(jié)點/分支節(jié)點：至少有一個子節(jié)點的節(jié)點稱為內(nèi)部節(jié)點或；

外部節(jié)點/葉節(jié)點：沒有子元素的節(jié)點稱為外部節(jié)點或葉節(jié)點；

子女節(jié)點：7和15為11的子女節(jié)點

父節(jié)點：11為7和15的父節(jié)點

兄弟節(jié)點：同一個父節(jié)點的子女節(jié)點互稱為兄弟；7和15互為兄弟節(jié)點

祖先節(jié)點：從根節(jié)點到該節(jié)點所經(jīng)過分支上的所有節(jié)點；如節(jié)點3的祖先節(jié)點為 11，7，8

子孫節(jié)點：以某一節(jié)點構(gòu)成的子樹，其下所有節(jié)點均為其子孫節(jié)點；如12和14為13的子孫節(jié)點

節(jié)點所在層次：根節(jié)點為1層，依次向下

樹的深度：樹中距離根節(jié)點最遠的節(jié)點所處的層次就是樹的深度；上圖中，樹的深度是4

節(jié)點的度：結(jié)點擁有子結(jié)點的數(shù)量；

樹的度：樹中節(jié)點的度的最大值；

有序樹

無序樹

關(guān)于數(shù)的深度和高度的問題，不同的教材有不同的說法，具體可以參考樹的高度和深度以及結(jié)點的高度和深度這篇文章

二叉樹是樹的一種特殊情況，每個節(jié)點最多有有兩個子女，分別稱為該節(jié)點的左子女和右子女，就是說，在二叉樹中，不存在度大于2的節(jié)點。

二叉搜索樹(BST)是二叉樹的一種，但是它只允許你在左側(cè)節(jié)點存儲(比父節(jié)點)小的值， 在右側(cè)節(jié)點存儲(比父節(jié)點)大(或者等于)的值。

上圖展示的便是二叉搜索數(shù)

同一層，數(shù)值從左到右依次增加

以某一祖先節(jié)點為參考，該節(jié)點左側(cè)值均小于節(jié)點值，右側(cè)值均大于節(jié)點值

在二叉樹的第i(i>=1)層，最多有x^(i-1)個節(jié)點

深度為k(k>=1)的二叉樹，最少有k個節(jié)點，最多有2^k-1個節(jié)點

對于一棵非空二叉樹，葉節(jié)點的數(shù)量等于度為2的節(jié)點數(shù)量加1

滿二叉樹：深度為k的滿二叉樹，是有2^k-1個節(jié)點的二叉樹，每一層都達到了可以容納的最大數(shù)量的節(jié)點

insert(key): 向樹中插入一個新的鍵；

inOrderTraverse: 通過中序遍歷方式遍歷所有節(jié)點

preOrderTraverse: 通過先序遍歷方式遍歷所有節(jié)點

postOrderTraverse: 通過后序遍歷方式遍歷所有節(jié)點

getMin: 返回樹中最小的值/鍵

getMax: 返回樹中最大的值/鍵

find(key): 在樹中查找一個鍵，如果節(jié)點存在則返回該節(jié)點不存在則返回null；

remove(key): 從樹中移除某個鍵

// 基類
class BinaryTreeNode {
  constructor(data) {
    this.key = data;
    this.left = null;
    this.right = null;
  }
}

下圖展現(xiàn)了二叉搜索樹數(shù)據(jù)結(jié)構(gòu)的組織方式：

//二叉查找樹（BST）的類
class BinarySearchTree {
  constructor() {
    this.root = null; // 根節(jié)點
  }
  
  insert(){} // 插入節(jié)點
  preOrderTraverse(){} // 先序遍歷
  inOrderTraverse(){} // 中序遍歷
  postOrderTraverse(){} // 后序遍歷
  search(){} // 查找節(jié)點
  getMin(){} // 查找最小值
  getMax(){} // 查找最大值
  remove(){} // 刪除節(jié)點
}

insert某個值到樹中，必須依照二叉搜索樹的規(guī)則【每個節(jié)點Key值唯一，最多有兩個節(jié)點，且左側(cè)節(jié)點值<父節(jié)點值<右側(cè)節(jié)點值】

不同情況具體操作如下：

根節(jié)點為null，直接賦值插入節(jié)點給根節(jié)點；

根節(jié)點不為null，按照BST規(guī)則找到left/right為null的位置并賦值

insert(key) {
  const newNode = new BinaryTreeNode(key);
  if (this.root !== null) {
    this.insertNode(this.root, newNode);
  } else {
    this.root = newNode;
  }
}

insertNode(node, newNode) {
  if (newNode.key < node.key) {
    if (node.left === null) {// 左側(cè)
      node.left = newNode;
    } else {
      this.insertNode(node.left, newNode);
    }
  } else {
    if (node.right === null) {// 右側(cè)
      node.right = newNode;
    } else {
      this.insertNode(node.right, newNode);
    }
  }
}

下圖為在已有BST的基礎(chǔ)上插入值為6的節(jié)點，步驟如下：

有無根節(jié)點？有；對比根節(jié)點值（6<11），根節(jié)點左側(cè)判斷；

第二層左側(cè)節(jié)點是否為null？不為；對比第二層左側(cè)節(jié)點的值（6<7），繼續(xù)左側(cè)判斷；

第三層左側(cè)節(jié)點是否為null？不為；對比第三層左側(cè)節(jié)點的值（6>5），以右側(cè)判斷；

第四層右側(cè)節(jié)點是否為null？為；插入該處

樹的遍歷，核心為遞歸：根節(jié)點需要找到其每一個子孫節(jié)點，但是并不知道這棵樹有多少層。因此，它找到其子節(jié)點，子節(jié)點也不知道，依次向下找，直到葉節(jié)點。

訪問樹的所有節(jié)點有三種方式:中序、先序和后序。下面依次介紹

（1）中序遍歷

中序遍歷是一種以上行順序訪問BST所有節(jié)點的遍歷方式，也就是以從最小到最大的順序訪問所有節(jié)點。中序遍歷的一種應(yīng)用就是對樹進行排序操作

inOrderTraverse(callback) {
  this.inOrderTraverseNode(this.root, callback);
}

inOrderTraverseNode(node, callback) {
  if (node !== null) {
    this.inOrderTraverseNode(node.left, callback);
    callback(node.key);
    this.inOrderTraverseNode(node.right, callback);
  }
}

下面的圖描繪了中序遍歷方法的訪問路徑:

（2）先序遍歷

先序遍歷是以優(yōu)先于后代節(jié)點的順序訪問每個節(jié)點的。先序遍歷的一種應(yīng)用是打印一個結(jié)構(gòu)化的文檔

preOrderTraverse(callback) {
  this.preOrderTraverseNode(this.root, callback);
}

preOrderTraverseNode(node, callback) {
  if (node !== null) {
    callback(node.key);
    this.preOrderTraverseNode(node.left, callback);
    this.preOrderTraverseNode(node.right, callback);
  }
}

下面的圖描繪了先序遍歷方法的訪問路徑:

（3）后序遍歷

后序遍歷則是先訪問節(jié)點的后代節(jié)點，再訪問節(jié)點本身。后序遍歷的一種應(yīng)用是計算一個目錄和它的子目錄中所有文件所占空間的大小

postOrderTraverse(callback) {
  this.postOrderTraverseNode(this.root, callback);
}

postOrderTraverseNode(node, callback) {
  if (node !== null) {
    this.postOrderTraverseNode(node.left, callback);
    this.postOrderTraverseNode(node.right, callback);
    callback(node.key);
  }
}

下面的圖描繪了后序遍歷方法的訪問路徑：

（1）最值
觀察下圖，我們可以非常直觀的發(fā)現(xiàn)左下角為最小值，右下角為最大值

具體代碼實現(xiàn)如下

getMin() {
  const ret = this.getMinNode();
  return ret && ret.key;
}

getMinNode(node = this.root) {
  if (node) {
    while (node && node.left !== null) {
      node = node.left;
    }
  }
  return node;
}

getMax() {
  const ret = this.getMaxNode();
  return ret && ret.key;
}

getMaxNode(node = this.root) {
  if (node) {
    while (node && node.right !== null) {
      node = node.right;
    }
  }
  return node;
}

（2）find()方法

遞歸找到與目標key值相同的節(jié)點，并返回；具體實現(xiàn)如下：

find(key) {
  return this.findNode(this.root, key);
}

findNode(node, key) {
  if (node === null) {
    return null;
  }
  if (key < node.key) {
    return this.findNode(node.left, key);
  }
  if (key > node.key) {
    return this.findNode(node.right, key);
  }
  return node;
}

移除節(jié)點是這一類方法中最為復(fù)雜的操作，首先需要找到目標key值對應(yīng)的節(jié)點，然后根據(jù)不同的目標節(jié)點類型需要有不同的操作

remove(key) {
  return this.removeNode(this.root, key);
}

removeNode(node, key) {
  if (node === null) {
    return null;
  }
  if (key < node.key) { // 目標key小于當前節(jié)點key，繼續(xù)向左找
    node.left = this.removeNode(node.left, key);
    return node;
  }
  if (key > node.key) { // 目標key小于當前節(jié)點key，繼續(xù)向右找
    node.right = this.removeNode(node.right, key);
    return node;
  }

  // 找到目標位置
  if (node.left === null && node.right === null) { // 目標節(jié)點為葉節(jié)點
    node = null;
    return node;
  }
  if (node.right === null) { // 目標節(jié)點僅有左側(cè)節(jié)點
    node = node.left;
    return node;
  }
  if (node.left === null) { // 目標節(jié)點僅有右側(cè)節(jié)點
    node = node.right;
    return node;
  }

  // 目標節(jié)點有兩個子節(jié)點
  const tempNode = this.getMinNode(node.right); // 右側(cè)最小值
  node.key = tempNode.key;
  node.right = this.removeNode(node.right, node.key);
  return node;
}

目標節(jié)點為葉節(jié)點圖例：子節(jié)點賦值為null，并將目標節(jié)點指向null

目標節(jié)點為僅有左側(cè)子節(jié)點或右側(cè)子節(jié)點圖例：將目標節(jié)點的父節(jié)點指向子節(jié)點

目標節(jié)點有兩個子節(jié)點：根據(jù)BST的構(gòu)成規(guī)則，以目標節(jié)點右側(cè)樹最小值替換重新連接

上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_集合&字典