• Author / Uploaded
• victor140188

• Categories
• Puntero (Programación de computadoras)
• Gestión de datos
• Lógica matemática
• Matemática aplicada
• Algoritmos y estructuras de datos

Citation preview

Cuestionario. Lic. En informática.

Unidad 5. Tema: grafos y arboles.

Materia: estructura de datos

Alumno: Estrada Mosso Víctor Daniel.

3er semestre.

Grupo: A.

Tlapa de comonfort gro. A 13 de septiembre de 2009

1

ÁRBOLES Un Árbol binario T se define como un conjunto finito de elementos, llamados nodos, de forma que: a) T es vacio (en cuyo caso se llama árbol nulo o árbol vacio) o b) T contiene un nodo distinguido R, llamado raíz de T, y los restantes nodos de T forman un par ordenado de árboles binarios disjuntos T1, T2. Si T contiene una raíz R, los dos árboles T 1, T2, se llaman, respectivamente subárboles izquierdo y derecho de la raíz R. si T1 no es vacio, entonces su raíz se llama sucesor derecho de R. Un árbol binario T se presenta frecuentemente en forma de diagrama. En particular, el diagrama de la figura 7-1 representa un árbol T como sigue. (i) T con 11 nodos. Representados por las letras de la A a la L. excluyendo la I. (ii) La raíz del árbol T es el nodo de la A, en la parte superior del diagrama. (iii) una línea hacia abajo y a la izquierda de N señala un sucesor derecho de N. observe que: B es un sucesor izquierdo y C un sucesor derecho del nodo A. El subárbol izquierdo de la raíz A consiste en los nodos B,D,E,F, y el subárbol derecho de A consiste en los nodos C,G,H,J,K y L.

B

D

A

E

C

F

G H J L

K

2

Cualquier nodo de N de un árbol binario T tiene 0,1 ó 2 sucesores. Los nodos A, B,C Y H tienen dos sucesores, los nodos R,J solo tienen un sucesor, y los nodos D,F,G,L y Y no tienen sucesores. Los nodos sin sucesor se llaman nodos terminales. Dos árboles binarios T y T se dice que son similares si tienen la misma estructura ó, en otras palabras, si tienen la misma forma. Los árboles se dice que son copias si son similares y tienen los mismos contenidos en sus correspondientes nodos.

Terminología Frecuentemente se usa una terminología de relaciones Familiares para describir las relaciones entre los nodos de un árbol T. En particular suponga que N es un nodo de T con un sucesor izquierdo S1 si un sucesor S2. Entonces N se llama el padre de S1, S2 analógicamente, S1 se llama el hijo de izquierdo de N y S2 el hijo derecho de N. es mas S1, S2 se dice que son hermanos. Cada nodo de N de un árbol binario T, excepto la raíz, tiene un único padre predecesor. I + -

. b

a

c

d

3

Arboles binarios completos Considere un árbol binario T. cada nodo de T puede tener como mucho dos hijos. De acuerdo con esto, se puede probar que le nivel r de T puede tener como mucho 2 r nodos. El árbol T se dice que es completo si todos sus niveles, excepto posiblemente el ultimo, tiene el máximo numero nodos posibles y si todos los nodos del último nivel están situados. Lo más posible a la izquierda. Así solo existe un árbol completo Tn con exactamente n nodos (por supuesto, ignoramos los contenidos de los nodos). Los nodos de los árboles completos T26 ha sido intencionalmente etiquetados con los enteros 1, 2,….., 26, de izquierda a derecha y de generación en generación. Con este etiquetado, se pueden determinar fácilmente los hijos o del padre de cada nodo k son, de un árbol completo Tn. Específicamente, los hijos izquierdo y derecho de un nodo k son, respectivamente, 2*k y 2*k +, y el padre de k es el nodo [k/2]. Por ejemplo, los hijos del nodo 9 son los nodos 18 y 19 y su padre es el nodo [9/2]=4. La profundidad d n del árbol completo Tn de n nodos viene dada por: D n= [log2 n+1]

