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

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

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

樹的結(jié)構(gòu)特點

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

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

過程如下：

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)
// 輸出二叉樹結(jié)構(gòu)：
// {
//     element: 1,
//     left: { element: 2, left: null, rgiht: null },
//     right: { element: 3, left: null, rgiht: null },
// }

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

二叉查找樹的定義

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

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

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

基本單元：二叉查找樹節(jié)點

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
    }
}

主體：二叉查找樹

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

增加節(jié)點

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

在此之前收集的兩個條件如下：

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

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

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é)點

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

如果當前節(jié)點不為空，在未到達葉子節(jié)點之前仍需對這顆樹進行遍歷，直到找到值。

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

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é)點

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

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

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方法：查找當前節(jié)點的右子樹最小值

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

remove方法：若index有效，遍歷將會到達待刪除節(jié)點的前一個節(jié)點，執(zhí)行removeNode方法刪除節(jié)點

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
    }
}

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

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

二叉樹的遍歷

遞歸實現(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 })
    }
}

層序遍歷（層級記錄）

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) }
}

迭代實現(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
}

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

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

項目地址：

Algorithmlib｜BinarySearchTree

Algorithmlib｜BinaryTree Traversal

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

您可能感興趣的文章: