JS遞歸及二叉搜索樹的移除節點

1遞歸含義：在某時某刻某個條件下調用包含自己的函數

2:註意點：⑴遞歸過程中一定要加限制條件，要不然會陷入死迴圈：

　　　　　　　　　　死迴圈eg：

function f(someP){
   f(somP);  
}
f(4); //Uncaught RangeError: Maximum call stack size exceeded

　　　　　　　　　　正常調用：

//計算輸入某個正整數，然後一直向下疊加 ，這裡僅僅做一個簡單示例，不進行輸入num的判斷
function f(num){
    let x;
    if(num>0){
        x =num + f(num-1); 
        return x;
    }
    return false;
}
    
f(5);

                     ⑵遞歸有個過程，不是一步到位的，這一點尤其重要，因為在學習JS數據結構與演算法中的二叉搜索樹的移除代碼會至關重要，不懂遞歸過程的話很容易看不懂移除代碼

function getSum(num){
     if(x === 1){
           return 1;
     }
     return num + getSum(num-1)
}

getSum(5);

　　　　　　過程如下：

　　　　　　　　　　①：getSum(5)調用函數並傳入參數5，執行函數中的num +getSum(num-1) ->5+getSum(5-1)

　　　　　　　　　　②：getSum(4)調用函數並傳入參數4，執行函數中的num+getSum(num-1) ->4+getSum(4-1)

　　　　　　　　　　③：getSum(3)調用函數並傳入參數3，執行函數中的num+getSum(num-1) ->3+getSum(3-1)

　　　　　　　　　　④：getSum(2)調用函數並傳入參數2，執行函數中的num+getSum(num-1) ->2+getSum(2-1)

　　　　　　　　　　⑤：getSum(1)調用函數並傳入參數1，執行函數中的return 1；

　　　　　　　　　　⑥：這時候再一步一步往回走，即1+2+3+4+5；即可以理解為遞歸調用過程中，是不會立即計算的，要等到限制條件結束後，才會一步一步往上計算。

3：二叉搜索樹的移除節點：移除節點程式是二叉搜索樹程式方法中最複雜的一個。

　　　eg：

class Node{    //節點類
  constructor(key){
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
function defaultCompare(a, b) {  //比較函數
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};
class BinarySearchTree{
  constructor(compareFn = defaultCompare){
    this.compareFn = compareFn;
    this.root = null;
  }
  remove(key){                                       
    this.root = this.removeNode(this.root,key);
  }
  removeNode(node,key){
    if(node == null){
      return null;
    }
    if(this.compareFn(key,node.key) === Compare.LESS_THAN){      // (1)
      node.left = this.removeNode(node.left,key);                //(2)
      return  node;　　　　　　　　　　　　　　　　　　　　　　　　　　　　//(3)
    }else if (this.compareFn(key,node.key) === Compare.BIGGER_THAN){　　//(4)
      node.right = this.removeNode(node.right,key);　　　　　　　　　　　　//(5)
      return  node;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//(6)　
    }else{　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//(7)
      if(node.left == null && node.right == null){  　　　　//(8)　　　　//第一種情況，移除一個葉節點（只有父節點沒有子節點的節點）
        node = null;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//(9)
        return  node;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//(10)
      }
      if(node.left == null){　　　　　　　　　　　　　　　//第二種情況，移除有一個左or右子節點的節點
        node = node.right;　　　　　　　　　　　　　　　　　　　　　　　　　　//(11)
        return  node;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//(12)
      }else if(node.right == null) {
        node = node.left;                                            //(13)
        return node;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//(14)
      }
      const aux = this.minNode(node.right);         //(15) //第三種情況，移除有兩個子節點的節點 
      node.key = aux.key;　　　　　　　　　　　　　　　　//(16)
      node.right = this.removeNode(node.right,aux.key); //(17)
      return  node;　　　　　　　　　　　　　　　　　　　　　　//(18)
    }
  }   
}
const tree1 = new BinarySearchTree();
tree1.remove(8);

　　　　假設現在有一個節點順序為

    　　　　現在我們需要移除節點8，則代碼的順序應該是：

①：開始時key:8   node: Node{ key: 11, left : Node, right : Node}，進入行(1)，判斷大小後進入行(2)，此時key:8   node: Node{ key: 7, left : Node, right : Node}

②：遞歸調用第一次，進入行(4)判斷大小後進入行(5)，此時key:8   node: Node{ key: 9, left : Node, right : Node}

③：遞歸調用第二次，進入行(1)判斷大小後進入行(2)，此時key:8   node: Node{ key: 8, left : null, right : null}

④：遞歸調用第三次，進入行(7 ，8， 9)，返回一個node，此時key: 8 ,node ：null；

⑤：進入行(3)，此時結果為： key:8 ,node:Node{key: 9 ,left:null,right:Node};

⑥：進入行(6)，此時結果為： key:8 ,node:Node{key: 9 ,left:Node,right:Node};

⑦：進入行(3)，此時結果為：key:8 ,node:Node{key: 11,left:Node,right:Node};

⑧：返回到remove()後，跳出程式，節點8已移除。

　　　備註1：上述步驟只實現了第一種情況，如果有需要，讀者可以用chrome的調試工具進行斷點調試，在Sources中可查看key及node的具體情況，

　　    備註2：這裡很明顯說明瞭遞歸調用的執行順序，我就是因為不懂執行順序，這段代碼看了我2個多小時。。。。。切記切記，