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

C++实现二叉搜索树

2023-06-29 08:04:13 深夜i -- --

C++ 二叉搜索树实现

二叉搜索树 (Binary Search Tree, BST) 是一种常用的数据结构，可以高效地实现插入、删除、查找等操作。在C++中，我们可以利用类的封装来实现BST。

首先，我们需要定义一个节点类 (Node)，包括数据变量和指向左右子节点的指针。代码如下：


class Node {
public:
  int data;
  Node* left;
  Node* right;
  Node(int val)
    data = val;
    left = right = nullptr;
  
};

接着，我们可以定义一个BST类 (BST)，包括插入、删除和查询等操作。在插入操作中，我们需要递归地比较待插入节点的值与当前节点的值，如果小于当前节点的值则插入左子树，否则插入右子树。代码如下：


class BST {
public:
  Node* root;
  BST()
    root = nullptr;
  
  
  void insertNode(int val) {
    root = insertNodeUtil(root, val);
  }
  
  Node* insertNodeUtil(Node* node, int val) {
    if (node == nullptr) {
      node = new Node(val);
    }
    else if (val < node->data) {
      node->left = insertNodeUtil(node->left, val);
    }
    else {
      node->right = insertNodeUtil(node->right, val);
    }
    return node;
  }
};

删除节点的过程比较复杂，需要分情况讨论。如果待删除节点是叶子节点，直接删除即可；如果待删除节点只有一个子节点，将该子节点替换上即可；如果待删除节点有两个子节点，找到其右子树的最小值节点（或左子树的最大值节点），将其值复制到待删除节点，然后递归删除该最小值/最大值节点即可。代码如下：


  void deleteNode(int val) {
    root = deleteNodeUtil(root, val);
  }
  
  Node* deleteNodeUtil(Node* node, int val) {
    if (node == nullptr)
      return nullptr;
    
    if (val < node->data) {
      node->left = deleteNodeUtil(node->left, val);
    }
    else if (val > node->data) {
      node->right = deleteNodeUtil(node->right, val);
    }
    else {
      if (node->left == nullptr && node->right == nullptr)
        delete node;
        node = nullptr;
      
      else if (node->left == nullptr) {
        Node* tmp = node;
        node = node->right;
        delete tmp;
      }
      else if (node->right == nullptr) {
        Node* tmp = node;
        node = node->left;
        delete tmp;
      }
      else {
        Node* tmp = findMinNode(node->right);
        node->data = tmp->data;
        node->right = deleteNodeUtil(node->right, tmp->data);
      }
    }
    return node;
  }
  
  Node* findMinNode(Node* node) {
    while (node->left != nullptr)
      node = node->left;
    
    return node;
  }

查询节点的过程也比较简单，递归地比较待查询节点的值与当前节点的值，如果相等则返回当前节点，否则继续在左/右子树中查找。代码如下：


  bool searchNode(int val) {
    return searchNodeUtil(root, val);
  }
  
  bool searchNodeUtil(Node* node, int val) {
    if (node == nullptr)
      return false;
    
    if (node->data == val)
      return true;
    
    else if (val < node->data) {
      return searchNodeUtil(node->left, val);
    }
    else {
      return searchNodeUtil(node->right, val);
    }
  }

以上就是C++实现BST的基本步骤，当然还有各种细节需要注意和完善。BST是一种非常有用的数据结构，能够应用到很多场合中。本文提供的代码只是一种简单的实现，感兴趣的读者可以进一步探究BST的其他实现方式和应用场景。

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

下一篇: C++如何强制结束函数

评论区

()

相似文章