C++类实现二叉搜索树 |holyya.com

C++类实现二叉搜索树

2023-07-07 16:31:07 深夜i -- --

C++ 类二叉搜索树实现

二叉搜索树（Binary Search Tree）是一种非常常用的数据结构，它能够提供快速的查找、插入和删除操作。在C++中，我们可以使用类来实现二叉搜索树。

首先我们需要定义一个节点类，表示二叉搜索树中的节点，包含节点值、左右子节点等基本信息。定义如下：


class TreeNode {
public:
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

接着，我们定义一个二叉搜索树类，其中包含了树的根节点，以及对树的插入、查找、删除等基本操作。其中，插入、查找和删除操作都是递归实现的，代码如下：


class BST {
public:
  TreeNode* root;
  BST()
    root = NULL;
  
  // 插入节点
  void insert(int val) {
    root = insertHelper(root, val);
  }
  // 查找节点
  TreeNode* search(int val) {
    return searchHelper(root, val);
  }
  // 删除节点
  void remove(int val) {
    root = removeHelper(root, val);
  }
private:
  // 插入节点的子函数
  TreeNode* insertHelper(TreeNode* root, int val) {
    if (root == NULL) {
      return new TreeNode(val);
    }
    if (val < root->val) {
      root->left = insertHelper(root->left, val);
    }
    else if (val > root->val) {
      root->right = insertHelper(root->right, val);
    }
    return root;
  }
  // 查找节点的子函数
  TreeNode* searchHelper(TreeNode* root, int val) {
    if (root == NULL || root->val == val)
      return root;
    
    if (val < root->val) {
      return searchHelper(root->left, val);
    }
    else {
      return searchHelper(root->right, val);
    }
  }
  // 删除节点的子函数
  TreeNode* removeHelper(TreeNode* root, int val) {
    if (root == NULL)
      return root;
    
    if (val < root->val) {
      root->left = removeHelper(root->left, val);
    }
    else if (val > root->val) {
      root->right = removeHelper(root->right, val);
    }
    else {
      if (root->left == NULL && root->right == NULL)
        delete root;
        root = NULL;
      
      else if (root->left == NULL) {
        TreeNode* temp = root->right;
        delete root;
        root = temp;
      }
      else if (root->right == NULL) {
        TreeNode* temp = root->left;
        delete root;
        root = temp;
      }
      else {
        TreeNode* temp = findMin(root->right);
        root->val = temp->val;
        root->right = removeHelper(root->right, temp->val);
      }
    }
    return root;
  }
  // 查找最小节点的子函数
  TreeNode* findMin(TreeNode* root) {
    while (root->left != NULL)
      root = root->left;
    
    return root;
  }
};

以上便是一个基本的二叉搜索树类的实现，可以通过调用insert、search、remove等方法来进行操作。当然，这里只是一个简单的实现，实际使用中可能需要根据具体情况进行一些调整和优化。

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

下一篇: C++中opendir和fopen的区别说明

评论区

()

相似文章