第一次接触树，各种递归搞得眼花，总算是按书上的代码，敲了下来，记录一下

/**
 * Created by admin on 2021/10/27.
 * 搜索二叉树实现
 */
#ifndef HELLOWORLD_BINARY_SEARCH_TREE_H
#define HELLOWORLD_BINARY_SEARCH_TREE_H
#include <istream>
template <typename Object>
class BinarySearchTree{
    struct TreeNode{
        Object object; // 数据
        TreeNode *left;  // 左子树指针
        TreeNode *right; // 右子树指针
    };  // 二进制树
    TreeNode *root; // 根节点
    void insert(const Object &, TreeNode *&);  // 插入元素
    void printTree(TreeNode *&);  // 打印树
    bool contain(const Object&, TreeNode *&);  // 查找树中是否有该元素
    TreeNode *findMax(TreeNode *&);  // 找最大值
    TreeNode *findMin(TreeNode *&);  // 找最小值
    void remove(const Object &object, TreeNode *&);
    void makeEmpty(TreeNode *&);
    TreeNode *clone(TreeNode *);
public:
    BinarySearchTree(): root(nullptr){};  // 普通构造函数
    ~BinarySearchTree(){ makeEmpty(root);}  // 析构函数
    BinarySearchTree(const BinarySearchTree &rhs): root(nullptr){root = clone(rhs.root);}
    void insert(const Object &object){ insert(object, root);} // 插入数据
    void printTree(){ printTree(root);};  // 打印树
    bool contain(const Object &object){ return contain(object, root);}
    const Object &findMax(){return findMax(root)->object;}  // 找最大值
    const Object &findMin(){return findMin(root)->object;}  // 找最小值
    void remove(const Object &object){remove(object, root);}  // 删除元素
};

template<typename Object>
void BinarySearchTree<Object>::insert(const Object &object, TreeNode *&treeNode) {
    if (treeNode == nullptr) treeNode = new TreeNode{object, nullptr, nullptr};  // 新建节点
    else if (object < treeNode->object) insert(object, treeNode->left);  // 向左递归插入
    else if (object > treeNode->object) insert(object, treeNode->right); // 向左递归插入
}

template<typename Object>
void BinarySearchTree<Object>::printTree(BinarySearchTree::TreeNode *&treeNode) {
    if (treeNode == nullptr) return;
    std::cout << treeNode->object;  // 前序打印
    if (treeNode->left != nullptr) printTree(treeNode->left);
    if (treeNode->right != nullptr) printTree(treeNode->right);
}

template<typename Object>
bool BinarySearchTree<Object>::contain(const Object &object, BinarySearchTree::TreeNode *&treeNode) {
    if (treeNode == nullptr) return false;
    else if (object < treeNode->object) contain(object, treeNode->left);
    else if (object > treeNode->object) contain(object, treeNode->right);
    else return true;  // 匹配
}

template<typename Object>
typename BinarySearchTree<Object>::TreeNode *BinarySearchTree<Object>::findMax(BinarySearchTree::TreeNode *&treeNode) {
    if (treeNode == nullptr) return nullptr;
    if (treeNode->right == nullptr) return treeNode;
    return findMax(treeNode->right);
}

template<typename Object>
typename BinarySearchTree<Object>::TreeNode *BinarySearchTree<Object>::findMin(BinarySearchTree::TreeNode *&treeNode) {
    if (treeNode == nullptr) return nullptr;
    if (treeNode->left == nullptr) return treeNode;
    return findMin(treeNode->left);
}

template<typename Object>
void BinarySearchTree<Object>::remove(const Object &object, BinarySearchTree::TreeNode *&treeNode) {
    if (treeNode == nullptr) return;
    else if (object < treeNode->object) remove(object, treeNode->left);
    else if (object > treeNode->object) remove(object, treeNode->right);
    else if (treeNode->left != nullptr && treeNode->right != nullptr){  // 双节点的情况
        treeNode->object = findMin(treeNode->right)->object;  // 值用右树最小值替换
        remove(treeNode->object, treeNode->right); // 找到替换的节点
    }else{
        TreeNode *oldTreeNode = treeNode;
        treeNode = treeNode->left != nullptr? treeNode->left: treeNode->right;
        delete oldTreeNode;
    }

}

template<typename Object>
void BinarySearchTree<Object>::makeEmpty(BinarySearchTree::TreeNode *&treeNode) {
    if (treeNode == nullptr) return;
    makeEmpty(treeNode->left);
    makeEmpty(treeNode->right);
    delete treeNode;
    treeNode = nullptr;
}

template<typename Object>
typename BinarySearchTree<Object>::TreeNode *BinarySearchTree<Object>::clone(BinarySearchTree::TreeNode *treeNode) {
    if (treeNode == nullptr) return nullptr;
    else return new TreeNode{treeNode->object, clone(treeNode->left), clone(treeNode->right)};
}


#endif //HELLOWORLD_BINARY_SEARCH_TREE_H