JavaScript實現簡單二叉查找樹

frank_fun 發布于2019-08-23 10:38 / 1693人閱讀

摘要：二叉查找樹二叉查找樹也叫二叉搜索樹它只允許我們在左節點存儲比父節點更小的值，右節點存儲比父節點更大的值，上圖展示的就是一顆二叉查找樹。

前兩天接到了螞蟻金服的面試電話，面試官很直接，上來就拋出了三道算法題。。。

其中有一道關于二叉樹實現中序遍歷的，當時沒回答好，所以特意學習了一把二叉樹的知識，行文記錄總結。

二叉樹&二叉查找樹

樹相關術語：

節點：樹中的每個元素稱為一個節點，

根節點：位于整棵樹頂點的節點，它沒有父節點，如上圖 5

子節點：其他節點的后代

葉子節點: 沒有子節點的元素稱為葉子節點，如上圖 3 8 24

二叉樹：二叉樹就是一種數據結構，它的組織關系就像是自然界中的樹一樣。官方語言的定義是：是一個有限元素的集合,該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。

二叉查找樹：
二叉查找樹也叫二叉搜索樹（BST）,它只允許我們在左節點存儲比父節點更小的值，右節點存儲比父節點更大的值，上圖展示的就是一顆二叉查找樹。

代碼實現

首先創建一個類來表示二叉查找樹，它的內部應該有一個Node類，用來創建節點

    function BinarySearchTree () {
        var Node = function(key) {
            this.key = key,
            this.left = null,
            this.right = null
        }
        var root = null
    }

它還應該有一些方法：

insert(key) 插入一個新的鍵

inOrderTraverse() 對樹進行中序遍歷，并打印結果

preOrderTraverse() 對樹進行先序遍歷，并打印結果

postOrderTraverse() 對樹進行后序遍歷，并打印結果

search(key) 查找樹中的鍵，如果存在返回true,不存在返回fasle

findMin() 返回樹中的最小值

findMax() 返回樹中的最大值

remove(key) 刪除樹中的某個鍵

向樹中插入一個鍵

向樹中插入一個新的鍵，首頁應該創建一個用來表示新節點的Node類實例，因此需要new一下Node類并傳入需要插入的key值，它會自動初始化為左右節點為null的一個新節點

然后，需要做一些判斷，先判斷樹是否為空，若為空，新插入的節點就作為根節點，如不為空，調用一個輔助方法insertNode()方法，將根節點和新節點傳入

    this.insert = function(key) {
        var newNode = new Node(key)
        if(root === null) {
            root = newNode
        } else {
            insertNode(root, newNode)
        }
    }

定義一下insertNode() 方法，這個方法會通過遞歸得調用自身，來找到新添加節點的合適位置

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

完成中序遍歷方法

要實現中序遍歷，我們需要一個inOrderTraverseNode(node)方法，它可以遞歸調用自身來遍歷每個節點

    this.inOrderTraverse = function() {
        inOrderTraverseNode(root)
    }

這個方法會打印每個節點的key值，它需要一個遞歸終止條件————檢查傳入的node是否為null，如果不為空，就繼續遞歸調用自身檢查node的left、right節點
實現起來也很簡單:

    var inOrderTraverseNode = function(node) {
        if (node !== null) {
            inOrderTraverseNode(node.left)
            console.log(node.key)
            inOrderTraverseNode(node.right)
        }
    }

先序遍歷、后序遍歷

有了中序遍歷的方法，只需要稍作改動，就可以實現先序遍歷和后序遍歷了
上代碼：

這樣就可以對整棵樹進行中序遍歷了

    // 實現先序遍歷
    this.preOrderTraverse = function() {
        preOrderTraverseNode(root)
    }
    var preOrderTraverseNode = function(node) {
        if (node !== null) {
            console.log(node.key)
            preOrderTraverseNode(node.left)
            preOrderTraverseNode(node.right)
        }
    }

    // 實現后序遍歷
    this.postOrderTraverse = function() {
        postOrderTraverseNode(root)
    }
    var postOrderTraverseNode = function(node) {
        if (node !== null) {
            postOrderTraverseNode(node.left)
            postOrderTraverseNode(node.right)
            console.log(node.key)
        }
    }

發現了吧，其實就是內部語句更換了前后位置，這也剛好符合三種遍歷規則：先序遍歷（根-左-右）、中序遍歷（左-根-右）、中序遍歷（左-右-根）

先來做個測試吧

