#BinarySearchTree

cBinarySearchTree.h

#include "cNode.h"
#include <iostream>
using namespace std;

template <typename T>
class cBinarySearchTree{
    friend class cNode<T>;
public:
    int count;
    cBinarySearchTree<T>(): count(0) {
        root = NULL;
    }
    ~cBinarySearchTree<T>() {};
    void treeInsert(T x);
    void treeDelete(T x);
    void treePrint();
private:
    cNode<T>* treeInsert(cNode<T>* t, T x);
    void treeDelete(cNode<T>* t, cNode<T>* r, cNode<T>* p);
    cNode<T>* deleteNode(cNode<T>* r);
    void treePrint(cNode<T>* t, int step);
    cNode<T>* root;
};

template  <typename T>
void cBinarySearchTree<T>::treePrint(){
    treePrint(root, 0);
}


template  <typename T>
void cBinarySearchTree<T>::treePrint(cNode<T>* t, int step){
    if(t != NULL){
        if(step != count - 1){
            for(int i = 0; i < step; i++){
                cout << "    ";
            }
            cout << t->key;
            step++;
        }
        cout << endl;
        treePrint(t->left, step);
        treePrint(t->right, step);
    }
}




template <typename T>
void cBinarySearchTree<T>::treeInsert(T x){
    count++;
    root = root->treeInsert(root, x);
}

template <typename T>
void cBinarySearchTree<T>::treeDelete(T x){
    count--;
    cNode<T>* r = root;
    cNode<T>* p = NULL;

    while(r->key != x){
        if(r->key < x){
            p = r;
            r = r->right;
        }
        else{
            p = r;
            r = r->left;
        }
    }


    // r의 부모를 찾아 p에 저장

    if(r)       treeDelete(root, r, p);
}


template <typename T>
void cBinarySearchTree<T>::treeDelete(cNode<T>* t, cNode<T>* r, cNode<T>* p){
    if(t == r){
         root = root->deleteNode(r);
    }
    else if(r == p->left)
        p->left = root->deleteNode(r);
    else
        p->right = root->deleteNode(r);
}

cNode.h

#include <iostream>

template <typename T>
class cBinarySearchTree;

template <typename T>
class cNode{
    friend class cBinarySearchTree<T>;
public:
    cNode() : key(0), left(NULL), right(NULL) {}
    cNode(T t){key = t; left = right = NULL;}
private:
    cNode<T>* left;
    cNode<T>* right;
    T key;
    cNode<T>* treeInsert(cNode<T>* t, T x);
    cNode<T>* deleteNode(cNode<T>* r);
};


template <typename T>
cNode<T>* cNode<T>:: treeInsert(cNode<T>* t, T x){
    if(t == NULL){
        cNode<T>* newNode = new cNode<T>(x);
        return newNode;
    }
    if(x < t->key){
        t->left = treeInsert(t->left, x);
        return t;
    }
    else{
        t->right = treeInsert(t->right, x);
        return t;
    }
}


template <typename T>
cNode<T>* cNode<T>::deleteNode(cNode<T>* r){

    if(r->left == NULL && r->right == NULL)
        return NULL;
    else if(r->left == NULL && r->right != NULL)
        return r->right;
    else if(r->left != NULL && r->right == NULL){
        return r->left;
    }
    else{
        cNode<T>* s = r->right;
        cNode<T>* parent;
        while(s->left != NULL){
            parent = s;
            s = s->left;
        }
        r->key = s->key;
        if(s == r->right)
            r->right = s->right;
        else
            parent->left = s->right;
    }
    return r;


}

Main.cpp

#include "cBinarySearchTree.h"
#include <iostream>
using namespace std;
 
int main(){
    char cmd;
    int n, x;
    cBinarySearchTree<int> tree;
    cin>>n;
    for(int i = 0; i<n; i++){
        cin>>cmd>>x;
        switch(cmd){
        case 'I':
            tree.treeInsert(x);
            break;
        case 'D':
            tree.treeDelete(x);
            break;
        }
    }
    tree.treePrint();
    return 0;
}