elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Borrar nodo de un arbol
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Borrar nodo de un arbol  (Leído 7,492 veces)
karmi

Desconectado Desconectado

Mensajes: 21



Ver Perfil
Borrar nodo de un arbol
« en: 10 Diciembre 2010, 04:29 am »

ayuda por favor, necesit borrar nodo de mi arbol...agradeceria me ayudasen, posteo mi codigo
Código
  1. #include <iostream.h>
  2. #include <windows.h>
  3.  
  4.  
  5. struct Nodo
  6. {
  7. Nodo *izq;
  8. int dato;
  9. Nodo *der;
  10. };
  11.  
  12. class arbolbinario
  13. {
  14. private:
  15. Nodo *raiz;
  16. public:
  17. arbolbinario()
  18. {
  19. raiz=NULL;
  20. }
  21. void insertar(int d)
  22. {
  23. Nodo *nuevo;
  24. nuevo = new Nodo();
  25. nuevo->izq= NULL;
  26. nuevo->dato=d;
  27. nuevo->der=NULL;
  28.  
  29. if (raiz==NULL)
  30. {
  31. raiz=nuevo;
  32. }
  33. else
  34. {
  35. Nodo *temp, *a;
  36. int b=0;
  37. temp = raiz;
  38. a = NULL;
  39. while(temp!=NULL)
  40. {
  41. a = temp;
  42. if(nuevo->dato<temp->dato)
  43. {
  44. temp = temp->izq;
  45. b=1;
  46. }
  47. else if (nuevo->dato>temp->dato)
  48. {
  49. temp = temp->der;
  50. b=2;
  51. }
  52. }
  53. if (b==1)
  54. {
  55. a->izq=nuevo;
  56. }
  57. else if (b==2)
  58. {
  59. a->der=nuevo;
  60. }
  61. }
  62.  
  63. }
  64.  
  65. void MostrarIn()
  66. {
  67. Nodo *temp;
  68. temp = raiz;
  69. MostrarInorden (temp);
  70. }
  71. void MostrarInorden(Nodo *T)
  72. {
  73. if (T!=NULL)
  74. {
  75. MostrarInorden(T->izq);
  76. cout << T->dato << endl;
  77. MostrarInorden(T->der);
  78. }
  79. }
  80. void MostrarPr()
  81. {
  82. Nodo *temp;
  83. temp = raiz;
  84. MostrarPreorden (temp);
  85. }
  86. void MostrarPreorden(Nodo *T)
  87. {
  88. if (T!=NULL)
  89. {
  90. cout << T->dato << endl;
  91. MostrarPreorden(T->izq);
  92. MostrarPreorden(T->der);
  93. }
  94. }
  95. void mostrarpost()
  96. {
  97. Nodo *temp;
  98. temp=raiz;
  99. mostrarpostorden(temp);
  100.  
  101. }
  102. void mostrarpostorden(Nodo *T)
  103. {
  104. if (T!=NULL)
  105. {
  106. cout<<T->dato<<endl;
  107. mostrarpostorden(T->der);
  108. mostrarpostorden(T->izq);
  109. }
  110. }
  111.  
  112. };
  113.  
  114. int eliminar(int n)
  115. *****ayuda
  116.  
  117. void main (void)
  118. {
  119. arbolbinario numeros;
  120. int op, n;
  121. do
  122. {
  123.  
  124. cout << "A R B O L B I N A R I O" << endl<<endl;
  125. cout << "1.- Insertar nodo"<< endl;
  126. cout << "2.- Mostrar inorden"<< endl;
  127. cout << "3.- Mostrar preorden"<< endl;
  128. cout << "4.- Mostrar postorden"<< endl;
  129. cout << "5.- eliminar numero"<< endl;
  130. cout << "6.- Salir"<< endl << endl;
  131.  
  132. cout << "Elige una opcion-> ";
  133. cin >> op;
  134.  
  135.  
  136. switch(op)
  137. {
  138. case 1:
  139. cout << "Introduce el numero: ";
  140. cin >> n;
  141. numeros.insertar(n);
  142. break;
  143. case 2:
  144. cout << "Inorden"<<endl;
  145. numeros.MostrarIn();
  146. break;
  147. case 3:
  148. cout << "Preorden"<<endl;
  149. numeros.MostrarPr();
  150. break;
  151. case 4:
  152. cout << "Postorden"<<endl;
  153. numeros.mostrarpost();
  154.  
  155. break;
  156. case 5:
  157. cout<<"introduce el numero a eliminar: "<<endl;
  158. numeros.eliminar();
  159. cout<<"numero eliminado"<<endl;
  160.  
  161. case 6:
  162. default:
  163.  
  164.  
  165. cout << "Bye!!!"<<endl;
  166. }
  167.  
  168. }while(1);
  169.  
  170. }
  171.  
  172.  


« Última modificación: 10 Diciembre 2010, 17:10 pm por Littlehorse » En línea

Bhrentox

Desconectado Desconectado

Mensajes: 98



Ver Perfil
Re: Borrar nodo de un arbol
« Respuesta #1 en: 10 Diciembre 2010, 06:12 am »

La verdad no he checado tu codigo pero espero te sirva este que hice hace ya bastante tiempo ytambien tiene la opcion de eliminar espero te sirva porque la verdad no recuerdo mucho de estas cosas pero espero te sirva de algo

Código
  1. #include<conio.h>
  2. #include<stdio.h>
  3. #include<iostream.h>
  4. #include<stdlib.h>
  5. #include<dos.h>
  6. struct nodo
  7. {
  8. int valor;
  9. struct nodo*sig;
  10. }*cab;
  11. void insertar(int num);
  12. void mostrar(void);
  13. void BorrarTodo(void);
  14. void Eliminar(int num);
  15. void insertord(int num);
  16.  
  17.  
  18. void main (void)
  19. {
  20. int op, num;
  21. cab=NULL;
  22. while(1)
  23. {
  24. clrscr();
  25. printf("1.-Insertar un nodo.\n2.-Eliminar un nodo.\n3.-Mostrar\n4.-Insettar nodos en orden\n0.-Salir\n");
  26. printf("\nElige una opcion: ");
  27. scanf("%d",&op);
  28. switch(op)
  29. {
  30. case 1:
  31. printf("Valor del nodo que deseas insertar: ");
  32. scanf("%d",&num);
  33. insertar(num);
  34. break;
  35. case 2:
  36. printf("Dame el valor del nodo a eliminar: ");
  37. scanf("%d",&num);
  38. Eliminar(num);
  39. break;
  40. case 3:
  41. mostrar();
  42. break;
  43. case 4:
  44. printf("Valor del nodo que deseas insertar: ");
  45. scanf("%d",&num);
  46. insertord(num);
  47. break;
  48. case 0:
  49. BorrarTodo();
  50. exit(0);//para usar exit debes declarar stdlib.h
  51. break;
  52. default:
  53. printf("ERROR Opcion incorrecta");
  54. getch();
  55.  
  56.  
  57.  
  58. }
  59. getch();
  60. }
  61. }
  62. void insertar(int num)
  63. {
  64. nodo *aux,*nuevo;
  65. aux=cab;
  66. nuevo=new nodo;
  67. nuevo->valor=num;
  68. nuevo->sig=NULL;
  69. if(cab==NULL)
  70. cab=nuevo;
  71.  
  72. else
  73. {
  74. while(aux->sig!=NULL)
  75. aux=aux->sig;
  76. aux->sig=nuevo;
  77.  
  78. }
  79. }
  80. void mostrar()
  81. {
  82. nodo *aux; //Aux es un apuntador
  83. aux=cab; //En esta line aux toma la direccion de cab
  84. while(aux!=NULL)
  85. {
  86. printf("%d, ",aux->valor);
  87. aux=aux->sig;
  88. }
  89. }
  90. void BorrarTodo(void)
  91. {
  92. nodo *aux;
  93. aux=cab;
  94. while(aux!=NULL)
  95. {
  96. cab=aux->sig;
  97. delete aux;
  98. aux=cab;
  99. }
  100. }
  101.  
  102. void Eliminar(int num)
  103. {
  104. nodo *aux,*aux2, *prev;
  105. int c=0;
  106. aux=cab;
  107.  
  108. while(c!=1)
  109. {
  110. if(aux->valor==num)
  111. {
  112. c=1;
  113. }
  114. else{
  115. prev=aux;
  116. aux=aux->sig;
  117. }
  118. }
  119.  
  120. if(c==1)
  121. {
  122. if(prev->sig==NULL)
  123. {
  124. cab=cab->sig;
  125. delete aux;
  126. }
  127. else
  128. {
  129. aux2 = aux->sig;
  130. prev->sig = aux2;
  131. delete aux;
  132. }
  133. }
  134.  
  135.  
  136. }
  137.  
  138.  
  139.  
  140. void insertord(int num)
  141. {
  142. nodo *aux,*nuevo,*aux2,*prev;
  143. int c=0;
  144. aux2=cab;
  145. nuevo=new nodo;
  146. // nuevo->valor=num;
  147. while(aux2!=NULL)
  148. {
  149. if(aux2->valor>=num)
  150. {
  151.  
  152. prev->sig=nuevo;
  153. nuevo->valor=num;
  154. nuevo->sig=aux2;
  155. cab=prev;
  156. aux2=NULL;
  157. c=1;
  158. }
  159. prev=aux2;
  160. aux2=aux2->sig;
  161. }
  162. if(aux2==NULL)
  163. if(c==0)
  164. {
  165. insertar(num);
  166. }
  167. else
  168. {
  169. delete aux2;
  170. }
  171. }