現在的完整代碼如下：

    function BinarySearchTree () {
        var Node = function(key) {
            this.key = key,
            this.left = null,
            this.right = null
        }
        var root = null
        
        //插入節點
        this.insert = function(key) {
            var newNode = new Node(key)
            if(root === null) {
                root = newNode
            } else {
                insertNode(root, newNode)
            }
        }
        var insertNode = function(node, newNode) {
            if (newNode.key <= node.key) {
                if (node.left === null) {
                    node.left = newNode
                }else {
                    insertNode(node.left, newNode)
                }
            }else {
                if (node.right === null) {
                    node.right = newNode
                }else {
                    insertNode(node.right, newNode)
                }
            }
        } 
        
        //實現中序遍歷
        this.inOrderTraverse = function() {
            inOrderTraverseNode(root)
        }
        var inOrderTraverseNode = function(node) {
            if (node !== null) {
                inOrderTraverseNode(node.left)
                console.log(node.key)
                inOrderTraverseNode(node.right)
            }
        }
        // 實現先序遍歷
        this.preOrderTraverse = function() {
            preOrderTraverseNode(root)
        }
        var preOrderTraverseNode = function(node) {
            if (node !== null) {
                console.log(node.key)
                preOrderTraverseNode(node.left)
                preOrderTraverseNode(node.right)
            }
        }

        // 實現后序遍歷
        this.postOrderTraverse = function() {
            postOrderTraverseNode(root)
        }
        var postOrderTraverseNode = function(node) {
            if (node !== null) {
                postOrderTraverseNode(node.left)
                postOrderTraverseNode(node.right)
                console.log(node.key)
            }
        }
    }

竟然已經完成了添加新節點和遍歷的方式，我們來測試一下吧：

定義一個數組，里面有一些元素

var arr = [9,6,3,8,12,15]

我們將arr中的每個元素依此插入到二叉搜索樹中，然后打印結果

    var tree = new BinarySearchTree()
    arr.map(item => {
        tree.insert(item)
    })
    tree.inOrderTraverse()
    tree.preOrderTraverse()
    tree.postOrderTraverse()

運行代碼后，我們先來看看插入節點后整顆樹的情況：

輸出結果

中序遍歷：

3
6
8
9
12
15

先序遍歷：

9
6
3
8
12
15

后序遍歷：

3
8
6
15
12
9

很明顯，結果是符合預期的，所以，我們用上面的JavaScript代碼，實現了對樹的節點插入，和三種遍歷方法，同時，很明顯可以看到，在二叉查找樹樹種，最左側的節點的值是最小的，而最右側的節點的值是最大的，所以二叉查找樹可以很方便的拿到其中的最大值和最小值

查找最小、最大值

怎么做呢？其實只需要將根節點傳入minNode/或maxNode方法，然后通過循環判斷node為左側(minNode)/右側(maxNode)的節點為null

實現代碼：

    // 查找最小值
    this.findMin = function() {
        return minNode(root)
    }
    var minNode = function(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    
    // 查找最大值
    this.findMax = function() {
        return maxNode(root)
    }
    var maxNode = function (node) {
        if(node) {
            while (node && node.right !== null) {
                node =node.right
            }
            return node.key
        }
        return null
    }

所搜特定值

this.search = function(key) {
    return searchNode(root, key)
}

同樣，實現它需要定義一個輔助方法,這個方法首先會檢驗node的合法性，如果為null，直接退出，并返回fasle。如果傳入的key比當前傳入node的key值小，它會繼續遞歸查找node的左側節點，反之，查找右側節點。如果找到相等節點，直接退出，并返回true

    var searchNode = function(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
        }
    }

移除節點

移除節點的實現情況比較復雜，它會有三種不同的情況：

需要移除的節點是一個葉子節點

需要移除的節點包含一個子節點

需要移除的節點包含兩個子節點

和實現搜索指定節點一元，要移除某個節點，必須先找到它所在的位置，因此移除方法的實現中部分代碼和上面相同：

    // 移除節點
    this.remove = function(key) {
        removeNode(root,key)
    }
    var removeNode = function(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{
            //需要移除的節點是一個葉子節點
            if (node.left === null && node.right === null) {
                node = null
                return node
            }
            //需要移除的節點包含一個子節點
            if (node.letf === null) {
                node = node.right
                return node
            }else if (node.right === null) {
                node = node.left
                return node
            }
            //需要移除的節點包含兩個子節點
            var aux = findMinNode(node.right)
            node.key = aux.key
            node.right = removeNode(node.right, axu.key)
            return node
        }
    }
    var findMinNode = function(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node
        }
        return null
    }