Arboles binarios extendidos: arboles-2 Un árbol binario T se dice que es un árbol-2 o árbol binario extendido si cada nodo N tiene 0 o 2 hijos. En se caso, los nodos con dos hijos se denomina nodos internos y los nodos con 0 hijos se denominan nodos externos. A veces los nodos se distinguen en los diagramas mediante el uso de círculos para los nodos internos y de los cuadrados para los nodos externos. El termino viene de la siguiente operación. Considere un árbol binario T, como el de la figura 7-5 (a). Entonces T puede ser a un árbol-2 reemplazando cada subárbol vacía por un nuevo nodo, como se ve en la figura 7-5(b). un ejemplo importante de árbol-2 es el árbol T correspondiente a una expresión algebraica E que usa solo operaciones binarias.

4

(a)Árbol binario T (b)Árbol-2 extendido

Representación de árboles binarios en memoria Sea T un árbol binario. Esta sección discute dos formas de representar T en la memoria. La primera y más usual forma, llamada representación enlazada de T, es analógica a la forma en que se representan las listas enlazadas en memoria. La segunda forma, que usa un arrray simple, se llama representación secuencial de T. el principal requerimiento para cualquier representación de T es que se tenga acceso directo a la raíz de R de T y, dado cualquier nodo de N de T, se tenga acceso directo a los hijos de N.

Representación enlazada de árboles binarios Considere el árbol T. a menos que se especifique lo contrario, T se mantendrá en memoria en términos de una enlazada que usa tres arrays paralelos, INFO,IZQ y DER, y una variable puntero RAIZ tal como sigue en el primer lugar, cada nodo N de T corresponderá a una posición K, tal que: (1)INFO[K] contendrá los datos del nodo N. (2)IZQ[Z}contendrá la localización de hijo izquierdo del nodo N (3)DER[K]contendrá la localización del hijo derecho del nodo N

Más aun, RAIZ contendrá la posición de la raíz R de T. si algún subárbol está vacío, entonces el correspondiente puntero contendrá el valor nulo; si el árbol mismo T está vacío, entonces RAIZ contendrá el valor nulo.

5

INFO

RAIZ 5 DISP 8

1 2 3

K C G

4

IZQ 0 3 0

DER 0 6 0

14

5 6

A H

10 17

2 1

7

L

0

0

8 9 10 11 12 13 14 15 16 17 18 19 20

B F E

J D

9 4 18 19 0 12 15 16 11 7 0 20 0

13 0 0

0 0

FIG. 7-7

6

NOMBRE

NSS

SEXO

SALRIO

IZQ 0

DER

Hembra

22800

0

12

Varón

19000

0

0

Varón

27200

2 1

0

Hembra

14700

0

0

Hembra

16400

3 11

10

Varón

19000

6

4

Hembra

15500

0 113

0

1

RAIZ 14

DISP 8

2

Davis

3

Kellly

4 5

Green

6

Brown

7 8

Lewis

192387282 165643351 175562261 178521056 181589939

9

Cohen

10 11

Rubin

177444557 135466262

Evans

168568113

Varón

34200

0 5

0

Harris

208561654

Hembra

22800

9

7

12 13

14

FIG. 7-8

7

Representación secuencial de árboles binarios Suponga que T es un árbol binario que es completo a casi es completo. Entonces una forma eficiente de mantener T en memoria llamada representación secuencial de T. Esta representación usa únicamente un array lineal ÁRBOL de la forma siguiente. (a)la raíz R de T se guarda en ÁRBOL[1] (b)si un nodo N esta en el ÁRBOL[K], entonces su hijo izquierdo esta en ÁRBOL[2*k] y su hijo derecho en ÁRBOL[2*K+1].

ÁRBOL

Harris

Cohen

Brown

Lewis

Green

Kelly

Rubin

Davis

Evans

De nuevo, se usa NULO para indicar un subárbol vacio. En particular, ÁRBOL [1]=NULO indica que el árbol está vacío.

8

RECORRIDO DE ÁRBOLES BINARIOS Existen tres modos estándar de recorrer un árbol binario T de raíz R. estos tres algoritmos denominados Preorden, inorden y postorden, son así: Presorden:

(1) procesar la raíz R (2) Recorrer el subárbol izquierdo de R en preorden (3) Recorrer el subárbol derecho de R en preorden

