數(shù)據(jù)結(jié)構(gòu)TypeScript之二叉查找樹(shù)實(shí)現(xiàn)詳解

更新時(shí)間：2023年01月30日 09:48:37 作者：前端技術(shù)獺

這篇文章主要為大家介紹了數(shù)據(jù)結(jié)構(gòu)TypeScript之二叉查找樹(shù)實(shí)現(xiàn)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

樹(shù)的結(jié)構(gòu)特點(diǎn)

樹(shù)是一種有層次的數(shù)據(jù)結(jié)構(gòu)，通常用于存儲(chǔ)具有層次性的數(shù)據(jù)。比如上下級(jí)的關(guān)系圖，動(dòng)物的分類圖等。樹(shù)的類型分好幾種，無(wú)序樹(shù)、有序樹(shù)和二叉樹(shù)等等。但最常應(yīng)用的還是二叉樹(shù)，其特點(diǎn)為每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹(shù)。

嘗試手動(dòng)構(gòu)建一顆二叉樹(shù)。

過(guò)程如下：

class BinaryTreeNode {
    constructor(element) {
        this.element = element
        this.left = null
        this.right = null
    }
}
let n1 = new BinaryTreeNode(1)
let n2 = new BinaryTreeNode(2)
let n3 = new BinaryTreeNode(3)
n1.left = n2
n1.right = n3
console.log(n1)
// 輸出二叉樹(shù)結(jié)構(gòu)：
// {
//     element: 1,
//     left: { element: 2, left: null, rgiht: null },
//     right: { element: 3, left: null, rgiht: null },
// }

面向?qū)ο蠓椒ǚ庋b二叉查找樹(shù)（迭代版）

二叉查找樹(shù)的定義

它或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：

若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
它的左、右子樹(shù)也分別為二叉查找樹(shù)。

構(gòu)造函數(shù)

基本單元：二叉查找樹(shù)節(jié)點(diǎn)

class BinarySearchTreeNode {
    index: number
    element: any
    left: (null | BinarySearchTreeNode)
    right: (null | BinarySearchTreeNode)
    constructor(index: number, element: any) {
        this.index = index
        this.element = element
        this.left = null
        this.right = null
    }
}

主體：二叉查找樹(shù)

class BinarySearchTree {
    length: number
    root: (null | BinarySearchTreeNode)
    constructor() {
        this.length = 0
        this.root = null
    }
}

增加節(jié)點(diǎn)

實(shí)現(xiàn)思路：根據(jù)二叉查找樹(shù)的有序性能夠讓節(jié)點(diǎn)不斷接近它合適的插入位置。

在此之前收集的兩個(gè)條件如下：

已知index的值大小。
二叉查找樹(shù)的左子樹(shù)節(jié)點(diǎn)值都比根節(jié)點(diǎn)值小，右子樹(shù)節(jié)點(diǎn)值都比根節(jié)點(diǎn)值大。

接下來(lái)就需要利用上面這兩個(gè)條件，將傳入的index參數(shù)不斷與樹(shù)中已存在的節(jié)點(diǎn)的index進(jìn)行大小比較。直到它在樹(shù)中找到合適的位置，執(zhí)行新節(jié)點(diǎn)的插入操作。

insert(index: number, element: any = null): BinarySearchTree {
    if (this.root === null) {
        this.root = new BinarySearchTreeNode(index, element)
    } else {
        let node: (null | BinarySearchTreeNode) = this.root
        while (1) {
            if (index === node!.index) {
                throw new Error(`${index} already exists`)
            } else if (index < node!.index) {
                if (node!.left === null) {
                    node!.left = new BinarySearchTreeNode(index, element)
                    break
                }
                node = node!.left
            } else if (index > node!.index) {
                if (node!.right === null) {
                    node!.right = new BinarySearchTreeNode(index, element)
                    break
                }
                node = node!.right
            }
        }
    }
    this.length++
    return this
}

查找節(jié)點(diǎn)

實(shí)現(xiàn)思路：讓待查找節(jié)點(diǎn)值在遍歷過(guò)程中不斷接近結(jié)果。

如果當(dāng)前節(jié)點(diǎn)不為空，在未到達(dá)葉子節(jié)點(diǎn)之前仍需對(duì)這顆樹(shù)進(jìn)行遍歷，直到找到值。

如果遍歷已到達(dá)葉子節(jié)點(diǎn)，都沒(méi)有找到值。說(shuō)明值根本就不存在，我們直接終止遍歷。

search(index: number): (void | boolean) {
    if (this.isEmpty()) {
        throw new Error('BinarySearchTree is empty')
    } else {
        let node: (null | BinarySearchTreeNode) = this.root
        while (node !== null) {
            if (index === node!.index) {
                return true
            } else if (index &lt; node!.index) {
                node = node!.left
            } else if (index &gt; node!.index) {
                node = node!.right
            }
        }
        if (!node) { return false }
    }
}

