Определить, есть ли в данном бинарном дереве два одинаковых элемента

#ifndef _avltree_
#define _avltree_
 
using namespace std;
 
enum Order {Preorder, Inorder, Postorder}; //порядок обхода дерева
 
template <class T> class Ttreenode //Структура узла дерева
{
public:
    T key; //хранимый объект
    unsigned int copies; //число копий объекта
    int height; //высота узла (отсчитывается от самого нижнего листа поддеревьев)
    Ttreenode * left; //лист имеет высоту 1
    Ttreenode * right;
    //конструктор
    Ttreenode(T k) {key = k; copies = 1; left = right = NULL; height = 1;};
};
 
template <class T> class Tavltree
{
    private:
        unsigned int keys;
        Ttreenode<T> * main_root;
        int height(Ttreenode<T> * ptr);
        int balance(Ttreenode<T> * ptr);
        void update_height(Ttreenode<T> * ptr);
        Ttreenode<T> * rotate_right(Ttreenode<T> * ptr);
        Ttreenode<T> * rotate_left(Ttreenode<T> * ptr);
        Ttreenode<T> * rebalance(Ttreenode<T> * ptr);
        Ttreenode<T> * add_node(Ttreenode<T> * root,const T &key);
        Ttreenode<T> * free_tree(Ttreenode<T> * root);
        Ttreenode<T> * find_min(Ttreenode<T> * ptr);
        Ttreenode<T> * remove_min(Ttreenode<T> * ptr);
        Ttreenode<T> * remove_node(Ttreenode<T> * root, const T &key); 
        void walk(Ttreenode<T> * ptr, Order order, int level, void (*callback)(Ttreenode<T> * , int));
        Ttreenode<T> * find_key(Ttreenode<T> * root, T key);
    public:
        Tavltree() {main_root = NULL; keys = 0;}; //конструктор по умолчанию
        unsigned int insert(const T &key);//добавляет объект в дерево, возвращает количество копий его после этого
        unsigned int find(const T &key);// ищет объект в дереве, возвращает количество копий
        unsigned int remove(const T&key);//удаляет объект, возвращает количество оставшихся копий
        ~Tavltree();
};
 
//Рекурсивный обход дерева
template <class T>
void Tavltree<T>::walk(Ttreenode<T> * ptr, Order order, int level, void (*callback)(Ttreenode<T> * , int))
{
    if (ptr==NULL) return;
    if ((order==Preorder)&&(callback!=NULL)) callback(ptr, level); 
    walk(ptr->left, order, level+1, callback);
    if ((order==Inorder)&&(callback!=NULL)) callback(ptr, level);
    walk(ptr->right, order, level+1, callback);
    if ((order==Postorder)&&(callback!=NULL)) callback(ptr, level); 
}
 
//Возвращает высоту поддерева для узла ptr
template <class T>
int Tavltree<T>::height(Ttreenode<T> * ptr)
{
    if (ptr==NULL) return 0; else return ptr->height;
}
//Возвращает разницу высот левого и правого поддеревьев узла ptr
template <class T>
int Tavltree<T>::balance(Ttreenode<T> * ptr)
{
    return height(ptr->right)-height(ptr->left);
}
//Обновляет поле height узла ptr на основе полей height его сыновей
template <class T>
void Tavltree<T>::update_height(Ttreenode<T> * ptr)
{
    ptr->height = max(height(ptr->left),height(ptr->right))+1;
}
// правый поворот вокруг узла ptr
template <class T>
Ttreenode<T> * Tavltree<T>::rotate_right(Ttreenode<T> * ptr)
{
    Ttreenode<T> * tmp = ptr->left;
    ptr->left = tmp->right;
    tmp->right = ptr;
    update_height(ptr);
    update_height(tmp);
    return tmp;
}
// левый поворот вокруг узла ptr
template <class T>
Ttreenode<T> * Tavltree<T>::rotate_left(Ttreenode<T> * ptr)
{
    Ttreenode<T> * tmp = ptr->right;
    ptr->right = tmp->left;
    tmp->left = ptr;
    update_height(ptr);
    update_height(tmp);
    return tmp;
}
// балансировка узла ptr
template <class T>
Ttreenode<T> * Tavltree<T>::rebalance(Ttreenode<T> * ptr)
{
    update_height(ptr);
    if(balance(ptr)==2)
        {
        if(balance(ptr->right) < 0) ptr->right = rotate_right(ptr->right);
        return rotate_left(ptr);
        }
    if(balance(ptr)==-2)
        {
        if(balance(ptr->left) > 0) ptr->left = rotate_left(ptr->left);
        return rotate_right(ptr);
        }
    return ptr;
}
//Рекурсивный поиск и добавление узла, с последующей балансировкой
template <class T>
Ttreenode<T> * Tavltree<T>::add_node(Ttreenode<T> * root,const T &key)
{
    if (root == NULL)
        {
        Ttreenode<T> * tmp = new Ttreenode<T>(key);
        if (tmp!=NULL)
            {
            keys = 1;
            return tmp;
            }
        else
            throw "Not enough memory ! (add_node)";
            exit(EXIT_FAILURE);
        }
    if (key < root->key)
        root->left = add_node(root->left, key);
    else if (key > root->key)
        root->right = add_node(root->right, key);
    else
        {//если узел существует, то меняем содержимое copies
        root->copies++;
        keys = root->copies;
        return root;
        }
    return rebalance(root);
};
 
