二叉搜索树的代码实现，有插入、查找、删除等基本功能。

需要注意的是，当类中有私有类pClass且在类外声明的成员函数的返回值是pClass类型的时候，需要在pClass前加typename。比如说

template <typename Comparable> typename binarysearchtree<Comparable>::BinaryNode* binarysearchtree<Comparable>::findMax(BinaryNode* t)const {
    if (t == NULL) return NULL;
    if (t->right == NULL) return t;
    return findMin(t->right);
}

这里的typename如果去掉的话就会报错

warning C4346:  “BinaryNode”: 依赖名称不是类型
error C2061:  语法错误: 标识符“BinaryNode”

 

这么做的原因，我目前还没搞清楚。

#pragma once
template <typename Comparable> class binarysearchtree {
public:
    binarysearchtree() { BinaryNode* root = nullptr; }
    binarysearchtree(const binarysearchtree& rhs) { this = rhs; }
    ~binarysearchtree() { makeEmpty(); }

    const Comparable& findMin() const { return findMin(root); }
    const Comparable& findMax() const { return findMax(root); }
    bool contains(const Comparable& x) const;
    bool isEmpty() const { return root == nullptr; }
    void printTree() const {
        printTree(root, 0);
    }

    void makeEmpty() {
        makeEmpty(root);

    }
    void insert(const Comparable& x);
    void remove(const Comparable& x);

    const binarysearchtree& operator=(const binarysearchtree& rhs) {
        if (*this != rhs) {
            makeEmpty();
            root = clone(rhs.root);
        }
        return &this;
    }
    
private:
    struct BinaryNode {
        Comparable element;
        BinaryNode* left;
        BinaryNode* right;

        BinaryNode(const Comparable& theElement, BinaryNode* lt, BinaryNode* rt) :
            element(theElement), left(lt), right(rt) {}
    };

    BinaryNode* root;

    void insert(const Comparable& x, BinaryNode*& t) const;
    void remove(const Comparable& x, BinaryNode*& t) const;
    BinaryNode* findMin(BinaryNode* t)const;
    BinaryNode* findMax(BinaryNode* t)const;
    bool contains(const Comparable& x, BinaryNode* t) const;
    void makeEmpty(BinaryNode*& t);
    void printTree(BinaryNode* t, const int& depth)const;
    BinaryNode* clone(BinaryNode* t) const;
};

template <typename Comparable> bool binarysearchtree<Comparable>::contains(const Comparable& x) const {
    return contains(x, root);
}

template <typename Comparable> void binarysearchtree<Comparable>::insert(const Comparable& x) {
    insert(x, root);
}

template <typename Comparable> void binarysearchtree<Comparable>::remove(const Comparable& x) {
    remove(x, root);
}

template <typename Comparable> bool binarysearchtree<Comparable>::contains(const Comparable& x, BinaryNode* t) const {
    if (t == NULL) return false;
    else if (t->element > x) return contains(x, t->left);
    else if (t->element < x) return contains(x, t->right);
    else return true;
}

template <typename Comparable> typename binarysearchtree<Comparable>::BinaryNode* binarysearchtree<Comparable>::findMin(BinaryNode* t)const{
    if (t == NULL) return NULL;
    if (t->left == NULL) return t;
    return findMin(t->left);
}

template <typename Comparable> typename binarysearchtree<Comparable>::BinaryNode* binarysearchtree<Comparable>::findMax(BinaryNode* t)const {
    if (t == NULL) return NULL;
    if (t->right == NULL) return t;
    return findMin(t->right);
}

template <typename Comparable> void binarysearchtree<Comparable>::insert(const Comparable& x, BinaryNode*& t) const {
    if (t == NULL) t = new BinaryNode(x, NULL, NULL);
    else if (t->element > x) insert(x, t->left);
    else if (t->element < x) insert(x, t->right);
    else;
}

template <typename Comparable> void binarysearchtree<Comparable>::remove(const Comparable& x, BinaryNode*& t) const {
    if (t == NULL) return;
    if (t->element > x) remove(x, t->left);
    else if (t->element < x) remove(x, t->right);
    else if (t->right != NULL && t->left != NULL) {
        t->element = findMin(t->right)->element;
        remove(t->element, t->right);
    }
    else {
        BinaryNode* oldNode = t;
        t = (t->left != NULL) ? t->left : t->right;
        delete oldNode;
    }
}

template<typename Comparable> void binarysearchtree<Comparable>::makeEmpty(BinaryNode*& t) {
    if (t != nullptr) {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
        t = nullptr;
    }
}

template<typename Comparable> typename binarysearchtree<Comparable>::BinaryNode* binarysearchtree<Comparable>::clone(BinaryNode* t) const {
    if (t == nullptr) return t;
    return new BinaryNode(t->element, clone(t->left), clone(t->right));
}

template<typename Comparable> void binarysearchtree<Comparable>::printTree(BinaryNode* t, const int& i)const {
    if (t != nullptr) {
        printTree(t->left, i + 1);
        std::cout << string(i, '\t') << t->element << std::endl;
        
        printTree(t->right, i + 1);
    }
}