SoFunction
Updated on 2025-03-04

Detailed explanation of the implementation of binary search tree of data structure TypeScript

Structural characteristics of the tree

TreeIt's a kindThere are layersdata structures, usually used forStorage is hierarchicalofdata. For example, the relationship diagram of superiors and subordinates, the classification diagram of animals, etc. There are several types of trees, such as unordered trees, ordered trees, binary trees, etc. But the most commonly used one isBinary Tree,ThatFeaturesforEach node contains up to two subtrees。

Try to build a binary tree manually.

The process is as follows:

class BinaryTreeNode {
    constructor(element) {
         = element
         = null
         = null
    }
}
let n1 = new BinaryTreeNode(1)
let n2 = new BinaryTreeNode(2)
let n3 = new BinaryTreeNode(3)
 = n2
 = n3
(n1)
// Output binary tree structure:// {
//     element: 1,
//     left: { element: 2, left: null, rgiht: null },
//     right: { element: 3, left: null, rgiht: null },
// }

Object-oriented method encapsulates binary search tree (iteration version)

Definition of binary search tree

It is either an empty tree or a binary tree with the following properties:

  • If it'sThe left subtree is not empty,butThe values ​​of all nodes on the left subtree are smaller than the values ​​of its root node；
  • If it'sThe right subtree is not empty,butThe values ​​of all nodes on the right subtree are greater than the values ​​of its root node；
  • Its left and right subtrees are also binary search trees respectively.

Constructor

Basic unit: Binary search tree node

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

Body: Binary search tree

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

Add nodes

Implementation idea: According to the order of the binary search tree, the node can be constantly approached to its appropriate insertion position.

The two conditions collected before this are as follows:

  • KnownindexThe value size of the .
  • Binary search treeThe values ​​of the left subtree node are smaller than the values ​​of the root node，The right subtree node value is larger than the root node value。

Next, you need to use the above two conditions to pass inindexParameters are constantly related to nodes that already exist in the treeindexMake a size comparison. Until it finds the right place in the tree, perform the insertion operation of the new node.

insert(index: number, element: any = null): BinarySearchTree {
    if ( === null) {
         = new BinarySearchTreeNode(index, element)
    } else {
        let node: (null | BinarySearchTreeNode) = 
        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
            }
        }
    }
    ++
    return this
}

Find nodes

Implementation idea: Let the node value to be found constantly approach the result during the traversal process.

If the current node is not empty, the tree needs to be traversed before reaching the leaf node until the value is found.

If the traversal has reached the leaf node, no value is found. It means that the value does not exist at all, so we directly terminate the traversal.

search(index: number): (void | boolean) {
    if (()) {
        throw new Error('BinarySearchTree is empty')
    } else {
        let node: (null | BinarySearchTreeNode) = 
        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 }
    }
}

Delete nodes

The deletion method is still based on iteration, and four different node situations need to be considered, as follows:

  • Leaf node: No nodes that do not have left and right subtrees, the nodes are directly empty.
  • Node with only the left subtree: Let its left node overwrite the node to be deleted.
  • Node with only the right subtree: Let its right node overwrite the node to be deleted.
  • Nodes with left and right subtrees: In order to ensure the order of the binary tree, the value of the node to be deleted is generally replaced with the minimum value of its right subtree.
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) = (node!.right)
        (temp!.index)
        node!.index = temp!.index
        node!.element = temp!.element
        ++
    }
    return node
}

minNodeMethod: Find the minimum value of the right subtree of the current node

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

removeMethod: IfindexValid, the traversal will reach the previous node of the node to be deleted, and executeremoveNodeMethod to delete nodes

remove(index: number): BinarySearchTree {
    if (()) {
        throw new Error('BinarySearchTree is empty')
    } else {
        let node: (null | BinarySearchTreeNode) = 
        while (node !== null) {
            if (index === node!.index) {
                 = (node)
                break
            } else if (node!.left !== null && index === node!.) {
                node!.left = (node!.left)
                break
            } else if (node!.right !== null && index === node!.) {
                node!.right = (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`) }
        --
        return this
    }
}

Notice: Our requirement is to change the properties of the previous node of the node to be deleted in the binary tree search tree, so that the instance object can produce reference values ​​to achieve the effect of deletion. If we traverse directly to the deleted node, no modification to this node (variable) will not be reflected on the instance object. Let’s take a look at the following example:

let a = { name: "Xiao Ming", age: 20 }
let b = a       // a and b point to the same address = null    // The effect will also become nullb = null        // b is reassigned, a and b will not point to the same address.  So a will not become null

Traversal of binary trees

The recursive implementation is as follows:

Preamble traversal (root left and right)

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) {
        ({ index: node!.index, element: node!.element })
        preOrderTraversalNode(node!.left, result)
        preOrderTraversalNode(node!.right, result)
    }
}

Middle order traversal (left root right)

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)
        ({ index: node!.index, element: node!.element })
        inOrderTraversalNode(node!.right, result)
    }
}

Post-order traversal (left and left and right roots)

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)
        ({ index: node!.index, element: node!.element })
    }
}

Layer sequence traversal (hierarchical record)

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

The iterative implementation is as follows:

Preamble traversal (root left and right)

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 || !()) {
        while (node !== null) {
            (node)
            ({ index: node!.index, element: node!.element })
            node = node!.left
        }
        node = ()
        node = node!.right
    }
    return result
}

Middle order traversal (left root right)

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 || !()) {
        while (node !== null) {
            (node)
            node = node!.left
        }
        node = ()
        ({ index: node!.index, element: node!.element })
        node = node!.right
    }
    return result
}

Post-order traversal (left and left and right roots)

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 || !()) {
        while (node !== null) {
            (node)
            node = node!.left
        }
        node = ()
        if (node!.right === null || node!.right === prev) {
            ({ index: node!.index, element: node!.element })
            prev = node
            node = null
        } else {
            (node)
            node = node!.right
        }
    }
    return result
}

Layer sequence traversal (breadth priority search)

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
    (node)
    while (!()) {
        ([])
        const { length } = queue
        for (let i = 0; i < length; i++) {
            node = ()
            result[ - 1].push({ index: node!.index, element: node!.element })
            if (node!.left) { (node!.left) }
            if (node!.right) { (node!.right) }
        }
    }
    return result
}

At this point, the addition, deletion and traversal methods of the binary search tree have been completed. The advantage of iterative implementation is that every time JavaScript calls a function, an execution context will be generated to push it into the function call stack. If the binary search tree we build is very high, recursion may cause stack explosion.

The relevant code in this article has been placed in my Github repository 👇

Project address:

Algorithmlib｜BinarySearchTree

Algorithmlib｜BinaryTree Traversal

The above is the detailed explanation of the binary search tree implementation of the data structure TypeScript binary search tree. For more information about the binary search tree of TypeScript data structure, please pay attention to my other related articles!