Inorden (1) recorrer el subárbol izquierdo de R en inorden (2) procesar la raíz R (3) recorrer el subárbol derecho de R en inorden Postorden (1) recorrer el subárbol izquierdo de R en postorden (2) procesar la raíz R (3) recorrer el subárbol derecho de R en postorden Observe que cada algoritmo contiene los mismos tres pasos y que el subárbol izquierdo de R siempre se recorre antes que el subárbol derecho. La diferencia entre los algoritmos es el momento en que se procesa la raíz R. específicamente en e algoritmo , la raíz R se procesa antes de recorrer l0os árboles; en el algoritmo , la raíz R se procesa entre los dos recorridos de los subárboles; y en le algoritmo , la raíz se procesa tras recorrer los subárboles. Los tres algoritmos se denominan a veces, respectivamente, recorrido nodo-izquierdo-nododerecha (de ingles, LNR) y recorrido izquierdo-derecho-nodo (LRN, del ingles).

ÁRBOLES A

LT

C B

D

Rt

E

F

9

ALGORITMOS DE RECORRIDO USANDO PILAS Suponga un árbol binario T mantenido en memoria por una representación enlazada. ÁRBOL (INFO, IZQ, DER, RAIZ) Esta sección discute la implementación de los tres recorridos estándar de T, definidos recursivamente en la última sección, mediante procedimientos no recursivos que usan pilas. Recorrido reorden: El orden del recorrido preorden usa una variable PTR (puntero) que contendrá la posición del nodo N que se está examinando. Esto se en la figura 7-15, donde L(N) denota al hijo izquierdo del nodo N y R(N) denotado al hijo derecho. El algoritmo también usa un array pila, que contendrá las direcciones de los nodos que hayan de ser procesados. PTR N

L(N)

R(N)

FIG. 7-15 ALGORITMO: Inicialmente meter NULO en PILA y entonces PTR:=RAIZ. Entonces repetir los siguientes pasos hasta que PTR o, lo que es el mismo, mientras PTR≠NULO. Una presentación formal de nuestro algoritmo de recorrido pre orden será: ALGORITMO: PREORD (INFO,IZQ, DER, RAIZ) UN ÁRBOL BINARIO Testa en memoria, el algoritmo hace un recorrido preorden T, aplicando una operación PORCESO a cada uno de sus nodos. Se usa un array PILA para mantener temporalmente las direcciones de los nodos 1.- [inicialmente meter NULO en PILA e iniciar PTR]. Poner SUP:=1,PILA[1]:=NULO Y PTR:=RAIZ 2.- Repetir pasos 3 a 5 mientras PTR≠NULO 3.- Aplicar PROCESO a INFO[PRT}. 4.- [¿hijo derecho?] Si DER [PTR]≠NULO, entonces :[meterlo en PILA]. Poner SUP:=SUP+1 y PILA[SUP]:=DER[PTR] [Fin de condicional]. 5.- [¿Hijo izquierdo?] Si IZQ [PTR]≠NULO, entonces: Poner PTR:=PILA [SUP] y SUP:=SUP-1

10

Recorrido Inorden El algoritmo de corrido inorden también usa una variable puntero PTR, que contendrá la posición del nodo N que se está examinando, y un array PILA, que mantendrá las direcciones de los nodos que queden por procesa. De hecho, en este algoritmo, un nodo sólo se procesa cuando se saca de la PILA.

ALGORRIMO: INOR (INFO, IZQ,DER, RAIZ) Un árbol binario está en memoria. Este algoritmo hace un recorrido inorden de T, aplicando una operación PORCESO a cada uno de sus nodos. Se usa en array PILA para mantener temporalmente las direcciones de los nodos. 1.- [meter NULO en PILA e inicializar PTR] Hacer SUP:=1, PILA [1], PILA [1]:=NULO y PTR :=RAIZ 2.- Repetir mientras que PTR ≠NULO:[meter el camino izquierdo en PILA ]. (a) hacer SUP:=SUP+1 y PILA +1 y PILA [SUP]:=PTR [guardar nodo]. (b) hacer PTR:=PTR:=IZQ [PTR],[Actualizar PTR]. 3.- hacer PTR:=PILA y SUP:=SUP=:=SUP-1. [sacar nodo de PILA]. 4.- repetir pasos 5 a 7 mientras PTR ≠NULO:[vuelta atrás]. 5.- aplicar el PROCESO a INFO[PTR]. 6.- [¿hijo derecho?]. si DER [PTR]≠NULO entonces: (a) hacer PTR :=DER[PTR]. (b)ir al paso 2 [Fin de condicional]. 7.- hacer PTR:=PILA [SUP] Y SUP:=SUP-1. [sacar nodo]. [Fin del bucle del paso 4] 8.-salir.

Recorrido postorden. El algoritmo de recorrido postorden es mas complicado que los dos algoritmos anteriores, ya que aquí tenemos que salvar el nodo N en dos situaciones distintas, distinguimos entre los dos casos metiendo en PILA N o su negativo, - N. (en realidad, la posición de N es lo que se mete en PILA, de forma que –N tiene un objetivo obvio.) de nuevo se usa una variable PTR (puntero)que a de contener la posición del nodo N que se esté examinando. 11

7.6 NODOS CABECERA; ÁRBOLES ENHEBRADOS

Nodos con cabecera Suponga un árbol binario T dispuesto en memoria por representación enlazada. A veces se añade al principio de T un nodo extra, especial, llamada nodo cabecera. Cuando se usa este nodo extra, la variable puntero el árbol, que llamaremos CABEZA (en lugar de raíz), apuntara al nodo cabecera, el puntero izquierdo del nodo cabecera apuntara a la raíz de T. Hebras; enhebrado inorden Considere de nuevo la representación enlazada de un árbol binario T. aproximadamente la mitad de las entradas de los campo puntero IZQ y DER contendrá valores nulos. Este espacio se puede aprovechar más eficientemente reemplazados las entradas nulas por algún otro tipo de información. Específicamente, reemplazaremos ciertas entradas nulas con punteros especiales que apuntaran a nodos supriores de árbol. Estos punteros especiales se llaman hebras, y los árboles binarios con este tipo de punteros se llaman árboles enhebrados. Las hebras de un árbol enhebrado se deben distinguir de alguna forma de los punteros normales. Las hebras en los diagramas de un árbol enhebrado se indican normalmente con las líneas discontinuas. En la memoria de la computadora se pude usar un campo extra INDICADOR de un bit para distinguir las hebras de los punteros ordinarios, o, alternativamente, denotar las hebras por enteros negativos y los punteros normales por enteros positivos.

12

Cabecera

x

A B

X

C

D X

E

X

F

X

X G X

H

J

X

X

L

X

X K X

X

Fig. 7-18 ARBOLES BINARIOS DE BÚSQUEDA Esta sección discute una de las estructuras de datos mas importantes de la informática, el árbol binario de búsqueda. Esta estructura permite buscar y encontrar un elemento con una media de tiempo de ejecución ʄ(n)=0(log2n). También permite insertar y borrar elementos fácilmente. Esta estructura contrasta con las siguientes estructuras. (a) Array lineal ordenado. Aquí se puede buscar y encontrar un elemento con un tiempo de ejecución ʄ(n)=0(log2n), pero es costoso al insertar y borrar elementos. (b) lista enlazada. Aquí se puede insertar y borrar fácilmente, pero es costoso el buscar y encontrar un elemento, ya que se pude buscar una búsqueda secuencial.

13

Supongamos que T es un árbol binario. Entonces T se dice que es un árbol binario de búsqueda (o árbol binario ordenado) se cada N de T tiene la siguiente propiedad: el valor de N es mayor que cualquier valor del subárbol izquierdo de N y es menor que cualquier valor del subárbol derecho de N. (no es difícil ver que esta propiedad garantice que el recorrido inorden de T dará una lista ordenado de los elementos de T).

38 56 14

82

8

23 18

45 70

Fig. 7-12

Búsqueda e inserción en arboles binarios en búsqueda Supongamos que T es un árbol binario de búsqueda. Esta sección discute las operaciones básicas de búsqueda e inserción sobre T, de hecho, la búsqueda e inserción se darán por único algoritmo de búsqueda e inserción. La operación de borrado se trata en la siguiente sección. El recorrido de T es el mismo de un recorrido de binario. Supongamos un ITEM de información dado. El siguiente algoritmo encuentra la posición de ITEM en el árbol binario de búsqueda T o inserta ITEM como un nuevo nodo en su sitio apropiado en el árbol. (a) comparar ITEM con el nodo RAIZ N del árbol (i) si ITEMN proceder con el hijo derecho de N (b) repetir el paso (a) hasta que se dé una de las siguientes condiciones. (i) se encuentra un nodo N tal que ITEM=N en este caso se a Completado la búsqueda. (ii) se encuentra un subárbol vacio, lo que indica que la búsqueda ha Sido infructuosa, y se inserta ITEM en el subárbol vacio. En otras palabras, se procede hacia abajo desde la raíz R por el árbol T hasta que se encuentra ITEM en T o hasta insertar ITEM como un nodo terminal de T. 14