//удаляет всё дерево
template <class T>
Ttreenode<T> * Tavltree<T>::free_tree(Ttreenode<T> * root)
{
    if (root!=NULL)
        {
        free_tree(root->left);
        free_tree(root->right);
        delete root;
        }
    return NULL;
}
// Поиск узла с ключом key в дереве root
// если нет узла, возвращает NULL иначе указ. на найденный узел
template <class T>
Ttreenode<T> * Tavltree<T>::find_key(Ttreenode<T> * root, T key)
{
    while (root!=NULL)
        {
        if (key == root->key) break;
        root = (key < root->key)?root->left:root->right;
        }
    return root;
}
// Поиск узла с минимальным ключом в поддереве ptr
// просто идём по левым ветвям
template <class T>
Ttreenode<T> * Tavltree<T>::find_min(Ttreenode<T> * ptr)
{
    while (ptr->left!=NULL) ptr=ptr->left;
    return ptr;
}
 
// удаление узла с минимальным ключом из поддерева ptr
template <class T>
Ttreenode<T> * Tavltree<T>::remove_min(Ttreenode<T> * ptr) 
{
    if (ptr->left == NULL) return ptr->right;
    ptr->left = remove_min(ptr->left);
    return rebalance(ptr);
}
 
// удаление узла с ключом key из дерева root
template <class T>
Ttreenode<T> * Tavltree<T>::remove_node(Ttreenode<T> * root, const T &key) 
{
    if (root==NULL) {keys = 0; return NULL;}
    if (key < root->key)
        root->left = remove_node(root->left, key);
    else if (key > root->key)
        root->right = remove_node(root->right, key);    
    else //нашли узел
        {
        //если несколько копий, то удаляем по одной
        keys = --(root->copies);
        if (keys) return root;
        //запоминаем потомков
        Ttreenode<T> * left_node = root->left;
        Ttreenode<T> * right_node = root->right;
        delete root; //удаляем узел
        //если нет потомков справа то выходим
        if( right_node==NULL ) return left_node;
        //а если есть, то ищем минимальный
        Ttreenode<T> * min = find_min(right_node);
        //и подвешиваем
        min->right = remove_min(right_node);
        min->left = left_node;
        return rebalance(min);
        }
    return rebalance(root);
}
 
template<class T>
Tavltree<T>::~Tavltree()
{
    main_root = free_tree(main_root);
}
 
template <class T>
unsigned int Tavltree<T>::insert(const T &key)
{
    main_root = add_node(main_root, key);
    return keys;
}
 
template <class T>
unsigned int Tavltree<T>::find(const T &key)
{
    Ttreenode<T> * ptr = main_root;
    unsigned int copies = 0;
    ptr = find_key(ptr, key);
    if (ptr != NULL) copies = ptr->copies;
    return copies;
}
 
//удаляет узел с ключом key возвращает сколько копий ключа осталось
template <class T>
unsigned int Tavltree<T>::remove(const T&key)
{
    main_root = remove_node(main_root, key);
    return keys;
}
 
#endif

#include <iostream>
#include "avltree.hpp"
 
using namespace std;
 
void main()
{
    Tavltree<int> tree;
    cout << "insert (5) returned copies=" << tree.insert(5) << endl;
    cout << "insert (3) returned copies=" << tree.insert(3) << endl;
    cout << "insert (2) returned copies="<< tree.insert(2) << endl;
    cout << "insert (3) returned copies="<< tree.insert(3) << endl;
    cout << "search (2) returned copies="<< tree.find(2) << endl;
    cout << "search (3) returned copies="<< tree.find(3) << endl;
    cout << "delete (3) returned copies="<< tree.remove(3) << endl;
    cout << "search (3) returned copies="<< tree.find(3) << endl;
    system("pause");
}