「C++实现」二叉搜索树 |21xrx.com

「C++实现」二叉搜索树

2023-07-02 15:10:18 深夜i -- --

C++ 二叉搜索树实现

二叉搜索树（Binary Search Tree，BST）是一种基于二叉树的数据结构，它具有良好的查找、插入和删除操作效率。C++是一种高效、通用、面向对象的编程语言，可以轻松地实现二叉搜索树，使其更加灵活、可靠。

在二叉搜索树中，每个节点都包含一个键值以及两个指向其左右子树的指针。对于任意一个节点，其左子树中的所有节点的键值都比该节点的键值小，而其右子树中的所有节点的键值都比该节点的键值大。因此，通过比较键值，我们可以很快地找到存储在树中的任意元素。

我们可以通过节点的插入和删除来操作BST。插入节点时，从根节点开始，比较待插入节点的键值与当前节点的键值的大小关系，如果大于等于当前节点则在其右子树查找，否则在左子树查找，直到找到空位置为止，将待插入节点插入到该位置。删除节点时，如果待删除节点有两个子节点，则找到其右子树的最小节点，将其替换待删除节点的键值，然后删除该最小节点；如果有一个子节点或没有子节点，则直接将该节点删除。

下面是一个简单的C++代码实现，用于插入和删除节点：

#include <iostream>
using namespace std;
struct Node {
  int key;
  Node *left;
  Node *right;
  Node(int k) : key(k), left(NULL), right(NULL) {}
};
Node* insert(Node* root, int key) {
  if (root == NULL) {
    return new Node(key);
  }
  if (key < root->key) {
    root->left = insert(root->left, key);
  } else if (key > root->key) {
    root->right = insert(root->right, key);
  }
  return root;
}
Node* search(Node* root, int key) {
  if (root == NULL || root->key == key)
    return root;
  
  if (root->key < key) {
    return search(root->right, key);
  }
  return search(root->left, key);
}
Node* minValueNode(Node* node) {
  Node* current = node;
  while (current && current->left != NULL)
    current = current->left;
  
  return current;
}
Node* deleteNode(Node* root, int key) {
  if (root == NULL)
    return root;
  
  if (key < root->key) {
    root->left = deleteNode(root->left, key);
  } else if (key > root->key) {
    root->right = deleteNode(root->right, key);
  } else {
    if (root->left == NULL) {
      Node* temp = root->right;
      delete root;
      return temp;
    } else if (root->right == NULL) {
      Node* temp = root->left;
      delete root;
      return temp;
    }
    Node* temp = minValueNode(root->right);
    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}
void inorder(Node* root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}
int main() {
  Node* root = NULL;
  root = insert(root, 50);
  insert(root, 30);
  insert(root, 40);
  insert(root, 70);
  insert(root, 60);
  insert(root, 80);
  cout << "Inorder traversal: ";
  inorder(root);
  cout << "\nDelete 20\n";
  root = deleteNode(root, 20);
  cout << "Inorder traversal: ";
  inorder(root);
  cout << "\nDelete 30\n";
  root = deleteNode(root, 30);
  cout << "Inorder traversal: ";
  inorder(root);
  cout << "\nDelete 50\n";
  root = deleteNode(root, 50);
  cout << "Inorder traversal: ";
  inorder(root);
  return 0;
}

运行结果如下：

Inorder traversal: 30 40 50 60 70 80 Delete 20 Inorder traversal: 30 40 50 60 70 80 Delete 30 Inorder traversal: 40 50 60 70 80 Delete 50 Inorder traversal: 40 60 70 80

在上述代码中，我们通过递归实现了节点的插入和删除操作，使用inorder遍历算法输出树中所有节点。当我们删除一个节点时，需要考虑其子节点，如果有一个或没有子节点，直接删除该节点；如果有两个子节点，则找到其右子树的最小节点，将其值赋给待删除节点，然后删除该最小节点。

总之，C++语言提供了丰富的工具和函数，使其可以很容易地实现二叉搜索树，这使得我们可以更好地理解和优化常见的数据结构和算法。

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

下一篇: 何时应该使用C++引用

评论区

相似文章