« Última modificación: 10 Diciembre 2010, 17:10 pm por Littlehorse » En línea

"Enseñar a los niños el uso de software libre en las escuelas, formará individuos con sentido de libertad“
“Microsoft no es el diablo, sólo hacen sistemas operativos vulgares.”
"No temo a los ordenadores; lo que temo es quedarme sin ellos"
"Una vez un ordenador me venció jugando al ajedrez, pero no me opuso resistencia cuando pasamos al kick boxing"
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Borrar nodo de un arbol
« Respuesta #2 en: 10 Diciembre 2010, 18:02 pm »

¡Buenas!

Para borrar un nodo, tienes que seguir los siguientes pasos.

1- Si es un nodo hoja, lo eliminas y pones a NULL el puntero del padre que aputaba a este.

2- Si es un nodo con un solo hijo, el hijo sera el nodo de reemplazo.

3- Si es un nodo con dos hijos, el nodo de reemplazo puede ser o bien el menor de los nodos mayores que el que quieres borrar (el nodo mas a la izquierda del subarbol derecho), ya que este sera mayor que los de la izquierda pero menor que cualquier otro de la derecha, o sino puedes utilizar el mayor de los nodos menores (el nodo mas a la derecha en el subarbol izquierdo) ya que este sera mayor que todos los menores que el nodo que quieres sustituir, pero menor que los mayores.  :rolleyes:

3.1 - Si utilizas el menor de los nodos mayores, y este tiene un subarbol derecho (el subarbol de los valores mayores que el nodo de reemplazo), tendras que recorrerlo por la derecha hasta alcanzar el mayor valor. Al ser el mayor valor del arbol que tiene como raiz el nodo de reemplazo, este valor seguira siendo mayor que el valor que quieres reemplazar. Pero al partir del valor mas pequeño entre los valores mayores, sera menor que cualquier otro valor del subarbol derecho que sea mayor que el del nodo de reemplazo, por lo tanto tendras que colgar el subarbol derecho del nodo que quieres reemplazar como subarbol derecho del mayor nodo mayor que el menor de los nodos mayores. Como hemos cogido como referencia el menor de los nodos mayores, el subarbol izquierdo de dicho nodo sera nulo, y por lo tanto puedes colgar el subarbol izquierdo del nodo quieres eliminar del nodo izquierdo del menor de los nodos mayores que el que quieres eliminar. Ahora que ya tienes construido el arbol con raiz el nodo de reemplazo de forma correcta, ya puedes eliminar el nodo que querias eliminar, y el puntero del padre que señalaba al nodo que has eliminado deberas apuntarlo al nodo de reemplazo. Evidentemente, si quieres eliminar el nodo raiz, no tendras padre, pero esto no supone ningun problema, ya que el nodo de reemplazo, por como hemos hecho las operaciones de sustitucion del nodo que se quiere eliminar por el de reemplazo, cumple todas la propiedades para ser el nuevo nodo raiz.

3.2- Si eliges como nodo de reemplazo el mayor de los nodos menores, los pasos que tendras que seguir son los anteriores, cambiando mayor por menor y aplicando sentido comun.

Ya ves que explicado es cosa de  :rolleyes: :rolleyes: :rolleyes:, pero en canto te pongas a traducirlo a codigo, lo veras mas claro y lo asimilaras mejor.

¡Saludos!
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Eliminar nodo en un arbol binario
.NET (C#, VB.NET, ASP)
DaNuK 4 29,296 Último mensaje 6 Diciembre 2010, 20:19 pm
por DaNuK
[C] Eliminando Nodo de Arbol Binario (Solucionado)
Programación C/C++
AlbertoBSD 5 16,182 Último mensaje 31 Mayo 2016, 05:01 am
por AlbertoBSD
Documentar función para borrar nodo según petición del usuario en C.
Programación C/C++
NOB2014 4 3,204 Último mensaje 16 Julio 2016, 02:59 am
por NOB2014
leer un documento HTML,cada etiqueta debe guardarse en un nodo de un árbol
Programación C/C++
mcMario 0 1,940 Último mensaje 12 Diciembre 2016, 02:40 am
por mcMario
Insertar nodo en Arbol Generico
Software
EASoft 0 1,721 Último mensaje 21 Agosto 2019, 15:03 pm
por EASoft
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines