JavaScript数据结构与算法之二叉树添加/删除节点操作示例

首先让我们来介绍一下“JavaScript数据结构与算法之二叉树添加/删除节点操作示例”这个主题。

主题介绍

本主题主要介绍了在 JavaScript 中对于二叉树数据结构进行添加/删除节点操作的示例代码。二叉树是一种常见的树形结构，在计算机科学领域中被广泛应用。节点的添加与删除是该数据结构中常见的操作之一，本主题将通过示例代码，为您详细介绍操作的过程。

代码实现

首先，我们需要定义一个二叉树的节点类，包含一个值属性和左右子节点属性。这里我先给出一个简单的实现。

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

接下来，我们需要定义实现添加节点的函数 insert。这个函数的过程包含了二叉树的遍历、查找、新建节点等过程。

insert(val) {
  const newNode = new TreeNode(val);
  if (this.root === null) {
    this.root = newNode;
    return this;
  } else {
    let current = this.root;

    while (true) {
      if (val === current.val) return undefined;

      if (val < current.val) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        } else {
          current = current.left;
        }
      } else {
        if (current.right === null) {
          current.right = newNode;
          return this;
        } else {
          current = current.right;
        }
      }
    }
  }
}

以上是二叉树添加节点的代码示例。

接下来，我们介绍删除节点的代码示例。删除节点的实现需要考虑到三种情况：

• 节点没有子节点，直接删除即可
• 节点有一个子节点，将该子节点替代被删除节点
• 节点有两个子节点，需要在右子树中寻找最小值节点，并将该节点替代被删除节点

下面是实现删除节点的代码示例：

delete(val) {
  if (this.root === null) return false;

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

  while (currentNode !== null) {
    if (val === currentNode.val) {
      if (currentNode.left === null && currentNode.right === null) {
        if (currentNode === this.root) {
          this.root = null;
        } else if (isLeftChild) {
          parentNode.left = null;
        } else {
          parentNode.right = null;
        }
      } else if (currentNode.left === null) {
        if (currentNode === this.root) {
          this.root = currentNode.right;
        } else if (isLeftChild) {
          parentNode.left = currentNode.right;
        } else {
          parentNode.right = currentNode.right;
        }
      } else if (currentNode.right === null) {
        if (currentNode === this.root) {
          this.root = currentNode.left;
        } else if (isLeftChild) {
          parentNode.left = currentNode.left;
        } else {
          parentNode.right = currentNode.left;
        }
      } else {
        let replacementNode = currentNode.right;
        let replacementParentNode = currentNode;

        while (replacementNode.left !== null) {
          replacementParentNode = replacementNode;
          replacementNode = replacementNode.left;
        }

        if (replacementNode !== currentNode.right) {
          replacementParentNode.left = replacementNode.right;
          replacementNode.right = currentNode.right;
        }

        if (currentNode === this.root) {
          this.root = replacementNode;
        } else if (isLeftChild) {
          parentNode.left = replacementNode;
        } else {
          parentNode.right = replacementNode;
        }

        replacementNode.left = currentNode.left;
      }

      return true;
    } else if (val < currentNode.val) {
      parentNode = currentNode;
      currentNode = currentNode.left;
      isLeftChild = true;
    } else {
      parentNode = currentNode;
      currentNode = currentNode.right;
      isLeftChild = false;
    }
  }

  return false;
}

以上就是二叉树删除节点的代码示例。

示例说明

此处给出两个关于添加节点和删除节点操作的示例，方便您了解二叉树数据结构的操作过程。

示例一：添加节点操作

假设有一个空白的二叉树，我们要添加以下数据：6, 4, 8, 3, 5, 7, 9。

const bst = new BinarySearchTree();
bst.insert(6);
bst.insert(4);
bst.insert(8);
bst.insert(3);
bst.insert(5);
bst.insert(7);
bst.insert(9);

这样就完成了二叉树的添加节点操作。

示例二：删除节点操作

假设有一个已经包含数据 6, 4, 8, 3, 5, 7, 9 的二叉树，我们需要删除节点为 4 的节点。

const bst = new BinarySearchTree();
bst.insert(6);
bst.insert(4);
bst.insert(8);
bst.insert(3);
bst.insert(5);
bst.insert(7);
bst.insert(9);
bst.delete(4);

这样就完成了二叉树的删除节点操作。

总结

二叉树作为一种常见的树形数据结构，在很多场景下都有广泛的应用。本文通过 JavaScript 实现的方式，为您介绍了二叉树的添加、删除节点操作。希望这篇文章能够对您理解二叉树数据结构有所帮助。