arbol que ingrese, elimine y liste datos

[gervasioe]

Tengo un problema para la eliminación de datos, depende que dato elimine me lo raliza bien o no. Acá dejo el código

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <cassert>

using namespace std;

struct arbol{
int dato;
struct arbol *izq;
struct arbol *der;
};

void imprime(struct arbol *);
void reemplazar(struct arbol *, struct arbol *);

int main(int argc, char *argv[])
{
struct arbol *raiz, *marca, *actual, *p;
int d,v;
char opcion;


printf("Presione i para ingresar valores y para finalizar ingrese 1000\n");
printf("Presione b para borrar un valor\n");
printf("Presione l para listarlos\n");
printf("Presione s para salir\n");

cin>>opcion;
do{
switch(opcion)
{
case 'i':{
printf("Ingrese el primer valor\n");
raiz= new struct arbol;
assert(raiz);
cin>>raiz->dato;
raiz->izq=0;
raiz->der=0;

while(d!=1000)
{
printf("Ingrese el siguiente valor\n");
actual= new struct arbol;
cin>>d;
if(d!=1000)
{
marca=raiz;
while(marca!=0)
{
actual=marca;
if(d < actual->dato)
marca= actual->izq;
else
marca=actual->der;
}

p=new struct arbol;
p->izq=0;
p->der=0;
p->dato=d;
if(d<actual->dato)
actual->izq=p;
else
actual->der=p;
}

}
printf("Los datos ordenados son:\n");
imprime(raiz);
break;
}
case 'b':
{
cout<<"Ingrese el valor a borrar"<<endl;
cin>>v;
marca=raiz;
while(marca->dato!=v) //busca el nodo a borrar
{
actual=marca;
if(v<marca->dato)
marca=marca->izq;
else
marca=marca->der;
}
p=marca;
if(marca->der!=0) //busca el el valor mas proximo
{ //para reemplazarlo por él
marca=marca->der;
actual->der=marca;
while(marca->izq!=0)
{
marca=marca->izq;
actual->izq=marca;
}
p->dato=marca->dato;
actual->izq=0;
free(marca);
}
else
{ //En el caso de que no
//tenga hijo derecho hace
//que el padre del
if(marca->izq!=0) //nodo a borrar apunte
{ //directamente al hijo
marca=marca->izq; //izquierdo del nodo a borrar
actual->izq=marca;
free(p);
}
else
if(p->dato<actual->dato)
actual->izq=0;
else actual->der=0;
free(p); //Si ambos hijos del nodo a
} //borrar son nulos hace que el padre
break; //apunte a nulo
}
case 'l':
{
printf("Los datos ordenados son:\n");
imprime(raiz);
printf("\n\n");
break;
}
default: break;
}
printf("\nPresione i para ingresar valores\n");
printf("Presione b para borrar un valor\n");
printf("Presione l para listarlos\n");
printf("Presione s para salir\n");

cin>>opcion;
}while(opcion!='s');

system("PAUSE");
return 0;
}
void imprime(struct arbol *p)
{
if(p->izq!=0)
imprime(p->izq);
printf("==> %d\n",p->dato);
if(p->der!=0)
imprime(p->der);
}