JavaScript 中怎么實(shí)現(xiàn)一個(gè)二叉樹算法

這篇文章將為大家詳細(xì)講解有關(guān)JavaScript 中怎么實(shí)現(xiàn)一個(gè)二叉樹算法，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

二叉樹和二叉搜索樹介紹

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

1. 創(chuàng)建BinarySearchTree類

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

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

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

2.插入一個(gè)鍵

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

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

insertNode的具體實(shí)現(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))     } }

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

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

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

樹的遍歷

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

• 中序遍歷：以從最小到最大的順序訪問所有節(jié)點(diǎn)

• 先序遍歷：以優(yōu)先于后代節(jié)點(diǎn)的順序訪問每個(gè)節(jié)點(diǎn)

• 后序遍歷：先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)再訪問節(jié)點(diǎn)本身

根據(jù)以上的介紹，我們可以有以下的實(shí)現(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);     } }

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

2 先序排序

// 先序排序 --- 優(yōu)先于后代節(jié)點(diǎn)的順序訪問每個(gè)節(jié)點(diǎn)    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);      }    }

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

3 后序排序

// 后續(xù)遍歷 --- 先訪問后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身    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ì)算有層級(jí)關(guān)系的所有元素的大小。

搜索樹中的值

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

1 最小值

最小值通過定義可以知道即是左側(cè)樹的最底端的節(jié)點(diǎn)，具體實(shí)現(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    }

相似的，實(shí)現(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.搜索一個(gè)特定的值

// 搜索樹中某個(gè)值 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 移除一個(gè)節(jié)點(diǎn)

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

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

關(guān)于JavaScript 中怎么實(shí)現(xiàn)一個(gè)二叉樹算法就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。