#include <iostream>
#include <locale>
#include <limits>
#include <string>

using namespace std;

template<class T> class tree;

// Класс узел дерева
template<class T>
class tree_node
{
	friend class tree<T>;
private:
	tree_node<T>* _left;
	tree_node<T>* _right;
	T _data;
public:
	// Конструктор
	tree_node(void);
	tree_node(T data, tree_node* left=0, tree_node* right=0);
	virtual ~tree_node(void);
};

// Класс - дерево
template<class T>
class tree
{
private:
	tree_node<T>* _root;
	// Освобождает ресурсы
	void dispose();
protected:
	static void for_each(const tree_node<T>* const root , void (func)(const T&));
	static bool isContain(const tree_node<T>* const root,const T& item);
	void insert(tree_node<T>*& root,const T& data);
public:
	// Конструктор
	tree(void);
	tree(const tree& t);
	// Деструктор
	virtual ~tree(void);
	// Оператор равно
	const tree<T>& operator=(const tree<T>& right);
	// Добавляет элемент к дереву
	void add(const T& item);
	// Обходит дерево
	void for_each(void (func)(const T&)) const;
	// Проверяет содержит ли дерево элемент item
	bool isContain(const T& item) const;
};

void print(const wstring& val)
{
	wcout<<val<<endl;
}

int main()
{
	locale::global(locale("russian_russia.866"));

	// Дерево со строками
	tree<wstring> myTree;

	// Вводим строки
	wcout<<L"Вводите строки(пустая строка для завершения ввода):"<<endl;
	wstring str;
	while(true)
	{
		getline(wcin,str);
		if(str.empty())
		{
			break;
		}
		myTree.add(str);
	}

	// Распечатаем
	wcout<<L"Введены следующие строки:"<<endl;
	myTree.for_each(print);

	// Что ищем?
	wcout<<L"Введите искомую строку:"<<endl;
	getline(wcin,str);

	// Проверяем есть ли
	if(myTree.isContain(str))
	{
		wcout<<L"Найдена"<<endl;
	}
	else
	{
		wcout<<L"Не найдена"<<endl;
	}
	cout<<endl;
	system("PAUSE");
	return 0;
}

#pragma region class tree_node

// Конструктор
template<typename T>
tree_node<T>::tree_node(void)
:_left(0)
,_right(0)
{
}

template<typename T>
tree_node<T>::tree_node(T data, tree_node* left, tree_node* right)
:_left(left)
,_right(right)
,_data(data)
{
}

template<typename T>
tree_node<T>::~tree_node(void)
{
	if(_left)
	{
		delete _left;
	}
	if(_right)
	{
		delete _right;
	}
}

#pragma endregion

#pragma region class tree

// Конструктор
template<typename T>
tree<T>::tree(void)
:_root(0)
{
}

template<typename T>
tree<T>::tree(const tree& t)
:_root(0)
{
	t.for_each(&tree<T>::add,*this);
}

// Деструктор
template<typename T>
tree<T>::~tree(void)
{
	dispose();
}

template<typename T>
const tree<T>& tree<T>::operator=(const tree<T>& right)
{
	if(this!=&right)
	{
		dispose();
		right.for_each(&tree<T>::add,*this);
	}
	return *this;
}

// Уничтожает дерево
template<typename T>
void tree<T>::dispose()
{
	if(_root)
	{
		delete _root;
		_root=0;
	}
}


template<typename T>
void tree<T>::insert(tree_node<T>*& root,const T& data)
{
	if(root)
	{
		tree_node<T>* current=root;
		tree_node<T>* insertingPos;
		while(current && current->_data>data)
		{
			insertingPos=current;
			current=current->_left;
		}
		if(current)
		{
			insert(current->_right,data);
		}
		else
		{
			insertingPos->_left=new tree_node<T>(data,0,0);
		}
	}
	else
	{
		root=new tree_node<T>(data,0,0);
	}
}

template<typename T>
void tree<T>::add(const T& item)
{
	insert(_root,item);
}

template<typename T>
void tree<T>::for_each(void (func)(const T&)) const
{
	for_each(_root,func);
}

template<typename T>
void tree<T>::for_each(const tree_node<T>* const root , void (func)(const T&))
{
	if(root)
	{
		for_each(root->_left,func);
		func(root->_data);
		for_each(root->_right,func);
	}
}

// Вот собственно метод обхода и поиска
template<typename T>
bool tree<T>::isContain(const tree_node<T>* const root,const T& item)
{
	if(root)
	{
		if(root->_data<item)
		{
			return isContain(root->_right,item);
		}
		else
		{
			return (root->_data==item) || isContain(root->_left,item);
		}
	}
	else
	{
		return false;
	}
}

template<typename T>
bool tree<T>::isContain(const T& item) const
{
	return isContain(_root,item);
}

#pragma endregion

Вводите строки(пустая строка для завершения ввода):
строка 1
еще одна строка
а эту строку будем искать
ну хватит

Введены следующие строки:
а эту строку будем искать
еще одна строка
ну хватит
строка 1
Введите искомую строку:
а эту строку будем искать
Найдена