[[359197]]

接下來讓我們一起來探討js數(shù)據(jù)結(jié)構(gòu)中的樹。這里的樹類比現(xiàn)實生活中的樹，有樹干，樹枝，在程序中樹是一種數(shù)據(jù)結(jié)構(gòu)，對于存儲需要快速查找的數(shù)據(jù)非有用，它是一種分層數(shù)據(jù)的抽象模型。一個樹結(jié)構(gòu)包含一系列存在父子關系的節(jié)點。每個節(jié)點都有一個父節(jié)點以及零個或多個子節(jié)點。如下所以為一個樹結(jié)構(gòu)：)

• 和樹相關的概念：1.子樹：由節(jié)點和他的后代構(gòu)成，如上圖標示處。2.深度：節(jié)點的深度取決于它祖節(jié)點的數(shù)量，比如節(jié)點5有2個祖節(jié)點，他的深度為2。3.高度：樹的高度取決于所有節(jié)點深度的最大值。

二叉樹和二叉搜索樹介紹

二叉樹中的節(jié)點最多只能有2個子節(jié)點，一個是左側(cè)子節(jié)點，一個是右側(cè)子節(jié)點，這樣定義的好處是有利于我們寫出更高效的插入，查找，刪除節(jié)點的算法。二叉搜索樹是二叉樹的一種，但是它只允許你在左側(cè)子節(jié)點存儲比父節(jié)點小的值，但在右側(cè)節(jié)點存儲比父節(jié)點大的值。接下來我們將按照這個思路去實現(xiàn)一個二叉搜索樹。

1. 創(chuàng)建BinarySearchTree類

這里我們將使用構(gòu)造函數(shù)去創(chuàng)建一個類：

function BinarySearchTree(){ 
    // 用于創(chuàng)建節(jié)點的類 
    let Node = function(key) { 
        this.key = key; 
        this.left = null; 
        this.right = null; 
    } 
    // 根節(jié)點 
    let root = null; 
} 

我們將使用和鏈表類似的指針方式去表示節(jié)點之間的關系，如果不了解鏈表，請看我后序的文章《如何實現(xiàn)單向鏈表和雙向鏈表》。

2.插入一個鍵

// 插入一個鍵 
this.insert = function(key) { 
    let newNode = new Node(key); 
    root === null ? (root = newNode) : (insertNode(root, newNode)) 
} 

向樹中插入一個新的節(jié)點主要有以下三部分：1.創(chuàng)建新節(jié)點的Node類實例 --> 2.判斷插入操作是否為根節(jié)點,是根節(jié)點就將其指向根節(jié)點 --> 3.將節(jié)點加入非根節(jié)點的其他位置。

insertNode的具體實現(xiàn)如下：

function insertNode(node, newNode){ 
    if(newNode.key < node.key) { 
        node.left === null ? (node.left = newNode) : (insertNode(node.left, newNode)) 
    }else { 
        node.right === null ? (node.right = newNode) : (insertNode(node.right, newNode)) 
    } 
} 

這里我們用到遞歸，接下來要實現(xiàn)的search，del等都會大量使用遞歸，所以說不了解的可以先自行學習了解。我們創(chuàng)建一個二叉樹實例，來插入一個鍵：

let tree = new BinarySearchTree(); 
tree.insert(20); 
tree.insert(21); 
tree.insert(520); 
tree.insert(521); 

插入的結(jié)構(gòu)會按照二叉搜索樹的規(guī)則去插入，結(jié)構(gòu)類似于上文的第一個樹圖。

樹的遍歷

訪問樹的所有節(jié)點有三種遍歷方式：中序，先序和后序。

• 中序遍歷：以從最小到最大的順序訪問所有節(jié)點
• 先序遍歷：以優(yōu)先于后代節(jié)點的順序訪問每個節(jié)點
• 后序遍歷：先訪問節(jié)點的后代節(jié)點再訪問節(jié)點本身

根據(jù)以上的介紹，我們可以有以下的實現(xiàn)代碼。

1 中序排序

this.inOrderTraverse = function(cb){ 
    inOrderTraverseNode(root, cb); 
} 
 
// 輔助函數(shù) 
function inOrderTraverseNode(node, cb){ 
    if(node !== null){ 
        inOrderTraverseNode(node.left, cb); 
        cb(node.key); 
        inOrderTraverseNode(node.right, cb); 
    } 
} 

使用中序遍歷可以實現(xiàn)對樹進行從小到大排序的功能。