刪除節(jié)點(diǎn)

刪除的方法依然是在迭代的基礎(chǔ)上，需要考慮四種不同節(jié)點(diǎn)情況，分別如下：

葉子節(jié)點(diǎn)：沒(méi)有左右子樹(shù)的節(jié)點(diǎn)，節(jié)點(diǎn)直接置空。
只帶左子樹(shù)的節(jié)點(diǎn)：讓它的左節(jié)點(diǎn)覆蓋待刪除節(jié)點(diǎn)。
只帶右子樹(shù)的節(jié)點(diǎn)：讓它的右節(jié)點(diǎn)覆蓋待刪除節(jié)點(diǎn)。
帶左右子樹(shù)的節(jié)點(diǎn)：為保證二叉樹(shù)的有序性，一般將待刪除節(jié)點(diǎn)值替換為它右子樹(shù)的最小值。

removeNode(node: (null | BinarySearchTreeNode)): (null | BinarySearchTreeNode) {
    if (node!.right === null && node!.left === null) {
        node = null
    } else if (node!.right === null) {
        node = node!.left
    } else if (node!.left === null) {
        node = node!.right
    } else if (node!.right !== null && node!.left !== null) {
        let temp: (null | BinarySearchTreeNode) = this.minNode(node!.right)
        this.remove(temp!.index)
        node!.index = temp!.index
        node!.element = temp!.element
        this.length++
    }
    return node
}

minNode方法：查找當(dāng)前節(jié)點(diǎn)的右子樹(shù)最小值

minNode(node: (null | BinarySearchTreeNode)): (null | BinarySearchTreeNode) {
    while (node!.left !== null) {
        node = node!.left
    }
    return node
}

remove方法：若index有效，遍歷將會(huì)到達(dá)待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，執(zhí)行removeNode方法刪除節(jié)點(diǎn)

remove(index: number): BinarySearchTree {
    if (this.isEmpty()) {
        throw new Error('BinarySearchTree is empty')
    } else {
        let node: (null | BinarySearchTreeNode) = this.root
        while (node !== null) {
            if (index === node!.index) {
                this.root = this.removeNode(node)
                break
            } else if (node!.left !== null && index === node!.left.index) {
                node!.left = this.removeNode(node!.left)
                break
            } else if (node!.right !== null && index === node!.right.index) {
                node!.right = this.removeNode(node!.right)
                break
            } else if (index < node!.index) {
                node = node!.left
            } else if (index > node!.index) {
                node = node!.right
            }
        }
        if (!node) { throw new Error(`${index} does not exist`) }
        this.length--
        return this
    }
}

注意：我們的需求是讓二叉樹(shù)查找樹(shù)中待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)屬性發(fā)生改變，讓實(shí)例對(duì)象產(chǎn)生引用值的特點(diǎn)從而實(shí)現(xiàn)刪除的效果。如果我們直接遍歷到被刪除節(jié)點(diǎn)，無(wú)論對(duì)這個(gè)節(jié)點(diǎn)（變量）作任何修改，都不會(huì)反映到實(shí)例對(duì)象上。來(lái)看下面的例子：

let a = { name: "小明", age: 20 }
let b = a       // a和b指向同一地址
b.age = null    // 此時(shí)產(chǎn)生效果，a.age也會(huì)變?yōu)閚ull
b = null        // b被重新賦值，a和b不會(huì)指向同一地址。所以a不會(huì)變?yōu)閚ull

二叉樹(shù)的遍歷

遞歸實(shí)現(xiàn)如下：

前序遍歷（根左右）

export const preOrderTraversal = (tree: BinarySearchTree) => {
    let result: Array<{ index: number, element: any }> = []
    preOrderTraversalNode(tree!.root, result)
    return result
}
const preOrderTraversalNode = (
    node: (null | BinarySearchTreeNode),
    result: Array<{ index: number, element: any }>) => {
    if (node !== null) {
        result.push({ index: node!.index, element: node!.element })
        preOrderTraversalNode(node!.left, result)
        preOrderTraversalNode(node!.right, result)
    }
}

中序遍歷（左根右）

export const inOrderTraversal = (tree: BinarySearchTree) => {
    let result: Array<{ index: number, element: any }> = []
    inOrderTraversalNode(tree!.root, result)
    return result
}
const inOrderTraversalNode = (
    node: (null | BinarySearchTreeNode),
    result: Array<{ index: number, element: any }>) => {
    if (node !== null) {
        inOrderTraversalNode(node!.left, result)
        result.push({ index: node!.index, element: node!.element })
        inOrderTraversalNode(node!.right, result)
    }
}

