314 lines
6.4 KiB
C++
314 lines
6.4 KiB
C++
#include <conio.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <iostream.h>
|
|
#include <dos.h>
|
|
|
|
struct nodo{
|
|
int dato;
|
|
struct nodo *hi;
|
|
struct nodo *hd;
|
|
struct nodo *padre;
|
|
};
|
|
|
|
void insertar (struct nodo **,int);
|
|
int esvacio(struct nodo *);
|
|
void listar_ird(struct nodo *);
|
|
struct nodo* buscar_nodo(struct nodo*,int);
|
|
void eliminar_nodo(struct nodo**,struct nodo*);
|
|
void eliminar(struct nodo*,struct nodo*);
|
|
|
|
void main(void){
|
|
struct nodo *arbol=NULL,*aux=NULL;int n=0;char tecla=NULL;
|
|
do{
|
|
clrscr();
|
|
printf ("Inserta nuevo nodo:");
|
|
cin >> n;
|
|
aux=buscar_nodo(arbol,n);
|
|
if (aux==NULL){
|
|
insertar(&arbol,n);
|
|
printf ("\nPara finalizar de introducir nodos pulse ESC.");
|
|
tecla=getch();
|
|
}
|
|
else{
|
|
nosound();sound(500);delay(500);nosound();
|
|
}
|
|
}while (tecla!=27);
|
|
clrscr();
|
|
listar_ird(arbol);getch();
|
|
while (n!=0){
|
|
printf ("\nRaiz %d",arbol->dato);
|
|
printf("\nIndica el nodo a eliminar: \n");
|
|
cin >> n;
|
|
aux=buscar_nodo(arbol,n);
|
|
eliminar(arbol,aux);
|
|
listar_ird(arbol);getch();
|
|
}
|
|
|
|
}
|
|
|
|
|
|
int esvacio(struct nodo *p){
|
|
return(p==NULL);
|
|
}
|
|
|
|
void insertar (struct nodo **p,int n){
|
|
struct nodo *aux=NULL;
|
|
if ((aux=(struct nodo *)malloc(sizeof(struct nodo)))==NULL){
|
|
clrscr();
|
|
printf ("No hay memoria suficiente.");
|
|
getch();
|
|
exit(1);
|
|
}
|
|
else{
|
|
if (esvacio(*p)){
|
|
aux->dato=n;aux->hd=NULL;aux->hi=NULL;aux->padre=aux;
|
|
(*p)=aux;
|
|
}
|
|
else{
|
|
struct nodo **q=NULL;
|
|
q=p;int sw=1;
|
|
while (sw==1){
|
|
sw=0;
|
|
if ((*q)->dato<n && (*q)->hd!=NULL){
|
|
q=&((*q)->hd);sw=1;
|
|
}
|
|
if ((*q)->dato>n && (*q)->hi!=NULL){
|
|
q=&((*q)->hi);sw=1;
|
|
}
|
|
}
|
|
aux->dato=n;aux->hi=NULL;aux->hd=NULL;aux->padre=(*q);
|
|
if ((*q)->dato<n)
|
|
(*q)->hd=aux;
|
|
else
|
|
(*q)->hi=aux;
|
|
}
|
|
}
|
|
}
|
|
|
|
void listar_ird(struct nodo *p) { //int x,int y){
|
|
if (p!=NULL){
|
|
//gotoxy(x,y);
|
|
printf("%d ",p->dato);
|
|
listar_ird(p->hi);
|
|
listar_ird(p->hd);
|
|
}
|
|
}
|
|
|
|
struct nodo* buscar_nodo(struct nodo *p,int n){
|
|
if (p==NULL || n==p->dato)
|
|
return p;
|
|
else
|
|
if (n<p->dato)
|
|
return (buscar_nodo(p->hi,n));
|
|
else
|
|
return (buscar_nodo(p->hd,n));
|
|
}
|
|
|
|
void eliminar(struct nodo *tree,struct nodo *aux){
|
|
if (aux==NULL){
|
|
printf ("El nodo no existe");getch();
|
|
}
|
|
else{
|
|
if (aux->hi==NULL && aux->hd==NULL && aux->padre!=aux){
|
|
if((aux->padre)->hi==aux)
|
|
(aux->padre)->hi=NULL;
|
|
else
|
|
if((aux->padre)->hd==aux)
|
|
(aux->padre)->hd=NULL;
|
|
}
|
|
else
|
|
if(aux->padre==aux && aux->hi==NULL && aux->hd==NULL)
|
|
tree=NULL;
|
|
else
|
|
eliminar_nodo(&tree,aux);
|
|
free(aux);
|
|
listar_ird(tree);getch();
|
|
}
|
|
}
|
|
|
|
|
|
void eliminar_nodo(struct nodo**p,struct nodo*q){
|
|
if (q->padre!=q){
|
|
if (q->hi!=NULL){
|
|
if((q->hi)->hd==NULL){
|
|
if ((q->padre)->hd==q)
|
|
(q->padre)->hd=q->hi;
|
|
else
|
|
if((q->padre)->hi==q)
|
|
(q->padre)->hi=q->hi;
|
|
(q->hi)->padre=q->padre;
|
|
(q->hi)->hd=q->hd;
|
|
if (q->hd!=NULL)
|
|
((q->hi)->hd)->padre=q->hi;
|
|
}
|
|
else{
|
|
struct nodo *aux=NULL;
|
|
if ((aux=(struct nodo *)malloc(sizeof(struct nodo)))==NULL){
|
|
clrscr();
|
|
printf ("No hay memoria suficiente.");
|
|
getch();
|
|
exit(1);
|
|
}
|
|
else{
|
|
aux=(q->hi)->hd;
|
|
while(aux->hd!=NULL)
|
|
aux=aux->hd;
|
|
if (aux->hi!=NULL)
|
|
eliminar_nodo(p,aux);
|
|
else
|
|
if ((aux->padre)->hd==aux)
|
|
(aux->padre)->hd=NULL;
|
|
else
|
|
if((aux->padre)->hi==aux)
|
|
(aux->padre)->hi=NULL;
|
|
// else
|
|
// if ((q->hd)->hd==aux)
|
|
// (q->hd)->hd=NULL;
|
|
// else
|
|
// if((q->hd)->hi==aux)
|
|
// (q->hd)->hi=NULL;
|
|
if ((q->padre)->hd==q)
|
|
(q->padre)->hd=aux;
|
|
else
|
|
if ((q->padre)->hi==q)
|
|
(q->padre)->hi=aux;
|
|
aux->padre=q->padre;
|
|
aux->hi=q->hi;
|
|
if (aux->hi!=NULL)
|
|
(aux->hi)->padre=aux;
|
|
aux->hd=q->hd;
|
|
if (aux->hd!=NULL)
|
|
(aux->hd)->padre=aux;
|
|
}
|
|
}
|
|
}
|
|
else{
|
|
if (q->hd!=NULL){
|
|
if((q->hd)->hi==NULL){
|
|
if ((q->padre)->hd==q)
|
|
(q->padre)->hd=q->hd;
|
|
else
|
|
if((q->padre)->hi==q)
|
|
(q->padre)->hi=q->hd;
|
|
(q->hd)->padre=q->padre;
|
|
(q->hd)->hi=q->hi;
|
|
if (q->hi!=NULL)
|
|
((q->hd)->hi)->padre=q->hd;
|
|
}
|
|
else{
|
|
struct nodo *aux=NULL;
|
|
if ((aux=(struct nodo *)malloc(sizeof(struct nodo)))==NULL){
|
|
clrscr();
|
|
printf ("No hay memoria suficiente.");
|
|
getch();
|
|
exit(1);
|
|
}
|
|
else{
|
|
aux=(q->hd)->hi;
|
|
while(aux->hi!=NULL)
|
|
aux=aux->hi;
|
|
if (aux->hd!=NULL)
|
|
eliminar_nodo(p,aux);
|
|
else
|
|
if ((aux->padre)->hd==aux)
|
|
(aux->padre)->hd=NULL;
|
|
else
|
|
if((aux->padre)->hi==aux)
|
|
(aux->padre)->hi=NULL;
|
|
// else
|
|
// if ((q->hd)->hd==aux)
|
|
// (q->hd)->hd=NULL;
|
|
// else
|
|
// if((q->hd)->hi==aux)
|
|
// (q->hd)->hi=NULL;
|
|
if ((q->padre)->hd==q)
|
|
(q->padre)->hd=aux;
|
|
else
|
|
if ((q->padre)->hi==q)
|
|
(q->padre)->hi=aux;
|
|
aux->padre=q->padre;
|
|
aux->hi=q->hi;
|
|
if (aux->hi!=NULL)
|
|
(aux->hi)->padre=aux;
|
|
aux->hd=q->hd;
|
|
if (aux->hd!=NULL)
|
|
(aux->hd)->padre=aux;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
else{
|
|
if (q->hi!=NULL){
|
|
if((q->hi)->hd==NULL){
|
|
(q->hi)->hd=(*p)->hd;
|
|
(*p)=q->hi;
|
|
(q->hi)->padre=q->hi;
|
|
|
|
}
|
|
else{
|
|
struct nodo *aux=NULL;
|
|
if ((aux=(struct nodo *)malloc(sizeof(struct nodo)))==NULL){
|
|
clrscr();
|
|
printf ("No hay memoria suficiente.");
|
|
getch();
|
|
exit(1);
|
|
}
|
|
else{
|
|
aux=(q->hi)->hd;
|
|
while(aux->hd!=NULL)
|
|
aux=aux->hd;
|
|
if (aux->hi!=NULL)
|
|
eliminar_nodo(p,aux);
|
|
(*p)=aux;
|
|
aux->padre=aux;
|
|
aux->hi=q->hi;
|
|
if (aux->hi!=NULL)
|
|
(aux->hi)->padre=aux;
|
|
aux->hd=q->hd;
|
|
if (aux->hd!=NULL)
|
|
(aux->hd)->padre=aux;
|
|
}
|
|
}
|
|
}
|
|
else{
|
|
if (q->hd!=NULL){
|
|
if((q->hd)->hi==NULL){
|
|
(*p)=q->hd;
|
|
(q->hd)->padre=q->hd;
|
|
}
|
|
else{
|
|
struct nodo *aux=NULL;
|
|
if ((aux=(struct nodo *)malloc(sizeof(struct nodo)))==NULL){
|
|
clrscr();
|
|
printf ("No hay memoria suficiente.");
|
|
getch();
|
|
exit(1);
|
|
}
|
|
else{
|
|
aux=(q->hd)->hi;
|
|
while(aux->hi!=NULL)
|
|
aux=aux->hi;
|
|
if (aux->hd!=NULL)
|
|
eliminar_nodo(p,aux);
|
|
(*p)=aux;
|
|
if ((aux->padre)->hd==aux)
|
|
(aux->padre)->hd=NULL;
|
|
else
|
|
if((aux->padre)->hi==aux)
|
|
(aux->padre)->hi=NULL;
|
|
aux->padre=aux;
|
|
aux->hi=q->hi;
|
|
if (aux->hi!=NULL)
|
|
(aux->hi)->padre=aux;
|
|
aux->hd=q->hd;
|
|
if (aux->hd!=NULL)
|
|
(aux->hd)->padre=aux;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|