2 先序排序

// 先序排序 --- 優(yōu)先于后代節(jié)點的順序訪問每個節(jié)點 
   this.preOrderTraverse = function(cb) { 
     preOrderTraverseNode(root, cb); 
   } 
 
   // 先序排序輔助方法 
   function preOrderTraverseNode(node, cb) { 
     if(node !== null) { 
       cb(node.key); 
       preOrderTraverseNode(node.left, cb); 
       preOrderTraverseNode(node.right, cb); 
     } 
   } 

使用先序排序可以實現(xiàn)結(jié)構(gòu)化輸出的功能。

3 后序排序

// 后續(xù)遍歷 --- 先訪問后代節(jié)點，再訪問節(jié)點本身 
   this.postOrderTraverse = function(cb) { 
     postOrderTraverseNode(root, cb); 
   } 
 
   // 后續(xù)遍歷輔助方法 
   function postOrderTraverseNode(node, cb) { 
     if(node !== null){ 
       postOrderTraverseNode(node.left, cb); 
       postOrderTraverseNode(node.right, cb); 
       cb(node.key); 
     } 
   } 

后序遍歷可以用于計算有層級關系的所有元素的大小。

搜索樹中的值

在樹中有三種經(jīng)常執(zhí)行的搜索類型：最大值，最小值，特定的值。

1 最小值

最小值通過定義可以知道即是左側(cè)樹的最底端的節(jié)點，具體實現(xiàn)代碼如下：

// 最小值 
   this.min = function(){ 
     return minNode(root) 
   } 
 
    function minNode(node) { 
     if(node) { 
       while(node && node.left !== null){ 
         node = node.left; 
       } 
       return node.key 
     } 
     return null 
   } 

相似的，實現(xiàn)最大值的方法如下：

// 最大值 
   this.max = function() { 
     return maxNode(root) 
   } 
 
   function maxNode(node) { 
     if(node){ 
       while(node && node.right !== null){ 
         node = node.right; 
       } 
       return node.key 
     } 
     return null 
   } 

2.搜索一個特定的值

// 搜索樹中某個值 
this.search = function(key) { 
    return searchNode(root, key) 
} 
 
// 搜索輔助方法 
function searchNode(node, key){ 
    if(node === null) { 
        return false 
    } 
    if(key < node.key) { 
        return searchNode(node.left, key) 
    } else if(key > node.key) { 
        return searchNode(node.right, key) 
    }else { 
        return true 
    } 
} 

3 移除一個節(jié)點

this.remove = function(key){ 
    root = removeNode(root, key); 
} 
 
// 發(fā)現(xiàn)最小節(jié)點 
function findMinNode(node) { 
    if(node) { 
    while(node && node.left !== null){ 
        node = node.left; 
    } 
    return node 
    } 
    return null 
} 
 
// 移除節(jié)點輔助方法 
function removeNode(node, key) { 
    if(node === null) { 
    return null 
    } 
 
    if(key < node.key){ 
    node.left = removeNode(node.left, key); 
    return node 
    } else if( key > node.key){ 
    node.right = removeNode(node.right, key); 
    return node 
    } else { 
    // 一個頁節(jié)點 
    if(node.left === null && node.right === null) { 
        node = null; 
        return node 
    } 
 
    // 只有一個子節(jié)點的節(jié)點 
    if(node.left === null) { 
        node = node.right; 
        return node 
    }else if(node.right === null) { 
        node = node.left; 
        return node 
    } 
 
    // 有兩個子節(jié)點的節(jié)點 
    let aux = findMinNode(node.right); 
    node.key = aux.key; 
    node.right = removeNode(node.right, aux.key); 
    return node 
    } 
} 

刪除節(jié)點需要考慮的情況比較多，這里我們會使用和min類似的實現(xiàn)去寫一個發(fā)現(xiàn)最小節(jié)點的函數(shù)，當要刪除的節(jié)點有兩個子節(jié)點時，我們要將當前要刪除的節(jié)點替換為子節(jié)點中最大的一個節(jié)點的值，然后將這個子節(jié)點刪除。

至此，一個二叉搜索樹已經(jīng)實現(xiàn)，但是還存在一個問題，如果樹的一遍非常深，將會存在一定的性能問題，為了解決這個問題，我們可以利用AVL樹，一種自平衡二叉樹，也就是說任何一個節(jié)點的左右兩側(cè)子樹的高度之差最多為1。