Primero dejemos en claro (o no tan en claro, pues sere un poco vago) que es un "arbol binario", un arbol binario para nosotros es una estructura de datos en la cual cada "nodo" tiene a lo sumo dos hijos o sub-arboles. Dare una definición recursiva que nos ayudara mucho, se basa en las siguientes dos reglas de construcción:

  1) () : ArbBin
  2) Si izq,der : ArbBin y x : Dato entonces (izq,x,der) : ArbBin

Esta definición recursiva nos trae "de regalo" un teorema que llamamos el esquema de recursión estructural, basicamente este nos dice que para definir una función sobre arboles basta definirla para el arbol vacio y luego definirla a partir de su valor en los subarboles. Intuitivamente tenemos el siguiente diagrama:

  f : BinArb -> ...
  f( () ) = ...
  f( (izq,x,der) ) = ... f(izq) ... f(der) ...

Ahora, todo lo anterior es puramente teorico, para trabajar con arboles en c++ debemos elegir una representación (o "modelo"), en nuestro caso los representaremos de la siguiente forma:

  struct nodo_arbol{
    Dato x;
    nodo_arbol* izq;
    nodo_arbol* der;
  };

Donde Dato es algun tipo de dato primitivo o creado por nosotros.
Con esta representación, un árbol no sera mas que un puntero al primer nodo (que llamaremos raíz) de nuestro arbol, el arbol vacio lo representaremos como un puntero a NULL.
A partir de ahora utilizaremos la siguiente abreviacion:

  typedef nodo_arbol* Arbol;

Comencemos con algunos algoritmos sencillos, por la propia definición recursiva de arbol binario generalmente diseñaremos algoritmos recursivos (aunque algunas cosas puntuales pueden implementarse de manera iterativa), para esto podemos pensar que utilizamos el teorema de recursion estructural para posteriormente traducir esa función abstracta a "codigo", por ejemplo calcular la cantidad de nodos de un arbol:

  int cantidadNodos(Arbol t){
    if(t == NULL){
      return 0;
    }else{
      return 1 + cantidadNodos(t->izq) + cantidadNodos(t->der);
    }
  }

Similarmente podemos calcular la altura (la cantidad de "niveles" del arbol) de la siguiente manera:

  int cantidadNodos(Arbol t){
    if(t == NULL){
      return 0;
    }else{
      return 1 + max(cantidadNodos(t->izq),cantidadNodos(t->der));
    }
  }