Ejemplo 7-14: (a) Considere el árbol binario de búsqueda T de la figura 7-21. Suponga que se da ITEM=20 simulando el algoritmo anterior, tendríamos los siguientes pasos. 1.- se compra ITEM=20 con la raíz, 38, del árbol T. como 2014, se procede con el hijo derecho de 14, que es 23. 3.- se compra ITEM=20 con 23. Como 2018 y 18 no tiene hijo derecho, se inserta 20 como hijo derecho de 18.

38 56 14

82

8

23

45

18

70

Fig. 7-22 ITEM=20 insertado

Complejidad del algoritmo de búsqueda Suponga que buscamos un elemento de información en un árbol de búsqueda binaria T. observe que el número de operaciones está limitado por la profundidad del árbol. Esto viene 15

del hecho de que bajamos por un único camino del árbol. Así, el tiempo de ejecución de la búsqueda será proporcional a la profundidad del árbol.

Aplicaciones de los arboles de búsqueda binaria. Considere un conjunto de N datos A1,A2,……AN. Suponga que queremos encontrar y borrar todos los duplicados del conjunto. Una forma directa de hacerlo es la siguiente. Algoritmo A: examinar los elementos desde A1 hasta AN (o sea, de izquierda a derecha). (a)para cada elemento Ak con A1,A2,….,AK -1, o sea, comparar AK con aquellos elementos que preceden a Ak (b)si Ak se en A1,A2,…., AK -1, entonces borrar Ak Tras a ver examinado todos los elementos, no habrá duplicados.

Ejemplo 7-16 Suponga que aplicamos A a la siguiente lista de 15 números: 14,10,17,12,10,11,20,12,18,25,20,,8,22,11,23. Observe que los primeros cuatro números (14,10, 17 y 12) no se borran sin embargo. A5= 10 se borra ya que A5=A2 A8= 12 se borra ya que A8=A4 A11= 20 se borra ya que A11=A7 A4= 11w se borra ya que A14=A6 Cuando el algoritmo A termina, quedaran los 11 números. 14,10,17,12,11,20,18,25,8,22,23. Que son todos distintos.

7.9 eliminación en un árbol de búsqueda binaria Suponga que T es un árbol de búsqueda binaria, y suponga un ITEM de información dado. Esta sección da un algoritmo que elimina ITEM del árbol T. El algoritmo de eliminación, para encontrar la posición del nodo N que contiene a ITEM, así como la posición del nodo padre p(N). la forma en que N es eliminado del árbol depende principalmente del número de hijos de N. existen tres casos. 16

Caso1.- N no tiene hijos. Entonces se elimina de T simplemente reemplazado la Posición de N en p(N) por el puntero nulo. Caso 2.- N tiene exactamente un hijo. Entonces N se elimina de T simplemente Reemplazado la posición de N en P(N) por la posición del hijo único de N. Caso 3.- N tiene dos sea S(N) el sucesor inorden de N. [el elector puede verificar que S(N) no tiene hijo izquierdo,] entonces N es eliminado de T primero eliminando S(N) de T (mediante los casos 1 ó 2) y luego reemplazando N en T por el nodo S(N). Observe que el tercer paso es mucho más complicado que los dos primeros, en los tres casos, el espacio de memoria del nodo N eliminando se devuelve a la lista DISP.

60 66 25 15

50 33 44

(a) el nodo 75 es eliminado.

INFO

IZQ

DER

RAIZ

1

33

0

9

3

2

25

8

10

3

60

2

4

4

66

0

0

DISP

5

6

7

6

0

7

5

8

15

0

0

9

44

0

0

10

50

1

0

17

(B) representación enlazada

Arboles en montón; ordenación por montón. Suponga que H es un árbol binario completo con N elementos. (al menos de que se indique lo contrario , asumiremos que H se tiene un memoria como un array lineal árbol mediante representación secuencial, no en representación enlazada). Se dice que H es u árbol en montón, montón máx. si cada nodo de N de H tiene la siguiente propiedad: el valor de N es mayor o igual que el valor de cualquier hijo de N. (un montón min se define analógicamente: el valor de N es menor o igual que el valor de cualquier hijo de N).