后序遍歷（左右根）

export const postOrderTraversal = (tree: BinarySearchTree) => {
    let result: Array<{ index: number, element: any }> = []
    postOrderTraversalNode(tree!.root, result)
    return result
}
const postOrderTraversalNode = (
    node: (null | BinarySearchTreeNode),
    result: Array<{ index: number, element: any }>) => {
    if (node !== null) {
        postOrderTraversalNode(node!.left, result)
        postOrderTraversalNode(node!.right, result)
        result.push({ index: node!.index, element: node!.element })
    }
}

層序遍歷（層級(jí)記錄）

export const levelOrderTraversal = (tree: BinarySearchTree) => {
    let result: Array<Array<{ index: number, element: any }>> = []
    levelOrderTraversalNode(tree!.root, result, 0)
    return result
}
const levelOrderTraversalNode = (
    node: (null | BinarySearchTreeNode),
    result: Array<Array<{ index: number, element: any }>>, level: number) => {
    if (!result[level]) { result[level] = [] }
    result[level].push({ index: node!.index, element: node!.element })
    if (node!.left) { levelOrderTraversalNode(node!.left, result, level + 1) }
    if (node!.right) { levelOrderTraversalNode(node!.right, result, level + 1) }
}

迭代實(shí)現(xiàn)如下：

前序遍歷（根左右）

const preOrderTraversal = (tree: BinarySearchTree) => {
    let stack: Stack = new Stack()
    let node: (null | BinarySearchTreeNode) = tree!.root
    let result: Array<{ index: number, element: any }> = []
    while (node !== null || !stack.isEmpty()) {
        while (node !== null) {
            stack.push(node)
            result.push({ index: node!.index, element: node!.element })
            node = node!.left
        }
        node = stack.pop()
        node = node!.right
    }
    return result
}

中序遍歷（左根右）

const inOrderTraversal = (tree: BinarySearchTree) => {
    let stack: Stack = new Stack()
    let node: (null | BinarySearchTreeNode) = tree!.root
    let result: Array<{ index: number, element: any }> = []
    while (node !== null || !stack.isEmpty()) {
        while (node !== null) {
            stack.push(node)
            node = node!.left
        }
        node = stack.pop()
        result.push({ index: node!.index, element: node!.element })
        node = node!.right
    }
    return result
}

后序遍歷（左右根）

export const postOrderTraversal = (tree: BinarySearchTree) => {
    let stack: Stack = new Stack()
    let node: (null | BinarySearchTreeNode) = tree!.root
    let result: Array<{ index: number, element: any }> = []
    let prev: (null | BinarySearchTreeNode) = null
    while (node !== null || !stack.isEmpty()) {
        while (node !== null) {
            stack.push(node)
            node = node!.left
        }
        node = stack.pop()
        if (node!.right === null || node!.right === prev) {
            result.push({ index: node!.index, element: node!.element })
            prev = node
            node = null
        } else {
            stack.push(node)
            node = node!.right
        }
    }
    return result
}

層序遍歷（廣度優(yōu)先搜索）

const levelOrderTraversal = (tree: BinarySearchTree) => {
    let result: Array<Array<{ index: number, element: any }>> = []
    if (!(tree!.root)) { return result }
    let queue: Queue = new Queue()
    let node: (null | BinarySearchTreeNode) = tree!.root
    queue.enqueue(node)
    while (!queue.isEmpty()) {
        result.push([])
        const { length } = queue
        for (let i = 0; i < length; i++) {
            node = queue.dequeue()
            result[result.length - 1].push({ index: node!.index, element: node!.element })
            if (node!.left) { queue.enqueue(node!.left) }
            if (node!.right) { queue.enqueue(node!.right) }
        }
    }
    return result
}

至此已完成二叉查找樹(shù)的增刪查和遍歷方法，迭代實(shí)現(xiàn)的優(yōu)勢(shì)在于JavaScript每調(diào)用一個(gè)函數(shù)就會(huì)產(chǎn)生一個(gè)執(zhí)行上下文將其推入函數(shù)調(diào)用棧中。如果我們構(gòu)建的二叉查找樹(shù)十分的高，遞歸就有可能出現(xiàn)爆棧問(wèn)題。

本文相關(guān)代碼已放置我的Github倉(cāng)庫(kù) ??

項(xiàng)目地址：

Algorithmlib｜BinarySearchTree

Algorithmlib｜BinaryTree Traversal

以上就是數(shù)據(jù)結(jié)構(gòu)TypeScript之二叉查找樹(shù)實(shí)現(xiàn)詳解的詳細(xì)內(nèi)容，更多關(guān)于TypeScript數(shù)據(jù)結(jié)構(gòu)二叉查找樹(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: