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

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

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

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

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

他們有共同的特點(diǎn)，也是遞歸的特點(diǎn)：

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

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

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

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

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

（1）緩存Memoizer

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

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

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

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

使用動(dòng)態(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）效率對(duì)比

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");

// 動(dòng)態(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
// 當(dāng)打印到【1000】時(shí)，普通的已溢出
fibo_memo: 0.370ms
fibo_dp: 16.458ms

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

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

節(jié)點(diǎn)：樹中的每個(gè)元素都叫作節(jié)點(diǎn)；

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

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

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

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

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

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

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

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

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

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

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

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

有序樹

無序樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// 基類
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é)點(diǎn)
  }
  
  insert(){} // 插入節(jié)點(diǎn)
  preOrderTraverse(){} // 先序遍歷
  inOrderTraverse(){} // 中序遍歷
  postOrderTraverse(){} // 后序遍歷
  search(){} // 查找節(jié)點(diǎn)
  getMin(){} // 查找最小值
  getMax(){} // 查找最大值
  remove(){} // 刪除節(jié)點(diǎn)
}

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

不同情況具體操作如下：

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

根節(jié)點(diǎn)不為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é)點(diǎn)，步驟如下：

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

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

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

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

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

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

（1）中序遍歷

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

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é)點(diǎn)的順序訪問每個(gè)節(jié)點(diǎn)的。先序遍歷的一種應(yīng)用是打印一個(gè)結(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é)點(diǎn)的后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身。后序遍歷的一種應(yīng)用是計(jì)算一個(gè)目錄和它的子目錄中所有文件所占空間的大小

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)左下角為最小值，右下角為最大值

具體代碼實(shí)現(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()方法

遞歸找到與目標(biāo)key值相同的節(jié)點(diǎn)，并返回；具體實(shí)現(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é)點(diǎn)是這一類方法中最為復(fù)雜的操作，首先需要找到目標(biāo)key值對(duì)應(yīng)的節(jié)點(diǎn)，然后根據(jù)不同的目標(biāo)節(jié)點(diǎn)類型需要有不同的操作

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

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

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

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

目標(biāo)節(jié)點(diǎn)為葉節(jié)點(diǎn)圖例：子節(jié)點(diǎn)賦值為null，并將目標(biāo)節(jié)點(diǎn)指向null

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

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

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