数据结构TypeScript之二叉查找树实现详解

时间:2023-02-03 前端技术獭人气:0

树的结构特点

树是一种有层次的数据结构，通常用于存储具有层次性的数据。比如上下级的关系图，动物的分类图等。树的类型分好几种，无序树、有序树和二叉树等等。但最常应用的还是二叉树，其特点为每个节点最多含有两个子树。

尝试手动构建一颗二叉树。

过程如下：

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)
// 输出二叉树结构：
// {
//     element: 1,
//     left: { element: 2, left: null, rgiht: null },
//     right: { element: 3, left: null, rgiht: null },
// }

面向对象方法封装二叉查找树（迭代版）

二叉查找树的定义

它或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉查找树。

构造函数

基本单元：二叉查找树节点

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

增加节点

实现思路：根据二叉查找树的有序性能够让节点不断接近它合适的插入位置。

在此之前收集的两个条件如下：

已知index的值大小。
二叉查找树的左子树节点值都比根节点值小，右子树节点值都比根节点值大。

接下来就需要利用上面这两个条件，将传入的index参数不断与树中已存在的节点的index进行大小比较。直到它在树中找到合适的位置，执行新节点的插入操作。

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
}

查找节点

实现思路：让待查找节点值在遍历过程中不断接近结果。

如果当前节点不为空，在未到达叶子节点之前仍需对这颗树进行遍历，直到找到值。

如果遍历已到达叶子节点，都没有找到值。说明值根本就不存在，我们直接终止遍历。

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

删除节点

删除的方法依然是在迭代的基础上，需要考虑四种不同节点情况，分别如下：

叶子节点：没有左右子树的节点，节点直接置空。
只带左子树的节点：让它的左节点覆盖待删除节点。
只带右子树的节点：让它的右节点覆盖待删除节点。
带左右子树的节点：为保证二叉树的有序性，一般将待删除节点值替换为它右子树的最小值。

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方法：查找当前节点的右子树最小值

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

remove方法：若index有效，遍历将会到达待删除节点的前一个节点，执行removeNode方法删除节点

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

注意：我们的需求是让二叉树查找树中待删除节点的前一个节点属性发生改变，让实例对象产生引用值的特点从而实现删除的效果。如果我们直接遍历到被删除节点，无论对这个节点（变量）作任何修改，都不会反映到实例对象上。来看下面的例子：

let a = { name: "小明", age: 20 }
let b = a       // a和b指向同一地址
b.age = null    // 此时产生效果，a.age也会变为null
b = null        // b被重新赋值，a和b不会指向同一地址。所以a不会变为null

二叉树的遍历

递归实现如下：

前序遍历（根左右）

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

迭代实现如下：

前序遍历（根左右）

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
}

层序遍历（广度优先搜索）

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
}

至此已完成二叉查找树的增删查和遍历方法，迭代实现的优势在于JavaScript每调用一个函数就会产生一个执行上下文将其推入函数调用栈中。如果我们构建的二叉查找树十分的高，递归就有可能出现爆栈问题。

本文相关代码已放置我的Github仓库

加载全部内容