其中，移除包含兩個子節點的節點是最復雜的情況，它包含左側節點和右側節點，對它進行移除主要需要三個步驟：

需要找到它右側子樹中的最小節點來代替它的位置

將它右側子樹中的最小節點移除

將更新后的節點的引用指向原節點的父節點

有點繞兒，但必須這樣，因為刪除元素后的二叉搜索樹必須保持它的排序性質

測試刪除節點

tree.remove(8)
tree.inOrderTraverse()

打印結果：

3
6
9
12
15

8 這個節點被成功刪除了，但是對二叉查找樹進行中序遍歷依然是保持排序性質的

到這里，一個簡單的二叉查找樹就基本上完成了，我們為它實現了，添加、查找、刪除以及先中后三種遍歷方法

存在的問題

但是實際上這樣的二叉查找樹是存在一些問題的，當我們不斷的添加更大/更小的元素的時候，會出現如下情況：

tree.insert(16)
tree.insert(17)
tree.insert(18)

來看看現在整顆樹的情況：

很容易發現，它是不平衡的，這又會引出平衡樹的概念，要解決這個問題，還需要更復雜的實現，例如：AVL樹，紅黑樹哎，之后再慢慢去學習吧

關于實現二叉排序樹，我也找到慕課網的一系列的視頻：Javascript實現二叉樹算法,
內容和上述實現基本一致

原文鏈接：行無忌的成長小屋：JavaScript實現簡單二叉查找樹

云服務器 GPU云服務器二叉查找樹二叉查找樹刪除結點二叉樹排序樹規則二叉排序樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/96548.html

學習javascript數據結構(四)——樹

摘要：原文博客地址學習數據結構四樹知乎專欄簡書專題前端進擊者知乎前端進擊者簡書博主博客地址的個人博客人之所能，不能兼備，棄其所短，取其所長。通常子樹被稱作左子樹和右子樹。敬請期待數據結構篇最后一篇文章學習數據結構五圖參考文章樹數據結構二叉樹前言總括：本文講解了數據結構中的[樹]的概念，盡可能通俗易懂的解釋樹這種數據結構的概念，使用javascript實現了樹，如有紕漏，歡迎批評指正。 ...

Dean 2019-08-20 13:47 評論0 收藏0
JavaScript 數據結構與算法之美 - 非線性表中的樹、堆是干嘛用的？其數據結構是怎樣的？

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。非線性表中的樹堆是干嘛用的其數據結構是怎樣的希望大家帶著這兩個問題閱讀下文。其中，前中后序，表示的是節點與它的左右子樹節點遍歷訪問的先后順序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言想學好前端，先練好內功，內功不行，...

singerye 2019-08-26 10:09 評論0 收藏0
數據結構與算法:二叉樹算法

摘要：因此，根據題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數據結構與算法描述實現二叉樹算法淺談數據結構二叉樹慕課網實現二叉樹算法前端樹控件騰訊軟件開發面試題內容銜接上一章數據結構與算法:常見排序算法內容提要什么是樹　　- 為什么使用樹二叉樹二叉查找樹紅黑樹Ｂ、Ｂ＋樹堆伸展樹樹可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...

Little_XM 2019-08-22 11:09 評論0 收藏0
JavaScript算法之二叉搜索樹

摘要：二叉搜索樹的特性二叉搜索樹由于其獨特的數據結構，使得其無論在增刪，還是查找，時間復雜度都是，為二叉樹的高度。二叉搜索樹的查找查找很簡單，根據左子節點比該節點小，右子節點比該節點大的原則進行循環判斷即可。什么是二叉樹二叉樹就是樹的每個節點最多只能有兩個子節點什么是二叉搜索樹二叉搜索樹在二叉樹的基礎上，多了一個條件，就是二叉樹在插入值時，若插入值比當前節點小，就插入到左節點，否則插...

khlbat 2019-08-21 16:26 評論0 收藏0
數據結構與算法對的javaScript描述-二叉搜索樹

摘要：定義樹以及相關概念二叉搜索樹的定義首先是二叉樹最多有兩個節點，分別是左右節點子節點的位置是確定的，變現為左子節點的值小于其父節點右子節點的值大于其父節點在中的描述描述的完整代碼傳送門可視化傳送門節點類樹是由節點組成的，要實現樹那么先要實現節定義樹以及相關概念 showImg(https://segmentfault.com/img/remote/1460000012578627?w...

forrest23 2019-08-21 18:24 評論0 收藏0