Ejemplo 7.19 Considere el árbol completo H de la figura 7-29(a). Observe que H es un árbol en montón. Esto significa, en particular, que el mayor elemento de H aparece en lo del montón, o sea, en la raíz del árbol. La figura 7-19 (b) muestra la presentación secuencial de H en el array ARBOL [1] es la raíz d3el árbol H, y los hijos de izquierdo y derecho de un nodo ARBOL [K] son, respectivamente, ARBOL [2K] y árbol [2K+1]. Esto significa en particular, que el padre de cualquier nodo de raíz árbol [J] es el nodo ARBOL [J÷2] (donde J÷2 significa división entera). Observe que los nodos de H del mismo nivel aparecen uno tras otro en el array ARBOL.

96

95 88

95 66

66

18

55

35

40

48

30

48

26

25

62

77

25

48

24 18

(a) montón 97 88 95 66 55 95 48 66 35 48 55 62 77 25 38 18 40 30 26 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 (b) Representación secuencial Fig. 7-29

Inserción en un árbol en montón Suponga que H es un montón con N elementos y suponga que se da un ITEM de información insertamos ITEM en el montón H tal y como sigue: (1) Primero se añade ITEM al final de H, de forma que H sigue siendo un árbol completo aunque no necesariamente un montón. (2) Entonces se subir a ITEM hasta su en H para que H sea finalmente un montón

La forma en que funciona este procedimiento se ilustra a continuación antes de presentarlo formalmente. Ejemplo 7-20 Considere el montón H de la figura 7-29. Suponga que queremos añadir ITEM=70 a H. primero ajuntamos 70 como el siguiente elemento del árbol completo, esto es, hacemos ARBOL [21]=70. Entonces 70 es el hijo derecho del ÁRBOL [10]=48. En la figura 7-30(a) esta dibujado el camino desde la raíz de H hasta 70. Ahora buscamos el sitio adecuado para 70 en el montón como sigue: (a) Comparamos 70 con su padre, 48. Como 70 es mayor que 48, intercambiamos 70 y 48; el camino ahora aparece como en la figura 7-30(b). (b) Comparamos 70 con su nuevo padre 55. Como 70 es mayor que 55, intercambiamos; el camino ahora aparece como en la figura 7-30(c). (c) Comparamos 70 con su nuevo padre, 88. Como 70 no excede a 88, ITEM=70 ha llegado a su lugar adecuado en H.

19

97

97

97

88

88

88 55

70

55

55

70 0

48

48 48

70

(a)

(b)

(c)

97

95 88

95 70

66

66

48

35

55

55

62

77

25

38

20

18

40

30

26 24

48 Fig. 7-30 ITEM=70 es insertado

LA DECLARACIÓN FORMAL DE PROCEDIMIENTO ES: Procedimiento 7.9: INSMONTON (ARBOL, N, ITEM) Árbol en montón H con N elementos está guardado en el array ARBOL, y se da un ITEM de información. Este procedimiento inserta ITEM como nuevo de H. PTR de la posición de ITEM a medida que sube por el árbol, y PAD indica la posición de padre de ITEM. 1. [Añadir el nuevo nodo a H e inicializar PTR]. Hacer N:=N+1 y PTR:=N. 2. [buscar la posición a insertar ITEM]. Repetir pasos 3 y 6 mientras PTRizqnodo),nuevo); else if(nuevo>(*rarbol)->info) insertanodonuevo(&((*rarbol)->dernodo),nuevo); } void preorden(ARBOL rarbol){ if(rarbol!=NULL){ printf(” %c “,rarbol->info); preorden(rarbol->izqnodo); preorden(rarbol->dernodo); } } void inorden(ARBOL rarbol){ if(rarbol!=NULL){ inorden(rarbol->izqnodo); printf(” %c “,rarbol->info); inorden(rarbol->dernodo); } } void postorden(ARBOL rarbol){ if(rarbol!=NULL){ postorden(rarbol->izqnodo); postorden(rarbol->dernodo); printf(” %c “,rarbol->info); } } void treefree(ARBOL rarbol){ if(rarbol!=NULL){ treefree(rarbol->izqnodo); treefree(rarbol->dernodo); free(rarbol); } } #include #include struct nodo 32

