前端: JavaScript 中的二叉樹(shù)算法實(shí)現(xiàn)
接下來(lái)讓我們一起來(lái)探討js數(shù)據(jù)結(jié)構(gòu)中的樹(shù)。這里的樹(shù)類(lèi)比現(xiàn)實(shí)生活中的樹(shù)，有樹(shù)干，樹(shù)枝，在程序中樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)，對(duì)于存儲(chǔ)需要快速查找的數(shù)據(jù)非有用，它是一種分層數(shù)據(jù)的抽象模型。一個(gè)樹(shù)結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)以及零個(gè)或多個(gè)子節(jié)點(diǎn)。如下所以為一個(gè)樹(shù)結(jié)構(gòu)：)
- 和樹(shù)相關(guān)的概念：1.子樹(shù)：由節(jié)點(diǎn)和他的后代構(gòu)成，如上圖標(biāo)示處。2.深度：節(jié)點(diǎn)的深度取決于它祖節(jié)點(diǎn)的數(shù)量，比如節(jié)點(diǎn)5有2個(gè)祖節(jié)點(diǎn)，他的深度為2。3.高度：樹(shù)的高度取決于所有節(jié)點(diǎn)深度的最大值。
二叉樹(shù)和二叉搜索樹(shù)介紹
二叉樹(shù)中的節(jié)點(diǎn)最多只能有2個(gè)子節(jié)點(diǎn)，一個(gè)是左側(cè)子節(jié)點(diǎn)，一個(gè)是右側(cè)子節(jié)點(diǎn)，這樣定義的好處是有利于我們寫(xiě)出更高效的插入，查找，刪除節(jié)點(diǎn)的算法。二叉搜索樹(shù)是二叉樹(shù)的一種，但是它只允許你在左側(cè)子節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)小的值，但在右側(cè)節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)大的值。接下來(lái)我們將按照這個(gè)思路去實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)。
1. 創(chuàng)建BinarySearchTree類(lèi)
這里我們將使用構(gòu)造函數(shù)去創(chuàng)建一個(gè)類(lèi)：
- function BinarySearchTree(){
- // 用于創(chuàng)建節(jié)點(diǎn)的類(lèi)
- let Node = function(key) {
- this.key = key;
- this.left = null;
- this.right = null;
- }
- // 根節(jié)點(diǎn)
- let root = null;
- }
我們將使用和鏈表類(lèi)似的指針?lè)绞饺ケ硎竟?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))
- }
向樹(shù)中插入一個(gè)新的節(jié)點(diǎn)主要有以下三部分：1.創(chuàng)建新節(jié)點(diǎn)的Node類(lèi)實(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))
- }
- }
這里我們用到遞歸，接下來(lái)要實(shí)現(xiàn)的search，del等都會(huì)大量使用遞歸，所以說(shuō)不了解的可以先自行學(xué)習(xí)了解。我們創(chuàng)建一個(gè)二叉樹(shù)實(shí)例，來(lái)插入一個(gè)鍵：
- let tree = new BinarySearchTree();
- tree.insert(20);
- tree.insert(21);
- tree.insert(520);
- tree.insert(521);
插入的結(jié)構(gòu)會(huì)按照二叉搜索樹(shù)的規(guī)則去插入，結(jié)構(gòu)類(lèi)似于上文的第一個(gè)樹(shù)圖。
樹(shù)的遍歷
訪(fǎng)問(wèn)樹(shù)的所有節(jié)點(diǎn)有三種遍歷方式：中序，先序和后序。
- 中序遍歷：以從最小到最大的順序訪(fǎng)問(wèn)所有節(jié)點(diǎn)
- 先序遍歷：以?xún)?yōu)先于后代節(jié)點(diǎn)的順序訪(fǎng)問(wèn)每個(gè)節(jié)點(diǎn)
- 后序遍歷：先訪(fǎng)問(wèn)節(jié)點(diǎn)的后代節(jié)點(diǎn)再訪(fǎng)問(wè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ì)樹(shù)進(jìn)行從小到大排序的功能。
2 先序排序
- // 先序排序 --- 優(yōu)先于后代節(jié)點(diǎn)的順序訪(fǎng)問(wè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ù)遍歷 --- 先訪(fǎng)問(wèn)后代節(jié)點(diǎn)，再訪(fǎng)問(wè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)系的所有元素的大小。
搜索樹(shù)中的值
在樹(shù)中有三種經(jīng)常執(zhí)行的搜索類(lèi)型：最大值，最小值，特定的值。
1 最小值
最小值通過(guò)定義可以知道即是左側(cè)樹(shù)的最底端的節(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è)特定的值
- // 搜索樹(shù)中某個(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è)頁(yè)節(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類(lèi)似的實(shí)現(xiàn)去寫(xiě)一個(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)刪除。
至此，一個(gè)二叉搜索樹(shù)已經(jīng)實(shí)現(xiàn)，但是還存在一個(gè)問(wèn)題，如果樹(shù)的一遍非常深，將會(huì)存在一定的性能問(wèn)題，為了解決這個(gè)問(wèn)題，我們可以利用AVL樹(shù)，一種自平衡二叉樹(shù)，也就是說(shuō)任何一個(gè)節(jié)點(diǎn)的左右兩側(cè)子樹(shù)的高度之差最多為1。
