JavaScript 二叉树

什么是二叉树

二叉树是一种每个节点最多有两个子节点的树状结构。通常，这两个子节点被称作左子节点和右子节点。二叉树是树形结构的一个重要类型，其应用广泛，尤其是在数据存储和检索领域。

二叉树的基本术语

在开始学习二叉树之前，我们需要了解一些基本术语：

• 根节点：二叉树的顶端节点。
• 叶子节点：没有子节点的节点。
• 父节点：拥有子节点的节点。
• 子节点：被其他节点指向的节点。
• 兄弟节点：有相同父节点的节点。
• 路径：从一个节点到另一个节点之间的连接。
• 深度：从根节点到该节点所经过的边的数量。
• 高度：从该节点到底部最远叶子节点的最长路径边的数量。

二叉树的实现

在 JavaScript 中，我们可以通过类来创建二叉树的节点以及整个二叉树。

创建节点

首先，我们创建一个节点类，用于表示二叉树中的每一个节点。

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

创建二叉树

接下来，我们将创建一个二叉树类，用于管理二叉树的节点，并提供添加节点的方法。

-- -------------------- ---- -------
----- ---------- -
    ------------- -
        --------- - -----
    -

    ---------- -
        ----- ------- - --- ----------------

        -- ---------- --- ----- -
            --------- - --------
        - ---- -
            -------------------------- ---------
        -
    -

    ---------------- -------- -
        -- -------------- - ----------- -
            -- ---------- --- ----- -
                --------- - --------
            - ---- -
                -------------------------- ---------
            -
        - ---- -
            -- ----------- --- ----- -
                ---------- - --------
            - ---- -
                --------------------------- ---------
            -
        -
    -
-

二叉树的遍历

二叉树的遍历是指按照一定的顺序访问二叉树中的所有节点。常见的遍历方法有三种：前序遍历、中序遍历和后序遍历。

前序遍历

前序遍历遵循“根-左-右”的原则，即先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。

function preOrderTraversal(node, callback) {
    if (node !== null) {
        callback(node.value);
        preOrderTraversal(node.left, callback);
        preOrderTraversal(node.right, callback);
    }
}

中序遍历

中序遍历遵循“左-根-右”的原则，即先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。

function inOrderTraversal(node, callback) {
    if (node !== null) {
        inOrderTraversal(node.left, callback);
        callback(node.value);
        inOrderTraversal(node.right, callback);
    }
}

后序遍历

后序遍历遵循“左-右-根”的原则，即先递归地对左子树进行后序遍历，然后递归地对右子树进行后序遍历，最后访问根节点。

function postOrderTraversal(node, callback) {
    if (node !== null) {
        postOrderTraversal(node.left, callback);
        postOrderTraversal(node.right, callback);
        callback(node.value);
    }
}

二叉搜索树（BST）

二叉搜索树是一种特殊的二叉树，它的每个节点都具有特定的性质：左子树上的所有节点值都小于该节点值，而右子树上的所有节点值都大于该节点值。

插入节点

插入新节点时，需要保证新节点满足二叉搜索树的性质。

-- -------------------- ---- -------
----- ---------------- ------- ---------- -
    ------------- -
        --------
    -

    ---------- -
        ----- ------- - --- ----------------

        -- ---------- --- ----- -
            --------- - --------
        - ---- -
            -------------------------- ---------
        -
    -

    ---------------- -------- -
        -- -------------- - ----------- -
            -- ---------- --- ----- -
                --------- - --------
            - ---- -
                -------------------------- ---------
            -
        - ---- -
            -- ----------- --- ----- -
                ---------- - --------
            - ---- -
                --------------------------- ---------
            -
        -
    -
-

查找节点

查找节点时，从根节点开始，根据节点值的大小关系，决定向左子树或右子树继续查找。

-- -------------------- ---- -------
------------------------------- - -------- ------- -
    --- ------- - ----------

    ----- -------- --- ----- -
        -- -------------- --- ------ -
            ------ --------
        - ---- -- ------ - -------------- -
            ------- - -------------
        - ---- -
            ------- - --------------
        -
    -

    ------ -----
--

总结

通过上述章节的学习，我们可以了解到二叉树的基本概念、术语以及如何在 JavaScript 中实现和操作二叉树。二叉树及其衍生的数据结构（如二叉搜索树）在计算机科学中有着重要的应用，掌握它们对于提升编程技能非常重要。