javascript封裝二叉搜尋樹（BST）

二叉搜尋樹(Binary Search Tree) 特點： 1、若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值 2、若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值.

如圖示：

二叉搜尋樹的插入節點：

//插入資料
    BinarySearchTree.prototype.insert = function (key) {
        let newNode = new Node(key)  //建立新節點

        //判斷跟節點是否有值
        if (this.root === null) {
            this.root = newNode
        } else {
            this.insertNode(this.root,newNode)
        }

    }

    //遞歸尋找适合的節點插入新節點
    BinarySearchTree.prototype.insertNode = function (node,newNode) {
        if (newNode.key < node.key) { //向左查找
            if (node.left === null) {
                node.left = newNode
            } else {
                this.insertNode(node.left,newNode)
            }
        } else { //向右查找
            if (node.right === null) {
                node.right = newNode
            } else {
                this.insertNode(node.right,newNode)
            }
        }
    }

二叉搜尋樹的三種周遊方式：

先序周遊：

javascript封裝二叉搜尋樹（BST）

代碼遞歸實作：

//先序周遊的遞歸函數
    BinarySearchTree.prototype.preOrderTraversalNode = function (node) {
        if (node !== null) {
            console.log(node.key) //列印周遊的節點的值
            this.preOrderTraversalNode(node.left) //處理左節點
            this.preOrderTraversalNode(node.right) //處理右節點
        }
    }

中序周遊

javascript封裝二叉搜尋樹（BST）

代碼遞歸實作：

//中序周遊的遞歸函數
    BinarySearchTree.prototype.midOrderTraversalNode = function (node) {
        if (node !== null) {
            this.midOrderTraversalNode(node.left)
            console.log(node.key)
            this.midOrderTraversalNode(node.right)
        }
    }

後序周遊

javascript封裝二叉搜尋樹（BST）

代碼遞歸實作：

//後序周遊的遞歸函數
    BinarySearchTree.prototype.postOrderTraversalNode = function (node) {

        if (node !== null) {
            this.postOrderTraversalNode(node.left)

            this.postOrderTraversalNode(node.right)
            console.log(node.key)
        }
    }

二叉搜尋樹的最大值和最小值：

//最小值
    BinarySearchTree.prototype.min = function () {
        let node = this.root

        while (node.left !== null) {
            node = node.left
        }
        return node.key
    }

    //最大值
    BinarySearchTree.prototype.max = function () {
        let node = this.root

        while (node.right !== null) {
            node = node.right
        }
        return node.key
    }

二叉搜尋樹尋找特定的值

