C++ Balanceamento Arvore Binária - Espinha Dorsal

[saulogoiana]

Olá companheiros!
 

O problema do meu código é que não estou sabendo como tratar os ponteiros, na última linha parece que a variável tmp1 não está "caminhando" para o endereço à direita fazendo com que fique infinitamente no laço while.

 

Meu resultado final deve ser uma árvore balanceada usando o algoritmo DSW.

struct NODE
{
	int valor;
	struct NODE *dir;
	struct NODE *esq;
};
typedef NODE *T;

void espinhadorsal(T *raiz){
	T *tmp1,*tmp2;
	tmp2 = tmp1 = raiz;
	
	while(tmp1!=NULL){
		if((*tmp1)->esq != NULL){
			tmp2 = tmp1;
			(*tmp1) = (*tmp1)->esq;
			if((*tmp1)->esq!=NULL){
				(*tmp1)->esq->dir = (*tmp1)->dir;//1
				(*tmp2)->esq = (*tmp1)->dir;//2
			}
			(*tmp1)->dir = *tmp2;//3
			raiz = tmp1;//4
			tmp1 = raiz;
		}
		else{
			(*tmp1)=(*tmp1)->dir;
		}
	}
	
	return;	
}