Vamos a implementar una interfaz de conjunto en C++, utilizando como representación interna un árbol binario de búsqueda (ABB).

Definiremos la clase paramétrica Conjunto<T> donde T será un tipo con un orden total estricto <.

Interfaz

Nos gustaría que las siguientes operaciones sean visibles al usuario:

• Crear un conjunto nuevo (vacío)
• Insertar un elemento
• Decidir si un elemento pertenece al conjunto
• Remover un elemento
• Obtener la cantidad de elementos
• Mostrar los elementos

Como extras nos gustaría:

• Obtener el mínimo
• Obtener el máximo
• Obtener el elemento siguiente a otro

template <class T>
class Conjunto {
	public:
		Conjunto();
		void insertar(const T&);
		bool pertenece(const T&);
		void remover(const t&);
		const T& minimo() const;
		const T& maximo() const;
		unsigned int cardinal() const;
		void mostrar(ostream&) const;
		const T& siguiente(const T&) const;
	private:
		/*...*/
};

Representación de nodos

Definiremos la estructura Nodo para representar los nodos del ABB. Lo haremos en la parte privada de la clase Conjunto<T> ya que fuera de esta clase la estructura no tiene sentido.