JavaScript数据结构之二叉树的删除算法示例

下面我来详细讲解一下“JavaScript数据结构之二叉树的删除算法示例”的完整攻略。

什么是二叉树？

二叉树是一种特殊的树形结构，每个节点最多只能有两个子节点，分别称为左子节点和右子节点。二叉树是一种常用的数据结构，在计算机科学中有着广泛的应用。

二叉树的删除算法

二叉树的删除算法是指在二叉树中删除一个节点的过程。删除节点通常需要考虑以下几种情况：

• 要删除的节点是叶子节点（没有子节点）
• 要删除的节点只有一个子节点
• 要删除的节点有两个子节点

以下是一份JavaScript的二叉树删除算法示例代码：

deleteNode(value) {
    if (!this.root) {
        return;
    }

    let parentNode = null;
    let currentNode = this.root;

    while (currentNode && currentNode.value !== value) {
        parentNode = currentNode;
        if (value < currentNode.value) {
            currentNode = currentNode.left;
        } else {
            currentNode = currentNode.right;
        }
    }

    if (!currentNode) {
        return;
    }

    if (!currentNode.left || !currentNode.right) {
        let childNode = currentNode.left || currentNode.right;

        if (!parentNode) {
            this.root = childNode;
        } else if (currentNode === parentNode.left) {
            parentNode.left = childNode;
        } else {
            parentNode.right = childNode;
        }
    } else {
        let minRightNode = currentNode.right;
        while (minRightNode.left) {
            minRightNode = minRightNode.left;
        }

        let tempValue = currentNode.value;
        currentNode.value = minRightNode.value;
        minRightNode.value = tempValue;

        this.deleteNode(minRightNode.value);
    }
}

示例

接下来，我们通过两个实际的示例来演示这个删除算法。

示例一：删除叶子节点

假设我们有一颗如下所示的二叉树：

      8
    /   \
   3     10
  / \      \
 1   6     14
    / \   /
   4   7 12

我们要删除叶子节点12，只需执行以下代码：

tree.deleteNode(12);

执行后，整个树的结构将变为：

      8
    /   \
   3     10
  / \      \
 1   6     14
    / \
   4   7

示例二：删除有两个子节点的节点

现在，我们要删除有两个子节点的节点10，只需执行以下代码：

tree.deleteNode(10);

执行后，整个树的结构将变为：

      8
    /   \
   3     12
  / \      \
 1   6     14
    / \
   4   7

在这个示例中，节点10被节点12取代了，而节点12原来的位置被删除了。这是因为要删除有两个子节点的节点，需要找到它右子树中的最小节点，并将其删除，然后将这个最小节点的值赋给要删除的节点。

至此，“JavaScript数据结构之二叉树的删除算法示例”的完整攻略就讲解完了。