C++实现删除二叉搜索树节点功能 |21xrx.com

C++实现删除二叉搜索树节点功能

2023-07-02 03:30:57 深夜i -- --

C++ 删除二叉搜索树节点功能

二叉搜索树是一种非常重要的数据结构，它可以高效地处理查找、插入和删除等操作。C++是一种非常强大的语言，它提供了许多方便的工具和功能，可以轻松实现二叉搜索树的节点删除功能。在本文中，我们将介绍如何使用C++来实现这个功能。

首先，让我们回顾一下二叉搜索树的定义和性质。一棵二叉搜索树是一棵二叉树，它的任何节点的左子树中的值都小于该节点的值，右子树中的值都大于该节点的值。对于任何一个节点，它的左子树和右子树都是一棵二叉搜索树。

在删除二叉搜索树的节点时，我们需要遵循以下步骤：

1. 如果要删除的节点是叶子节点，直接将其删除即可；

2. 如果要删除的节点只有一颗子树，将该节点的子树替换它的位置即可；

3. 如果要删除的节点有两颗子树，需要找到该节点的后继节点（即该节点右子树中最小的节点），将其值赋给该节点，然后将后继节点删除。

接下来，让我们看看如何使用C++来实现这个功能。

1. 删除叶子节点

对于叶子节点，我们只需要将其父节点的左/右指针指向NULL即可。

例如，假设我们要删除二叉搜索树中的节点5：

7 / \ 5 9 / \ 8 10

我们可以执行以下代码：

Node *deleteNode(Node *root, int key) {
  if (root == NULL) return NULL;
  if (root->val == key) {
    if (root->left == NULL && root->right == NULL)
      delete root;
      return NULL;
    
  }
  // ...
}

2. 删除只有一颗子树的节点

对于只有一颗子树的节点，我们只需要将该节点的子树替换给它的父节点即可。

例如，假设我们要删除二叉搜索树中的节点7：

7 / \ 5 9 / \ 8 10

删除节点7之后，它的子节点5就应该替换成节点9的子节点：

9 / \ 5 10 / 8

我们可以执行以下代码：

Node *deleteNode(Node *root, int key) {
  if (root == NULL) return NULL;
  if (root->val == key) {
    if (root->left == NULL && root->right == NULL)
      delete root;
      return NULL;
    
    if (root->left == NULL) {
      Node *newRoot = root->right;
      delete root;
      return newRoot;
    }
    if (root->right == NULL) {
      Node *newRoot = root->left;
      delete root;
      return newRoot;
    }
  }
  // ...
}

3. 删除有两颗子树的节点

对于有两颗子树的节点，我们需要找到该节点的后继节点（即该节点右子树中值最小的节点），将其值赋给该节点，然后将后继节点删除。

例如，假设我们要删除二叉搜索树中的节点7：

7 / \ 5 9 / \ 8 10

删除节点7之后，它的后继节点是节点8，于是我们将节点8的值赋给节点7：

8 / \ 5 9 \ 10

然后我们可以删除节点8：

9 / \ 5 10 / 8

我们可以执行以下代码：

Node *findMin(Node *root) {
  while (root->left != NULL)
    root = root->left;
  
  return root;
}
Node *deleteNode(Node *root, int key) {
  if (root == NULL) return NULL;
  if (root->val == key) {
    if (root->left == NULL && root->right == NULL)
      delete root;
      return NULL;
    
    if (root->left == NULL) {
      Node *newRoot = root->right;
      delete root;
      return newRoot;
    }
    if (root->right == NULL) {
      Node *newRoot = root->left;
      delete root;
      return newRoot;
    }
    Node *successor = findMin(root->right);
    root->val = successor->val;
    root->right = deleteNode(root->right, root->val);
  } else if (root->val > key) {
    root->left = deleteNode(root->left, key);
  } else {
    root->right = deleteNode(root->right, key);
  }
  return root;
}

到此为止，我们已经成功地实现了二叉搜索树的节点删除功能。在实际应用中，我们可以根据自己的需求对代码进行修改和优化，以满足不同的需求。

上一篇: idea打包java可执行jar包

下一篇: 《C++从入门到精通》读后感

评论区

相似文章