Tenho a seguinte árvore binária :
Definida pela seguinte estruta de dado :
typedef struct Node{
int data;
struct Node * left;
struct Node * right;
} node;
typedef struct Node * root;
E tenho a seguinte função :
void removeNode(root * start, int key){
node * ant;
if (*start == NULL){
return ;
}
//Verifica se a chave é igual ao nó naquele momento
if((*start)->data == key){
//Verifica se é uma folha
if((*start)->left == NULL && (*start)->right == NULL){
free(*start);
*start = NULL;
return;
}
//Verifica se tem somente um descendente à esquerda
else if((*start)->left != NULL && (*start)->right == NULL){
ant = (*start)->left;
free(*start);
*start = NULL;
return;
}
//Verifica se tem somente um descendente à direita
else if((*start)->left == NULL && (*start)->right != NULL){
ant = (*start)->right;
free(*start);
*start = NULL;
return;
}
} else {
ant = *start;
removeNode(&(*start)->left,key);
ant = *start;
removeNode(&(*start)->right,key);
}
}
Preciso remover os nós com as seguintes especificações:
- Caso o nó seja uma folha, simplesmente remover ele.
- Ao se remover um nó de chave x, com apenas 1 descendente, o ancestral de x será o ancestral do descendente de x.
O meu problema está em pegar o antecedente, tentei desta forma, mas quando tento remover o 8, por exemplo, o ant
fica no 6.
Como proceder?