//尋找特定的值
    BinarySearchTree.prototype.search = function (key) {
        return this.searchNode(this.root,key)
    }

    //遞歸尋找特定的值
    BinarySearchTree.prototype.searchNode = function (node,key) {
        if (node === null) { 
            return false
        }
        if (node.key > key) {
           return this.searchNode(node.left,key)
        } else if (node.key < key) {
            return this.searchNode(node.right,key)
        } else {
            return true
        }

删除節點：有三種情況 1、删除葉子節點 2、删除隻有一個子節點的節點3、删除有兩個子節點的節點

//删除節點
    BinarySearchTree.prototype.remove = function (key) {
        //1、找到要删除的節點
        //2、定義變量 儲存資訊
        let current = this.root
        let parent = null
        let isLeftChild = true //标記要删除的節點是父節點的左子節點還是右子節點

        //開始尋找删除的節點
        while (current.key !== key) {
            parent = current
            if (key < current.key) {
                isLeftChild = true
                current = current.left
            } else {
                isLeftChild = false
                current = current.right
            }
            if (current === null) return false //不存在 要删除的節點
        }

        //删除的是葉子節點
        if (current.left === null && current.right === null) {
            if (current === this.root) {
                this.root = null
            } else if (isLeftChild) {
                parent.left = null
            } else {
                parent.right = null
            }
        }

        //删除隻有一個子節點的節點
       else if (current.right === null) { //current 沒有右子節點
           if (current === this.root) {
               this.root = current.left
           } else if (isLeftChild) {
               parent.left = current.left
           } else {
               parent.right = current.left
           }
        }
       else if (current.left === null) { //current 沒有左子節點
           if (current === this.root) {
               this.root = current.right
           } else if (isLeftChild) {
               parent.left = current.right
           } else {
               parent.right = current.right
           }
        }
       else { //删除的節點有兩個子節點
           //擷取後繼節點
           let successor = this.getSuccessor(current)

            if (current === this.root) {
                this.root = successor
            } else if (isLeftChild) {
                parent.left = successor
            } else {
                parent.right = successor
            }
           //将删除節點的左子樹 = current.left
            successor.left = current.left
        }
    }

    //尋找後繼的辦法
    BinarySearchTree.prototype.getSuccessor = function (delNode) {
        //定義變量 儲存找到的後繼
        let successor = delNode
        let current = delNode.right
        let successorParent = delNode

        //循環查找
        while (current !== null) { //找到delNode右邊最小值的節點 為後繼節點
            successorParent = successor
            successor = current
            current = current.left
        }
        //判斷尋找的後繼節點是否直接就是delNode的right節點
        if (successor !== delNode.right) {
            successorParent.left = successor.right
            successor.right = delNode.right
        }

        return successor
    }

整體代碼

//封裝二叉搜尋樹
function BinarySearchTree() {

    //内部節點類
    function Node(key) {
        this.left = null
        this.key = key
        this.right = null
    }

    this.root = null

    //插入資料
    BinarySearchTree.prototype.insert = function (key) {
        let newNode = new Node(key)  //建立新節點

        //判斷跟節點是否有值
        if (this.root === null) {
            this.root = newNode
        } else {
            this.insertNode(this.root,newNode)
        }

    }

    //遞歸尋找适合的節點插入新節點
    BinarySearchTree.prototype.insertNode = function (node,newNode) {
        if (newNode.key < node.key) { //向左查找
            if (node.left === null) {
                node.left = newNode
            } else {
                this.insertNode(node.left,newNode)
            }
        } else { //向右查找
            if (node.right === null) {
                node.right = newNode
            } else {
                this.insertNode(node.right,newNode)
            }
        }
    }

    //先序周遊
    BinarySearchTree.prototype.preOrderTraversal = function () {
        this.preOrderTraversalNode(this.root)
    }

    //先序周遊的遞歸函數
    BinarySearchTree.prototype.preOrderTraversalNode = function (node) {

        if (node !== null) {
            console.log(node.key) //列印周遊的節點的值
            this.preOrderTraversalNode(node.left) //處理左節點
            this.preOrderTraversalNode(node.right) //處理右節點
        }

    }

    //中序周遊
    BinarySearchTree.prototype.midOrderTraversal = function () {
        this.midOrderTraversalNode(this.root)
    }

    //中序周遊的遞歸函數
    BinarySearchTree.prototype.midOrderTraversalNode = function (node) {

        if (node !== null) {
            this.midOrderTraversalNode(node.left)
            console.log(node.key)
            this.midOrderTraversalNode(node.right)
        }
    }

    //後序周遊
    BinarySearchTree.prototype.postOrderTraversal = function () {
        this.postOrderTraversalNode(this.root)
    }

    //後序周遊的遞歸函數
    BinarySearchTree.prototype.postOrderTraversalNode = function (node) {

        if (node !== null) {
            this.postOrderTraversalNode(node.left)

            this.postOrderTraversalNode(node.right)
            console.log(node.key)
        }
    }

    //最小值
    BinarySearchTree.prototype.min = function () {
        let node = this.root

        while (node.left !== null) {
            node = node.left
        }
        return node.key
    }

    //最大值
    BinarySearchTree.prototype.max = function () {
        let node = this.root

        while (node.right !== null) {
            node = node.right
        }
        return node.key
    }

    //尋找特定的值
    BinarySearchTree.prototype.search = function (key) {
        return this.searchNode(this.root,key)
    }

    //遞歸尋找特定的值
    BinarySearchTree.prototype.searchNode = function (node,key) {
        if (node === null) {
            return false
        }
        if (node.key > key) {
           return this.searchNode(node.left,key)
        } else if (node.key < key) {
            return this.searchNode(node.right,key)
        } else {
            return true
        }

    }

    //删除節點
    BinarySearchTree.prototype.remove = function (key) {
        //1、找到要删除的節點
        //2、定義變量 儲存資訊
        let current = this.root
        let parent = null
        let isLeftChild = true //标記要删除的節點是父節點的左子節點還是右子節點

        //開始尋找删除的節點
        while (current.key !== key) {
            parent = current
            if (key < current.key) {
                isLeftChild = true
                current = current.left
            } else {
                isLeftChild = false
                current = current.right
            }
            if (current === null) return false //不存在 要删除的節點
        }

        //删除的是葉子節點
        if (current.left === null && current.right === null) {
            if (current === this.root) {
                this.root = null
            } else if (isLeftChild) {
                parent.left = null
            } else {
                parent.right = null
            }
        }

        //删除隻有一個子節點的節點
       else if (current.right === null) { //current 沒有右子節點
           if (current === this.root) {
               this.root = current.left
           } else if (isLeftChild) {
               parent.left = current.left
           } else {
               parent.right = current.left
           }
        }
       else if (current.left === null) { //current 沒有左子節點
           if (current === this.root) {
               this.root = current.right
           } else if (isLeftChild) {
               parent.left = current.right
           } else {
               parent.right = current.right
           }
        }
       else { //删除的節點有兩個子節點
           //擷取後繼節點
           let successor = this.getSuccessor(current)

            if (current === this.root) {
                this.root = successor
            } else if (isLeftChild) {
                parent.left = successor
            } else {
                parent.right = successor
            }
           //将删除節點的左子樹 = current.left
            successor.left = current.left
        }
    }

    //尋找後繼的辦法
    BinarySearchTree.prototype.getSuccessor = function (delNode) {
        //定義變量 儲存找到的後繼
        let successor = delNode
        let current = delNode.right
        let successorParent = delNode

        //循環查找
        while (current !== null) { //找到delNode右邊最小值的節點 為後繼節點
            successorParent = successor
            successor = current
            current = current.left
        }
        //判斷尋找的後繼節點是否直接就是delNode的right節點
        if (successor !== delNode.right) {
            successorParent.left = successor.right
            successor.right = delNode.right
        }

        return successor
    }
}

const  bst = new BinarySearchTree()

bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)

//測試周遊

bst.preOrderTraversal()
bst.midOrderTraversal()
bst.postOrderTraversal()

console.log(bst.min());
console.log(bst.max());

console.log(bst.search(25))
console.log(bst.search(100))
console.log(bst.search(7))


bst.remove(7)
bst.remove(15)
bst.remove(10)
bst.postOrderTraversal()

javascript封裝二叉搜尋樹（BST）

繼續閱讀

D. Ehab the Xorcist(構造+思維)

關于 underscore 中模闆引擎的應用示例

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【JavaScript文法】函數對象的淺拷貝、深拷貝

【資料結構】醫院選址

JS--運算符

數組和類數組

[轉]ISUP信令的IAM消息詳細内容

jquery_126_demo

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器