{ struct nodo *izq, *der; char *dato; }; int cont=0; struct nodo *crear(char s[30]) { struct nodo *p; p=(struct nodo *) malloc (sizeof(struct nodo)); p->izq=NULL; p->der=NULL; p->dato=s; return (p); } void insertar(struct nodo *raiz, char s[30]) { struct nodo *nuevo,*q,*p; nuevo=crear(s); q=NULL; p=raiz; while(p!=NULL && strcmp( p->dato,nuevo->dato)!=0) { q=p; if(strcmp(p->dato,nuevo->dato)izq; else // if (strcmp(p->dato,nuevo->dato)der; } if(strcmp(p->dato,nuevo->dato)!=0) if(strcmp(q->dato,nuevo->dato)>0) q->izq=nuevo; else q->der=nuevo; } cargar() { struct nodo *raiz=NULL; FILE *archivo; char caracter[30],espa, tem[30]; int b=0; 33

archivo = fopen("c:\prueba.txt","r"); if (archivo == NULL) { printf("\nEl archivo no existe \n\n"); getch(); exit(1); } else { printf("\nEl contenido del archivo de prueba es \n\n"); while (feof(archivo) == 0) { espa=getc(archivo); if (espa==' ') { printf("\n"); cont++; } else { printf("%c",espa); } b++; // getch(); //llenar arbol binario /*if (raiz==NULL) { raiz=crear(caracter); } else { insertar(raiz,caracter); }*/ // printf("%c",caracter); } printf("\nEL NUMERO DE PALABRAS ES: %d",cont); } 34

getch(); return 0; } void main() { //struct nodo *raiz=NULL; char opc; int dato,x,s; do { clrscr(); gotoxy(27,8);printf("1. Cargar Archivos"); gotoxy(27,10);printf("2. Contar palabras"); gotoxy(27,12);printf("3. Mostrar palabras"); gotoxy(27,20);printf("4. Salir"); gotoxy(27,22);printf("opcion: []\b\b"); opc=getche(); switch(opc) { case '1': clrscr(); cargar(); break; case '2': clrscr(); printf("EL NUMERO DE PALABRAS ES: %d",cont); getch(); break; case '3': clrscr(); // orden(raiz); getch(); break; case '4': break default: 35

clrscr(); gotoxy(31,10);printf("La opcion no existe"); gotoxy(24,12);printf("presione una tecla para continuar..."); getch(); break; } }while(opc!='4'); }

Otro código sobre árbol. #include #include #include #include #include #include struct nodoarbol{ struct nodoarbol *izqnodo; int info; struct nodoarbol *dernodo; }; typedef struct nodoarbol NODO; typedef NODO *ARBOL; void insertanodonuevo(ARBOL *,int); void inorden(ARBOL); void preorden(ARBOL); void postorden(ARBOL); void treefree(ARBOL); main(){ int i; char newnod,chain[200],elementos; clrscr(); ARBOL raiz=NULL; printf(“\nINTRODUSCA UNA CADENA DE CARACTERES\n”); gets(chain); elementos=strlen(chain); for(i=1;iinfo=nuevo; (*rarbol)->izqnodo=NULL; (*rarbol)->dernodo=NULL; } 36

else{printf(“\n memoria no disponible!!!\n”);} } else if(nuevoinfo) insertanodonuevo(&((*rarbol)->izqnodo),nuevo); else if(nuevo>(*rarbol)->info) insertanodonuevo(&((*rarbol)->dernodo),nuevo); } void preorden(ARBOL rarbol){ if(rarbol!=NULL){ printf(” %c “,rarbol->info); preorden(rarbol->izqnodo); preorden(rarbol->dernodo); } } void inorden(ARBOL rarbol){ if(rarbol!=NULL){ inorden(rarbol->izqnodo); printf(” %c “,rarbol->info); inorden(rarbol->dernodo); } } void postorden(ARBOL rarbol){ if(rarbol!=NULL){ postorden(rarbol->izqnodo); postorden(rarbol->dernodo); printf(” %c “,rarbol->info); } } void treefree(ARBOL rarbol){ if(rarbol!=NULL){ treefree(rarbol->izqnodo); treefree(rarbol->dernodo); free(rarbol); } }

Códigos de arboles 37

#include #include main() { int lista[4]; int i,res; int x, z; printf(“Inserte un numero para convertirlo en binario: “); scanf(“%d”, &x); while (x > 2) { res=0; if (x-(x/2)==(x/2)) { for (i=0;i