【Data Structure】二叉搜索树

使用C++实现二叉搜索树的添加、删除和查询，其余内容待补充中

#include <iostream>
using namespace std ;
struct BSTreeNode {
    int data ;
    BSTreeNode* left ;
    BSTreeNode* right ;
    BSTreeNode() : data(0), left(nullptr), right(nullptr) {} ;
    BSTreeNode(int val) : data(val), left(nullptr), right(nullptr) {} ;
};
class BSTree {
public:
    BSTreeNode* root ;
    BSTree();
    ~BSTree();
    void insert(int val) ;
    BSTreeNode* find(int val) ;
    BSTreeNode* findMin() ;
    BSTreeNode* findMax() ;
    void remove(int val) ;
private:
    void insert(BSTreeNode* node, int val) ;
    BSTreeNode* find(BSTreeNode* node, int val) ;
    BSTreeNode* remove(BSTreeNode* node, int val) ;
    BSTreeNode* findMin(BSTreeNode* node) ;
    BSTreeNode* findMax(BSTreeNode* node) ;

};

BSTree::BSTree() { this->root = nullptr ; }
BSTree::~BSTree() {}
void BSTree::insert(int val) {
    if (this->root == nullptr) {
        this->root = new BSTreeNode(val) ;
        return ;
    }
    insert(root, val) ;
}

void BSTree::insert(BSTreeNode* node, int val) {
    if (node->data > val) {
        if (node->left == nullptr) {
            node->left = new BSTreeNode(val) ;
        } else {
            insert(node->left, val) ;
        }
    } else if (node->data < val) {
        if (node->right == nullptr) {
            node->right = new BSTreeNode(val) ;
        } else {
            insert(node->right, val) ;
        }
    } else {
        cout << "Error!" << endl ;
    }
}

BSTreeNode* BSTree::find(int val) {
    return find(root, val) ;
}

BSTreeNode* BSTree::find(BSTreeNode* node, int val) {
    if (node == nullptr) {
        return nullptr ;
    }
    if (node->data > val) {
        return find(node->left, val) ;
    } else if (node->data < val) {
        return find(node->right, val) ;
    } else {
        return node ;
    }
}

BSTreeNode* BSTree::findMin() {
    return findMin(root) ;
}

BSTreeNode* BSTree::findMax() {
    return findMax(root) ;
}

BSTreeNode* BSTree::findMax(BSTreeNode* node) {
    if (node == nullptr) return nullptr ;
    if (node->right == nullptr) {
        return node ;
    } else {
        return findMax(node->right) ;
    }
}

BSTreeNode* BSTree::findMin(BSTreeNode* node) {
    if (node == nullptr) return nullptr ;
    if (node->left == nullptr) {
        return node ;
    } else {
        return findMin(node->left) ;
    }
}


BSTreeNode* BSTree::remove(BSTreeNode* node, int val) {
    BSTreeNode* t ;
    if (node == nullptr) cout << "Error!" << endl ;
    else if (node->data > val) node->left = remove(node->left, val) ;
    else if (node->data < val) node->right = remove(node->right, val) ;
    else {
        if (node->left != nullptr && node->right != nullptr) {
            t = findMin(node->right) ;
            node->data = t->data ;
            node->right = remove(node->right, val) ;
        } else {
            t = node ;
            if (node->left == nullptr) {
                node = node->right ;
            } else if (node->right == nullptr) {
                node = node->left ;
            }
            delete t ;
            t = nullptr ;
        }
    }
    return node ;
}

void BSTree::remove(int val) {
    root = remove(root, val) ;
}


int main() {
    BSTree* tree = new BSTree() ;
    tree->insert(1) ;
    tree->insert(2) ;
    tree->insert(3) ;
    tree->insert(-1) ;
    tree->insert(-10) ;
    cout << tree->findMin()->data << endl ;
    tree->remove(-10) ;
    cout << tree->findMin()->data << endl ;
    tree->remove(-1) ;
    cout << tree->findMin()->data << endl ;
    tree->remove(1) ;
    cout << tree->findMin()->data << endl ;
    return 0 ;
}

【Data Structure】二叉搜索树

原文：https://www.cnblogs.com/Suans/p/14383673.html