(6758&785$'('$726

$3817(6

02) Instituto Tecnolgico de la Paz. (s.f.). Estructura de datos Apuntes, pp. 1-58.

,1752'8&&,21

&RPR\DVDEHPRVODVFRPSXWDGRUDVIXHURQGLVHDGDVRLGHDGDVFRPRXQD

KHUUDPLHQWDPHGLDQWHODFXDOSRGHPRVUHDOL]DURSHUDFLRQHVGHFOFXOR

FRPSOLFDGDVHQXQODSVRGHPQLPRWLHPSR3HURODPD\RUDGHODV

DSOLFDFLRQHVGHHVWHIDQWVWLFRLQYHQWRGHOKRPEUHVRQODVGHDOPDFHQDPLHQWR

\DFFHVRGHJUDQGHVFDQWLGDGHVGHLQIRUPDFLQ

/DLQIRUPDFLQTXHVHSURFHVDHQODFRPSXWDGRUDHVXQFRQMXQWRGHGDWRVTXH

SXHGHQVHUVLPSOHVRHVWUXFWXUDGRV/RVGDWRVVLPSOHVVRQDTXHOORVTXH

RFXSDQVORXQORFDOLGDGGHPHPRULDPLHQWUDVTXHORVHVWUXFWXUDGRVVRQXQ

FRQMXQWRGHFDVLOODVGHPHPRULDDODVFXDOHVKDFHPRVUHIHUHQFLDPHGLDQWHXQ

LGHQWLILFDGRUQLFR

'HELGRDTXHSRUORJHQHUDOWHQHPRVTXHWUDWDUFRQFRQMXQWRVGHGDWRV\QR

FRQGDWRVVLPSOHVHQWHURVUHDOHVERROHDQRVHWFTXHSRUVVRORVQRQRV

GLFHQQDGDQLQRVVLUYHQGHPXFKRHVQHFHVDULRWUDWDUFRQHVWUXFWXUDVGH

GDWRVDGHFXDGDVDFDGDQHFHVLGDG

/DVHVWUXFWXUDVGHGDWRVVRQXQDFROHFFLQGHGDWRVFX\DRUJDQL]DFLQVH

FDUDFWHUL]DSRUODVIXQFLRQHVGHDFFHVRTXHVHXVDQSDUDDOPDFHQDU\DFFHGHU

DHOHPHQWRVLQGLYLGXDOHVGHGDWRV

8QDHVWUXFWXUDGHGDWRVVHFDUDFWHUL]DSRUORVLJXLHQWH

3XHGHQGHVFRPSRQHUVHHQORVHOHPHQWRVTXHODIRUPDQ

/DPDQHUDHQTXHVHFRORFDQORVHOHPHQWRVGHQWURGHODHVWUXFWXUDDIHFWDUOD

IRUPDHQTXHVHUHDOLFHQORVDFFHVRVDFDGDHOHPHQWR

/DFRORFDFLQGHORVHOHPHQWRV\ODPDQHUDHQTXHVHDFFHGHDHOORVSXHGH

VHUHQFDSVXODGD

81,'$',7,326'('$726

7,326'('$726

Definicin: El tipo de un dato es el conjunto de valores que puede tomar durante el programa. Si se le intenta dar un valor fuera del conjunto se producir un error.

La asignacin de tipos a los datos tiene dos objetivos principales: Por un lado, detectar errores en las operaciones Por el otro, determinar cmo ejecutar estas operaciones

Un lenguaje fuertemente tipeado es aquel en el que todos los datos deben de tener un tipo declarado explcitamente, y adems que existen ciertas restricciones en las expresiones en cuanto a los tipos de datos que en ellas intervienen. Una ventaja de los lenguajes fuertemente tipeados es que se gasta mucho menos esfuerzo en depurar (corregir) los programas gracias a la gran cantidad de errores que detecta el compilador.

&ODVLILFDFLRQHVHQORVWLSRVGHGDWRV

Existen muchas clasificaciones para los tipos de datos. Una de estas es la siguiente:

Dinmicos Estticos

o El tipo cadenao Estructuradoso Simples

Ordinales No-ordinales

Tipos estticos Casi todos los tipos de datos son estticos, la excepcin son los

punteros. Que un tipo de datos sea esttico quiere decir que el tamao que ocupa en memoria no puede variar durante la ejecucin del programa. Es decir, una vez declarada una variable de un tipo determinado, a sta se le asigna un trozo de memoria fijo, y este trozo no se podr aumentar ni disminur.Tipos dinmicos.

Dentro de esta categora entra slamente el tipo puntero. Este tipo te permite tener un mayor control sobre la gestin de memoria en tus programas. Con

ellos puedes manejar el tamao de tus variables en tiempo de ejecucin, o sea, cuando el programa se est ejecutando. Los punteros quizs sean el concepto ms complejo a la hora de aprender un lenguaje de programacin.Tipos simplesComo su nombre indica son los tipos bsicos. Son los ms sencillos y los ms fciles de aprender. Los tipos simples ms bsicos son: entero, lgico, carctery real. Y la mayora de los lenguajes de programacin los soportan, no como ocurre con los estructurados que pueden variar de un lenguaje a otro. Tipos estructuradosMientras que una variable de un tipo simple slo referencia a un elemento, los estructurados se refieren a colecciones de elementos. Las colecciones de elementos que aparecen al hablar de tipos estructurados son muy variadas: tenemos colecciones ordenadas que se representan mediante el tipo array, colecciones sin orden mediante el tipo conjunto, e incluso colecciones que contienen otros tipos, son los llamados registros.

Tipos ordinalesDentro de los tipos simples, los ordinales son los ms abundantes. De un tipo se dice que es ordinal porque el conjunto de valores que representa se puede contar, es decir, podemos establecer una relacin uno a uno entre sus elementos y el conjunto de los nmeros naturales. Dentro de los tipos simples ordinales, los ms importantes son:

El tipo entero. El tipo lgico. El tipo carcter.

Tipos no-ordinales

Simplificando, podramos reducir los tipos simples no-ordinales al tipo real. Este tipo nos sirve para declarar variables que pueden tomar valores dentro del conjunto de los nmeros reales. A diferencia de los tipos ordinales, los no-ordinales no se pueden contar. No se puede establecer una relacin uno a uno entre ellos y los nmero naturales. Dicho de otra forma, para que un conjunto se considere ordinal se tiene que poder calcular la posicin, el anterior elemento y el siguiente de un elemento cualquiera del conjunto.Cul es el sucesor de 5.12? Ser 5.13, o 5.120, o 5.121, ...

81,'$',,(6758&785$66(&8(1&,$/(6

,1752'8&&,216XSRQJDPRVTXHQRVHQIUHQWDPRVDXQSUREOHPDFRPRHVWH8QDHPSUHVD

TXHFXHQWDFRQHPSOHDGRVGHVHDHVWDEOHFHUXQDHVWDGVWLFDVREUHORV

VDODULRVGHVXVHPSOHDGRV\TXLHUHVDEHUFXDOHVHOVDODULRSURPHGLR\

WDPELQFXDQWRVGHVXVHPSOHDGRVJDQDHQWUH\

6LWRPDPRVODGHFLVLQGHWUDWDUHVWHWLSRGHSUREOHPDVFRQGDWRVVLPSOHV

SURQWRQRVSHUFDWDUDPRVGHOHQRUPHGHVSHUGLFLRGHWLHPSRDOPDFHQDPLHQWR\

YHORFLGDG(VSRUHVRTXHSDUDVLWXDFLRQHVGHHVWHWLSRODPHMRUVROXFLQVRQ

ORVGDWRVHVWUXFWXUDGRV

8QDUUHJORSXHGHGHILQLUVHFRPRXQJUXSRRXQDFROHFFLQILQLWDKRPRJQHD\

RUGHQDGDGHHOHPHQWRV/RVDUUHJORVSXHGHQVHUGHORVVLJXLHQWHVWLSRV

De una dimensin. De dos dimensiones. De tres o ms dimensiones.

$UUHJORV8QLGLPHQVLRQDOHV

8QDUUHJORXQLGLPHQVLRQDOHVXQWLSRGHGDWRVHVWUXFWXUDGRTXHHVWIRUPDGR

GHXQDFROHFFLQILQLWD\RUGHQDGDGHGDWRVGHOPLVPRWLSR(VODHVWUXFWXUD

QDWXUDOSDUDPRGHODUOLVWDVGHHOHPHQWRVLJXDOHV

(OWLSRGHDFFHVRDORVDUUHJORVXQLGLPHQVLRQDOHVHVHODFFHVRGLUHFWRHVGHFLU

SRGHPRVDFFHGHUDFXDOTXLHUHOHPHQWRGHODUUHJORVLQWHQHUTXHFRQVXOWDUD

HOHPHQWRVDQWHULRUHVRSRVWHULRUHVHVWRPHGLDQWHHOXVRGHXQQGLFHSDUD

FDGDHOHPHQWRGHODUUHJORTXHQRVGDVXSRVLFLQUHODWLYD

3DUDLPSOHPHQWDUDUUHJORVXQLGLPHQVLRQDOHVVHGHEHUHVHUYDUHVSDFLRHQ

PHPRULD\VHGHEHSURSRUFLRQDUODGLUHFFLQEDVHGHODUUHJORODFRWDVXSHULRU

\ODLQIHULRU

5(35(6(17$&,21(10(025,$

Los arreglos se representan en memoria de la forma siguiente: [[DUUD\>@RILQWHJHU

3DUDHVWDEOHFHUHOUDQJRGHODUUHJORQPHURWRWDOGHHOHPHQWRVTXH

FRPSRQHQHODUUHJORVHXWLOL]DODVLJXLHQWHIRUPXOD5$1*2 /V/Ldonde:OV /PLWHVXSHULRUGHODUUHJOR

OL /PLWHLQIHULRUGHODUUHJOR

3DUDFDOFXODUODGLUHFFLQGHPHPRULDGHXQHOHPHQWRGHQWURGHXQDUUHJORVH

XVDODVLJXLHQWHIRUPXOD$>L@ EDVH$>LOLZ@donde :$ ,GHQWLILFDGRUQLFRGHODUUHJOR

L ,QGLFHGHOHOHPHQWR

OL /PLWHLQIHULRU

Z 1PHURGHE\WHVWLSRFRPSRQHQWH

6LHODUUHJORHQHOFXDOHVWDPRVWUDEDMDQGRWLHQHXQQGLFHQXPHUDWLYR

XWLOL]DUHPRVODVVLJXLHQWHVIUPXODV5$1*2 RUGOVRUGOL

$>L@ EDVH$>RUGLRUGOLZ@

$UUHJORV%LGLPHQVLRQDOHV

(VWHWLSRGHDUUHJORVDOLJXDOTXHORVDQWHULRUHVHVXQWLSRGHGDWRHVWUXFWXUDGR

ILQLWRRUGHQDGR\KRPRJQHR(ODFFHVRDHOORVWDPELQHVHQIRUPDGLUHFWDSRU

PHGLRGHXQSDUGHQGLFHV

/RVDUUHJORVELGLPHQVLRQDOHVVHXVDQSDUDUHSUHVHQWDUGDWRVTXHSXHGHQYHUVH

FRPRXQDWDEODFRQILODV\FROXPQDV/DSULPHUDGLPHQVLQGHODUUHJOR

UHSUHVHQWDODVFROXPQDVFDGDHOHPHQWRFRQWLHQHXQYDORU\FDGDGLPHQVLQ

UHSUHVHQWDXQDUHODFLQ

/DUHSUHVHQWDFLQHQPHPRULDVHUHDOL]DGHGRVIRUPDVDOPDFHQDPLHQWRSRU

FROXPQDVRSRUUHQJORQHV

3DUDGHWHUPLQDUHOQPHURWRWDOGHHOHPHQWRVHQXQDUUHJORELGLPHQVLRQDO

XVDUHPRVODVVLJXLHQWHVIUPXODV 5$1*2'(5(1*/21(6_5 /V/L

5$1*2'(&2/801$65 /V/L

1R727$/'(&20321(17(6 55

5(35(6(17$&,21(10(025,$325&2/801$6

[DUUD\>@RILQWHJHU

3DUDFDOFXODUODGLUHFFLQGHPHPRULDGHXQHOHPHQWRVHXVDQODVLJXLHQWH

IRUPXOD $>LM@ EDVH$>MOL5LOLZ@

5(35(6(17$&,21(10(025,$3255(1*/21(6

[DUUD\>@RILQWHJHU

3DUDFDOFXODUODGLUHFFLQGHPHPRULDGHXQHOHPHQWRVHXVDQODVLJXLHQWH

IRUPXOD$>LM@ EDVH$>LOL5MOLZ@

GRQGH

L ,QGLFHGHOUHQJOQDFDOFXODU

M ,QGLFHGHODFROXPQDDFDOFXODU

OL /PLWHLQIHULRUGHUHQJORQHV

OL /PLWHLQIHULRUGHFROXPQDV

Z 1PHURGHE\WHVWLSRFRPSRQHQWH

$UUHJORV0XOWLGLPHQVLRQDOHV

(VWHWDPELQHVXQWLSRGHGDWRHVWUXFWXUDGRTXHHVWFRPSXHVWRSRUQ

GLPHQVLRQHV3DUDKDFHUUHIHUHQFLDDFDGDFRPSRQHQWHGHODUUHJORHV

QHFHVDULRXWLOL]DUQQGLFHVXQRSDUDFDGDGLPHQVLQ

3DUDGHWHUPLQDUHOQPHURGHHOHPHQWRVHQHVWHWLSRGHDUUHJORVVHXVDQODV

VLJXLHQWHVIUPXODV 5$1*25L OVLOLL

1R727$/'((/(0(1726 5555Q

GRQGH

L Q

Q 1RWRWDOGHGLPHQVLRQHV

3DUDGHWHUPLQDUODGLUHFFLQGHPHPRULDVHXVDODVLJXLHQWHIRUPXOD

/2&$>LLLLQ@ EDVH$>LOL555QLOL55LQOLQ5Q@Z

2SHUDFLRQHV&RQ$UUHJORV

/DVRSHUDFLRQHVHQDUUHJORVSXHGHQFODVLILFDUVHGHODVLJXLHQWHIRUPD

/HFWXUD

(VFULWXUD

$VLJQDFLQ

$FWXDOL]DFLQ

2UGHQDFLQ

%VTXHGD

D/(&785$

(VWHSURFHVRFRQVLVWHHQOHHUXQGDWRGHXQDUUHJOR\DVLJQDUXQYDORUDFDGD

XQRGHVXVFRPSRQHQWHV

/DOHFWXUDVHUHDOL]DGHODVLJXLHQWHPDQHUD SDUDLGHVGHKDVWD1KD]

[DUUHJOR>L@

E(6&5,785$

&RQVLVWHHQDVLJQDUOHXQYDORUDFDGDHOHPHQWRGHODUUHJOR

/DHVFULWXUDVHUHDOL]DGHODVLJXLHQWHPDQHUD SDUDLGHVGHKDVWD1KD]

DUUHJOR>L@[

F$6,*1$&,21

1RHVSRVLEOHDVLJQDUGLUHFWDPHQWHXQYDORUDWRGRHODUUHJORSRUORTXHVH

UHDOL]DGHODPDQHUDVLJXLHQWH SDUDLGHVGHKDVWD1KD]

DUUHJOR>L@DOJQBYDORU

G$&78$/,=$&,21

'HQWURGHHVWDRSHUDFLQVHHQFXHQWUDQODVRSHUDFLRQHVGHHOLPLQDULQVHUWDU\

PRGLILFDUGDWRV3DUDUHDOL]DUHVWHWLSRGHRSHUDFLRQHVVHGHEHWRPDUHQ

FXHQWDVLHODUUHJORHVWRQRRUGHQDGR

3DUDDUUHJORVRUGHQDGRVORVDOJRULWPRVGHLQVHUFLQERUUDGR\PRGLILFDFLQ

VRQORVVLJXLHQWHV

,QVHUWDU

6LLPHQVDMHDUUHJORFRQWUDULRFDVR(QDUUHJOR>L@YDORULLHQWRQFHV!

%RUUDU

6L1! HQWRQFHV

LQLFLR

L

HQFRQWUDGRIDOVR

PLHQWUDVL Q\HQFRQWUDGR IDOVR

LQLFLR

VLDUUHJOR>L@ YDORUBDBERUUDUHQWRQFHV

LQLFLR

HQFRQWUDGRYHUGDGHUR

11

SDUDNGHVGHLKDVWD1KD]

DUUHJOR>N@DUUHJOR>N@

ILQ

HQFDVRFRQWUDULR

LL

ILQ

ILQ

6LHQFRQWUDGR IDOVRHQWRQFHV

PHQVDMHYDORUQRHQFRQWUDGR

0RGLILFDU

6L1! HQWRQFHV

LQLFLR

L

HQFRQWUDGRIDOVR

PLHQWUDVL 1\HQFRQWUDGR IDOVHKD]

LQLFLR

6LDUUHJOR>L@ YDORUHQWRQFHV

DUUHJOR>L@YDORUBQXHYR

HQFRQWUDGRYHUGDGHUR

(QFDVRFRQWUDULR

LL

ILQ

ILQ

0DWU]3RFR'HQVD5HJXODU

8QDPDWU]SRFRGHQVDHVDTXHOODTXHHVWIRUPDGDSRUHOHPHQWRVTXHHQVX

PD\RUDVRQFHURV(VWHWLSRGHPDWULFHVVRQPDWULFHVFXDGUDGDVTXHVH

GLYLGHQHQORVVLJXLHQWHVWLSRV

0DWU]WULDQJXODUVXSHULRU

0DWU]WULDQJXODULQIHULRU

0DWU]WULGLDJRQDO

0$75,=75,$1*8/$5683(5,25

(QHVWHWLSRGHPDWU]ORVHOHPHQWRVLJXDOHVDFHURVHHQFXHQWUDQGHEDMRGHOD

GLDJRQDOSULQFLSDO(MHPSOR

3DUDHYLWDUHOGHVSHUGLFLRGHPHPRULDTXHVHRFDVLRQDUDDODOPDFHQDUXQD

PDWU]HQGRQGHODPD\RUDGHORVHOHPHQWRVVRQFHURVHVFRQYHQLHQWH

WUDVSDVDUDXQDUUHJORXQLGLPHQVLRQDOWRGRVORVHOHPHQWRVGLIHUHQWHVGHFHUR

(ODUUHJORFRQORVHOHPHQWRVGLVWLQWRVGHFHURGHODPDWU]DQWHULRUHVHO

VLJXLHQWH

8QDYH]TXHKDOODPRVYDFLDGRODPDWU]HVLQGLVSHQVDEOHFRQRFHUHOOXJDU

GHQWURGHODUUHJORXQLGLPHQVLRQDOHQHOFXDOTXHGDURQVLWXDGRVORVHOHPHQWRV\

HVWRVHORJUDFRQODVLJXLHQWHIRUPXOD

/2&$>LM@ EDVH$QLLLM

GRQGH

$ 0DWU]WULDQJXODUVXSHULRU

Q 1RWRWDOGHHOHPHQWRV

M UHQJORQHV

L FROXPQDV

0$75,=75,$1*8/$5,1)(5,25

(QHVWHWLSRGHPDWULFHVORVHOHPHQWRVLJXDOHVDFHURVHHQFXHQWUDQSRU

HQFLPDGHODGLDJRQDOSULQFLSDO(MHPSOR

8QDYH]TXHYDFLDPRVODPDWU]HQXQDUUHJORXQLGLPHQVLRQDOODIRUPXODSDUD

REWHQHUODVSRVLFLRQHVGHORVHOHPHQWRVHVODVLJXLHQWH

/2&$>LM@ EDVH$LLM

0$75,=75,',$*21$/

(QVWDORVHOHPHQWRVGLIHUHQWHVGHFHURVHHQFXHQWUDQHQODGLDJRQDO

SULQFLSDOHQODVGLDJRQDOHVSRUGHEDMRHQFLPDGHVWD(MHPSOR

LM@ EDVH$LM

2UGHQDFLRQHVHQ$UUHJORV

/DLPSRUWDQFLDGHPDQWHQHUQXHVWURVDUUHJORVRUGHQDGRVUDGLFDHQTXHHV

PXFKRPVUSLGRWHQHUDFFHVRDXQGDWRHQXQDUUHJORRUGHQDGRTXHHQXQR

GHVRUGHQDGR

([LVWHQPXFKRVDOJRULWPRVSDUDODRUGHQDFLQGHHOHPHQWRVHQDUUHJORV

HQVHJXLGDYHUHPRVDOJXQRVGHHOORV

D6HOHFFLQ'LUHFWD

Este mtodo consiste en seleccionar el elemento ms pequeo de nuestra lista para colocarlo al inicio y as excluirlo de la lista. 3DUDDKRUUDUHVSDFLRVLHPSUHTXHYD\DPRVDFRORFDUXQHOHPHQWRHQVX

SRVLFLQFRUUHFWDORLQWHUFDPELDUHPRVSRUDTXHOTXHODHVWRFXSDQGRHQHVH

PRPHQWR

(ODOJRULWPRGHVHOHFFLQGLUHFWDHVHOVLJXLHQWHL

PLHQWUDVL 1KD]

PLQL

ML

PLHQWUDVM 1KD]

VLDUUHJOR>M@>PLQ@HQWRQFHV

PLQM

MM

LQWHUFDPELDDUUHJOR>PLQ@DUUHJOR>L@

LL

E2UGHQDFLQSRU%XUEXMD

Es el mtodo de ordenacin ms utilizado por su fcil comprensin y programacin, pero es importante sealar que es el ms ineficiente de todos los mtodos . (VWHPWRGRFRQVLVWHHQOOHYDUORVHOHPHQWRVPHQRUHVDODL]TXLHUGDGHO

DUUHJORORVPD\RUHVDODGHUHFKDGHOPLVPR/DLGHDEVLFDGHODOJRULWPRHV

FRPSDUDUSDUHVGHHOHPHQWRVDG\DFHQWHVHLQWHUFDPELDUORVHQWUHVKDVWDTXH

WRGRVVHHQFXHQWUHQRUGHQDGRVL

PLHQWUDVL1KD]

M1

PLHQWUDVM!LKD]

VLDUUHJOR>M@DUUHJOR>M@HQWRQFHV

LQWHUFDPELDDUUHJOR>M@DUUHJOR>M@

MM

LL

F2UGHQDFLQSRU0H]FOD

Este algoritmo consiste en partir el arreglo por la mitad, ordenar la mitad izquierda, ordenar la mitad derecha y mezclar las dos mitades ordenadas en un array ordenado. Este ltimo paso consiste en ir comparando pares sucesivos de elementos (uno de cada mitad) y poniendo el valor ms pequeo en el siguiente hueco.SURFHGLPLHQWRPH]FODUGDWL]TSL]TXGHUSGHUX

LQLFLR

L]TDL]TS

GHUDGHUS

LQGL]TS

PLHQWUDVL]TD L]TX\GHUD GHUXKD]

VLDUUHJOR>L]TD@GDW>GHUD@HQWRQFHV

WHPSRUDO>LQG@DUUHJOR>L]TD@

L]TDL]TD

HQFDVRFRQWUDULR

WHPSRUDO>LQG@DUUHJOR>GHUD@

GHUDGHUD

LQGLQG

PLHQWUDVL]TD L]TXKD]

WHPSRUDO>LQG@DUUHJOR>L]TD@

L]TDL]TD

LQGLQG

PLHQWUDVGHUD GHUXKD]

WHPSRUDO>LQG@ GDW>GHUD@

GHUDGHUD

LQGLQG

SDUDLQGL]TSKDVWDGHUXKD]

DUUHJOR>LQG@WHPSRUDO>LQG@

ILQ

%VTXHGDVHQ$UUHJORV

8QDEVTXHGDHVHOSURFHVRPHGLDQWHHOFXDOSRGHPRVORFDOL]DUXQHOHPHQWR

FRQXQYDORUHVSHFLILFRGHQWURGHXQFRQMXQWRGHGDWRV7HUPLQDPRVFRQ[LWR

ODEVTXHGDFXDQGRHOHOHPHQWRHVHQFRQWUDGR

$FRQWLQXDFLQYHUHPRVDOJXQRVGHORVDOJRULWPRVGHEVTXHGDTXHH[LVWHQ

D%VTXHGD6HFXHQFLDO

$HVWHPWRGRWDPELHQVHOHFRQRFHFRPREVTXHGDOLQHDO\FRQVLVWHHQ

HPSH]DUDOLQLFLRGHOFRQMXQWRGHHOHPHQWRVHLUDWUDYH]GHHOORVKDVWD

HQFRQWUDUHOHOHPHQWRLQGLFDGRKDVWDOOHJDUDOILQDOGHDUUHJOR

(VWHHVHOPWRGRGHEVTXHGDPVOHQWRSHURVLQXHVWURDUUHJORVHHQFXHQWUD

FRPSOHWDPHQWHGHVRUGHQDGRHVHOQLFRTXHQRVSRGUD\XGDUDHQFRQWUDUHO

GDWRTXHEXVFDPRV

LQG

HQFRQWUDGRIDOVR

PLHQWUDVQRHQFRQWUDGR\LQG1KD]

VLDUUHJOR>LQG@ YDORUBEXVFDGRHQWRQFHV

HQFRQWUDGRYHUGDGHUR

HQFDVRFRQWUDULR

LQGLQG

E%VTXHGD%LQDULD

/DVFRQGLFLRQHVTXHGHEHFXPSOLUHODUUHJORSDUDSRGHUXVDUEVTXHGDELQDULD

VRQTXHHODUUHJORHVWHRUGHQDGR\TXHVHFRQR]FDHOQXPHURGHHOHPHQWRV

(VWHPWRGRFRQVLVWHHQORVLJXLHQWHFRPSDUDUHOHOHPHQWREXVFDGRFRQHO

HOHPHQWRVLWXDGRHQODPLWDGGHODUUHJORVLWHQHPRVVXHUWH\ORVGRVYDORUHV

FRLQFLGHQHQHVHPRPHQWRODEVTXHGDWHUPLQD3HURFRPRH[LVWHXQDOWR

SRUFHQWDMHGHTXHHVWRQRRFXUUDUHSHWLUHPRVORVSDVRVDQWHULRUHVHQODPLWDG

LQIHULRUGHODUUHJORVLHOHOHPHQWRTXHEXVFDPRVUHVXOWRPHQRUTXHHOGHOD

PLWDGGHODUUHJORRHQODPLWDGVXSHULRUVLHOHOHPHQWREXVFDGRIXHPD\RU

/DEVTXHGDWHUPLQDFXDQGRHQFRQWUDPRVHOHOHPHQWRRFXDQGRHOWDPDRGHO

DUUHJORDH[DPLQDUVHDFHUR

HQFRQWUDGRIDOVR

SULPHUR

XOWLPR1

PLHQWUDVSULPHUR XOWLPR\QRHQFRQWUDGRKD]

PLWDGSULPHURXOWLPR

VLDUUHJOR>PLWDG@ YDORUBEXVFDGRHQWRQFHV

HQFQWUDGRYHUGDGHUR

HQFDVRFRQWUDULR

VLDUUHJOR>PLWDG@!YDORUBEXVFDGRHQWRQFHV

XOWLPRPLWDG

HQFDVRFRQWUDULR

SULPHURPLWDG

F%VTXHGDSRU+DVK

/DLGHDSULQFLSDOGHHVWHPWRGRFRQVLVWHHQDSOLFDUXQDIXQFLQTXHWUDGXFHHO

YDORUGHOHOHPHQWREXVFDGRHQXQUDQJRGHGLUHFFLRQHVUHODWLYDV8QD

GHVYHQWDMDLPSRUWDQWHGHHVWHPWRGRHVTXHSXHGHRFDVLRQDUFROLVLRQHV

IXQFLRQKDVKYDORUBEXVFDGR

LQLFLR

KDVKYDORUBEXVFDGRPRGQXPHURBSULPR

ILQ

LQLFLRKDVKYDORU

LOLQLFLR

HQFRQWUDGRIDOVR

UHSLWH

VLDUUHJOR>LO@ YDORUHQWRQFHV

HQFRQWUDGRYHUGDGHUR

HQFDVRFRQWUDULR

LOLOPRG1

KDVWDHQFRQWUDGRRLO LQLFLR

&2/$6

8QDFRODHVXQDHVWUXFWXUDGHDOPDFHQDPLHQWRGRQGHODSRGHPRVFRQVLGHUDU

FRPRXQDOLVWDGHHOHPHQWRVHQODTXHVWRVYDQDVHULQVHUWDGRVSRUXQ

H[WUHPR\VHUQH[WUDGRVSRURWUR

/DVFRODVVRQHVWUXFWXUDVGHWLSR),)2ILUVWLQILUVWRXW\DTXHHOSULPHU

HOHPHQWRHQHQWUDUDODFRODVHUHOSULPHURHQVDOLUGHHOOD

([LVWHQPXFKVLPRVHMHPSORVGHFRODVHQODYLGDUHDOFRPRSRUHMHPSOR

SHUVRQDVHVSHUDQGRHQXQWHOIRQRSEOLFRQLRVHVSHUDQGRSDUDVXELUDXQ

MXHJRPHFQLFRHVWXGLDQWHVHVSHUDQGRSDUDVXELUDXQFDPLQHVFRODUHWF

5HSUHVHQWDFLQHQ0HPRULD

3RGHPRVUHSUHVHQWDUDODVFRODVGHGRVIRUPDV

&RPRDUUHJORV

&RPROLVWDVRUGHQDGDV

(QHVWDXQLGDGWUDWDUHPRVDODVFRODVFRPRDUUHJORVGHHOHPHQWRVHQGRQGH

GHEHPRVGHILQLUHOWDPDRGHODFROD\GRVDSXQWDGRUHVXQRSDUDDFFHVDUHO

SULPHUHOHPHQWRGHODOLVWD\RWURTXHJXDUGHHOOWLPR(QORVXFHVLYRDO

DSXQWDGRUGHOSULPHUHOHPHQWROROODPDUHPRV)DOGHHOOWLPRHOHPHQWR$\

0$;,02SDUDGHILQLUHOQPHURP[LPRGHHOHPHQWRVHQODFROD

&ROD/LQHDO

/DFRODOLQHDOHVXQWLSRGHDOPDFHQDPLHQWRFUHDGRSRUHOXVXDULRTXHWUDEDMD

EDMRODWFQLFD),)2SULPHURHQHQWUDUSULPHURHQVDOLU/DVFRODVOLQHDOHVVH

UHSUHVHQWDQJUILFDPHQWHGHODVLJXLHQWHPDQHUD

/DVRSHUDFLRQHVTXHSRGHPRVUHDOL]DUHQXQDFRODVRQODVGHLQLFLDOL]DFLQ

LQVHUFLQ\H[WUDFFLQ/RVDOJRULWPRVSDUDOOHYDUDFDERGLFKDVRSHUDFLRQHVVH

HVSHFLILFDQPVDGHODQWH

/DVFRQGLFLRQHVDFRQVLGHUDUHQHOWUDWDPLHQWRGHFRODVOLQHDOHVVRQODV

VLJXLHQWHV

2YHUIORZFRODOOHQDFXDQGRVHUHDOLFHXQDLQVHUFLQ

8QGHUIORZFRODYDFDFXDQGRVHUHTXLHUDGHXQDH[WUDFFLQHQODFROD

9DFR

$/*25,702'(,1,&,$/,=$&,1

)

$

$/*25,7023$5$,16(57$5

6L$ P[LPRHQWRQFHV

PHQVDMHRYHUIORZ

HQFDVRFRQWUDULR

$$

FROD>$@YDORU

$/*25,7023$5$(;75$(5

6L$OW)HQWRQFHV

PHQVDMHXQGHUIORZ

HQFDVRFRQWUDULR

))

[FROD>)@

&ROD&LUFXODU

/DVFRODVOLQHDOHVWLHQHQXQJUDYHSUREOHPDFRPRODVH[WUDFFLRQHVVOR

SXHGHQUHDOL]DUVHSRUXQH[WUHPRSXHGHOOHJDUXQPRPHQWRHQTXHHO

DSXQWDGRU$VHDLJXDODOP[LPRQPHURGHHOHPHQWRVHQODFRODVLHQGRTXH

DOIUHQWHGHODPLVPDH[LVWDQOXJDUHVYDFRV\DOLQVHUWDUXQQXHYRHOHPHQWR

QRVPDQGDUXQHUURUGHRYHUIORZFRODOOHQD

3DUDVROXFLRQDUHOSUREOHPDGHGHVSHUGLFLRGHPHPRULDVHLPSOHPHQWDURQODV

FRODVFLUFXODUHVHQODVFXDOHVH[LVWHXQDSXQWDGRUGHVGHHOOWLPRHOHPHQWRDO

SULPHURGHODFROD

/DUHSUHVHQWDFLQJUILFDGHHVWDHVWUXFWXUDHVODVLJXLHQWH

/DFRQGLFLQGHYDFRHQHVWHWLSRGHFRODHVTXHHODSXQWDGRU)VHDLJXDOD

FHUR

/DVFRQGLFLRQHVTXHGHEHPRVWHQHUSUHVHQWHVDOWUDEDMDUFRQHVWHWLSRGH

HVWUXFWXUDVRQODVVLJXLHQWHV

2YHUIORZFXDQGRVHUHDOLFHXQDLQVHUFLQ

8QGHUIORZFXDQGRVHUHTXLHUDGHXQDH[WUDFFLQHQODFROD

9DFLR

$/*25,702'(,1,&,$/,=$&,1

)

$

$/*25,7023$5$,16(57$5

6L) $) \$ P[LPRHQWRQFHV

PHQVDMHRYHUIORZ

HQFDVRFRQWUDULR

LQLFLR

VL$ P[LPRHQWRQFHV

$

FROD>$@YDORU

HQFDVRFRQWUDULR

$$

FROD>$@YDORU

VL) HQWRQFHV

)

ILQ

$/*25,7023$5$(;75$(5

6L) HQWRQFHV

PHQVDMHXQGHUIORZ

HQFDVRFRQWUDULR

[FROD>)@

VL) $HQWRQFHV

)

$

HQFDVRFRQWUDULR

VL) P[LPRHQWRQFHV

)HQFDVRFRQWUDULR))

'REOH&ROD

(VWDHVWUXFWXUDHVXQDFRODELGLPHQVLRQDOHQTXHODVLQVHUFLRQHV\

HOLPLQDFLRQHVVHSXHGHQUHDOL]DUHQFXDOTXLHUDGHORVGRVH[WUHPRVGHOD

ELFROD*UILFDPHQWHUHSUHVHQWDPRVXQDELFRODGHODVLJXLHQWHPDQHUD

([LVWHQGRVYDULDQWHVGHODGREOHFROD

'REOHFRODGHHQWUDGDUHVWULQJLGD

'REOHFRODGHVDOLGDUHVWULQJLGD

/DSULPHUYDULDQWHVORDFHSWDLQVHUFLRQHVDOILQDOGHODFROD\ODVHJXQGD

DFHSWDHOLPLQDFLRQHVVORDOIUHQWHGHODFROD

$/*25,7026'((175$'$5(675,1*,'$

$OJRULWPRGH,QLFLDOL]DFLQ

)

$

$OJRULWPRSDUD,QVHUWDU

6L$ P[LPRHQWRQFHV

PHQVDMHRYHUIORZ

HQFDVRFRQWUDULR

$$

FROD>$@YDORU

$OJRULWPRSDUD([WUDHU

6L)JW$HQWRQFHV

PHQVDMHXQGHUIORZ

HQFDVRFRQWUDULR

PHQVDMHIUHQWHDWUV

VLIUHQWHHQWRQFHV

[FROD>)@

))

HQFDVRFRQWUDULR

[FROD>$@

$$

$/*25,7026'(6$/,'$5(675,1*,'$

$OJRULWPRGH,QLFLDOL]DFLQ

)

$

$OJRULWPRSDUD,QVHUWDU

6L)JW$HQWRQFHV

PHQVDMHRYHUIORZ

HQFDVRFRQWUDULR

PHQVDMH)UHQWH$WUV

VL)UHQWHHQWRQFHV

FROD>)@YDORU

HQFDVRFRQWUDULR

$$

FROD>$@YDORU

$OJRULWPRSDUD([WUDHU

6L) HQWRQFHV

PHQVDMHXQGHUIORZ

HQFDVRFRQWUDULR

[FROD>)@

))

&RODGH3ULRULGDGHV

(VWDHVWUXFWXUDHVXQFRQMXQWRGHHOHPHQWRVGRQGHDFDGDXQRGHHOORVVHOHV

DVLJQDXQDSULRULGDG\ODIRUPDHQTXHVRQSURFHVDGRVHVODVLJXLHQWH

8QHOHPHQWRGHPD\RUSULRULGDGHVSURFHVDGRDOSULQFLSLR

'RVHOHPHQWRVFRQODPLVPDSULRULGDGVRQSURFHVDGRVGHDFXHUGRDO

RUGHQHQTXHIXHURQLQVHUWDGRVHQODFROD

$OJRULWPRSDUD,QVHUWDU

[

ILQDOYHUGDGHUR

SDUDLGHVGHKDVWDQKD]

6LFROD>L@JWSULRULGDGHQWRQFHV

[L

ILQDOIDOVR

VDOLU

VLILQDOHQWRQFHV

[Q

SDUDLGHVGHQKDVWD[

FROD>L@SULRULGDG

QQ

$OJRULWPRSDUD([WUDHU

6LFROD>@ HQWRQFHV

PHQVDMHRYHUIORZ

HQFDVRFRQWUDULR

SURFHVDUFROD>@

SDUDLGHVGHKDVWDQKD]

FROD>L@FROD>@

QQ

2SHUDFLRQHVHQ&RODV

/DVRSHUDFLRQHVTXHQRVRWURVSRGHPRVUHDOL]DUVREUHXQDFRODVRQODV

VLJXLHQWHV

,QVHUFLQ

([WUDFFLQ

/DVLQVHUFLRQHVHQODFRODVHOOHYDUQDFDERSRUDWUVGHODFRODPLHQWUDVTXH

ODVHOLPLQDFLRQHVVHUHDOL]DUQSRUHOIUHQWHGHODFRODKD\TXHUHFRUGDUTXHHO

SULPHURHQHQWUDUHVHOSULPHURHQVDOLU

3,/$6

/DVSLODVVRQRWURWLSRGHHVWUXFWXUDGHGDWRVOLQHDOHVODVFXDOHVSUHVHQWDQ

UHVWULFFLRQHVHQFXDQWRDODSRVLFLQHQODFXDOSXHGHQUHDOL]DUVHODV

LQVHUFLRQHV\ODVH[WUDFFLRQHVGHHOHPHQWRV

8QDSLODHVXQDOLVWDGHHOHPHQWRVHQODTXHVHSXHGHQLQVHUWDU\HOLPLQDU

HOHPHQWRVVORSRUXQRGHORVH[WUHPRV&RPRFRQVHFXHQFLDORVHOHPHQWRV

GHXQDSLODVHUQHOLPLQDGRVHQRUGHQLQYHUVRDOTXHVHLQVHUWDURQ(VGHFLUHO

OWLPRHOHPHQWRTXHVHPHWLDODSLODVHUHOSULPHURHQVDOLUGHHOOD

(QODYLGDFRWLGLDQDH[LVWHQPXFKRVHMHPSORVGHSLODVXQDSLODGHSODWRVHQ

XQDDODFHQDXQDSLODGHODWDVHQXQVXSHUPHUFDGRXQDSLODGHSDSHOHVVREUH

XQHVFULWRULRHWF

'HELGRDORUGHQHQTXHVHLQVHUWDQ\HOLPLQDQORVHOHPHQWRVHQXQDSLOD

WDPELQVHOHFRQRFHFRPRHVWUXFWXUD/,)2/DVW,Q)LUVW2XWOWLPRHQHQWUDU

SULPHURHQVDOLU

5HSUHVHQWDFLQHQ0HPRULD

/DVSLODVQRVRQHVWUXFWXUDVGHGDWRVIXQGDPHQWDOHVHVGHFLUQRHVWQ

GHILQLGDVFRPRWDOHVHQORVOHQJXDMHVGHSURJUDPDFLQ/DVSLODVSXHGHQ

UHSUHVHQWDUVHPHGLDQWHHOXVRGH

$UUHJORV

/LVWDVHQOD]DGDV

1RVRWURVDKRUDXVDUHPRVORVDUUHJORV3RUORWDQWRGHEHPRVGHILQLUHOWDPDR

P[LPRGHODSLODDGHPVGHXQDSXQWDGRUDOOWLPRHOHPHQWRLQVHUWDGRHQOD

SLODHOFXDOGHQRPLQDUHPRV63/DUHSUHVHQWDFLQJUILFDGHXQDSLODHVOD

VLJXLHQWH

&RPRXWLOL]DPRVDUUHJORVSDUDLPSOHPHQWDUSLODVWHQHPRVODOLPLWDQWHGH

HVSDFLRGHPHPRULDUHVHUYDGD8QDYH]HVWDEOHFLGRXQP[LPRGHFDSDFLGDG

SDUDODSLOD\DQRHVSRVLEOHLQVHUWDUPVHOHPHQWRV

8QDSRVLEOHVROXFLQDHVWHSUREOHPDHVHOXVRGHHVSDFLRVFRPSDUWLGRVGH

PHPRULD6XSRQJDVHTXHVHQHFHVLWDQGRVSLODVFDGDXQDFRQXQWDPDR

P[LPRGHQHOHPHQWRV(QHVWHFDVRVHGHILQLUXQVRORDUUHJORGHQ

HOHPHQWRVHQOXJDUTXHGRVDUUHJORVGHQHOHPHQWRV

(QHVWHFDVRXWLOL]DUHPRVGRVDSXQWDGRUHV63SDUDDSXQWDUDOOWLPR

HOHPHQWRLQVHUWDGRHQODSLOD\63SDUDDSXQWDUDOOWLPRHOHPHQWRLQVHUWDGR

HQODSLOD&DGDXQDGHODVSLODVLQVHUWDUVXVHOHPHQWRVSRUORVH[WUHPRV

RSXHVWRVHVGHFLUODSLODLQLFLDUDSDUWLUGHODORFDOLGDGGHODUUHJOR\ODSLOD

LQLFLDUHQODORFDOLGDGQ'HHVWHPRGRVLODSLODQHFHVLWDPVGHQ

HVSDFLRVKD\TXHUHFRUGDUTXHDFDGDSLODVHOHDVLJQDURQQORFDOLGDGHV\OD

SLODQRWLHQHRFXSDGRVVXVQOXJDUHVHQWRQFHVVHSRGUQVHJXLULQVHUWDQGR

HOHPHQWRVHQODSLODVLQFDHUHQXQHUURUGHGHVERUGDPLHQWR

1RWDFLQ,QILMD3RVWILMD\3UHILMD

/DVSLODVVRQHVWUXFWXUDVGHGDWRVPX\XVDGDVSDUDODVROXFLQGHGLYHUVRV

WLSRVGHSUREOHPDV3HURWDOYH]HOSULQFLSDOXVRGHHVWDVHVWUXFWXUDVHVHO

WUDWDPLHQWRGHH[SUHVLRQHVPDWHPWLFDV

$/*25,7023$5$&219(57,5(;35(6,21(6,1),-$6(13267),-$6

531

1. Incrementar la pila 2. Inicializar el conjunto de operaciones3. Mientras no ocurra error y no sea fin de la expresin infija haz

o Si el carcter es:1. PARENTESIS IZQUIERDO. Colocarlo en la pila 2. PARENTESIS DERECHO. Extraer y desplegar los valores hasta

encontrar parntesis izquierdo. Pero NO desplegarlo.3. UN OPERADOR.

Si la pila esta vaca o el carcter tiene ms alta prioridad que el elemento del tope de la pila insertar el carcter en la pila.

En caso contrario extraer y desplegar el elemento del tope de la pila y repetir la comparacin con el nuevo tope.

4. OPERANDO. Desplegarlo. 4. Al final de la expresin extraer y desplegar los elementos de la pila hasta que se

vace.

$/*25,7023$5$(9$/8$581$(;35(6,21531

1. Incrementar la pila 2. Repetir

o Tomar un caracter. o Si el caracter es un operando colocarlo en la pila.o Si el caracter es un operador entonces tomar los dos valores del tope de

la pila, aplicar el operador y colocar el resultado en el nuevo tope de la pila. (Se produce un error en caso de no tener los 2 valores)

3. Hasta encontrar el fin de la expresin RPN.

5HFXUVLQ

3RGHPRVGHILQLUODUHFXUVLYLGDGFRPRXQSURFHVRTXHVHGHILQHHQWUPLQRVGH

VPLVPR

(OFRQFHSWRGHUHFXUVLQHVGLIFLOGHSUHFLVDUSHURH[LVWHQHMHPSORVGHODYLGD

FRWLGLDQDTXHQRVSXHGHQVHUYLUSDUDGDUQRVXQDPHMRULGHDDFHUFDGHORTXH

HVUHFXUVLYLGDG8QHMHPSORGHHVWRHVFXDQGRVHWRPDXQDIRWRJUDIDGHXQD

IRWRJUDIDRFXDQGRHQXQSURJUDPDGHWHOHYLVLQXQSHULRGLVWDWUDQVILHUHHO

FRQWURODRWURSHULRGLVWDTXHVHHQFXHQWUDHQRWUDFLXGDG\HVWHDVXYH]OH

WUDQVILHUHHOFRQWURODRWUR

&DVRVWSLFRVGHHVWUXFWXUDVGHGDWRVGHILQLGDVGHPDQHUDUHFXUVLYDVRQORV

UEROHVELQDULRV\ODVOLVWDVHQOD]DGDV

/DUHFXUVLQVHSXHGHGDUGHGRVIRUPDV

DIRECTA. Este tipo de recursin se da cuando un subprograma se llama directamente a s mismo.

INDIRECTA Sucede cuando un subprograma llama a un segundo subprograma, y este a su vez llama al primero, es decir el subproceso A llama al B, y el B invoca al subproceso A.

,PSOHPHQWDU5HFXUVLQ8VDQGR3LODV

2WUDGHODVDSOLFDFLRQHVHQODVTXHSRGHPRVXWLOL]DUODVSLODVHVHQOD

LPSOHPHQWDFLQGHODUHFXUVLYLGDG$FRQWLQXDFLQVHPRVWUDUQDOJXQRV

HMHPSORV_

_1

)DFWRULDO

_1Q1JW

_

VS

PLHQWUDVQ!KD]

SXVKSLODQ

QQ

PLHQWUDVVS!KD]

IDFWRULDOIDFWRULDOSRSSLOD

_

_VLDE

4

_4DEEVLD E

_

VS

4

OHHDOHHE

PLHQWUDVD! EKD]

SXVKSLOD

DDE

PLHQWUDVVS!KD]

44SRSSLOD

2SHUDFLRQHVHQ3LODV

/DVSULQFLSDOHVRSHUDFLRQHVTXHSRGHPRVUHDOL]DUHQXQDSLODVRQ

Insertar un elemento (push). Eliminar un elemento (pop).

/RVDOJRULWPRVSDUDUHDOL]DUFDGDXQDGHHVWDVRSHUDFLRQHVVHPXHVWUDQD

FRQWLQXDFLQ/DYDULDEOHP[LPRSDUDKDFHUUHIHUHQFLDDOP[LPRQPHURGH

HOHPHQWRVHQODSLOD

,QVHUFLQ3XVK

VLVS P[LPRHQWRQFHV

PHQVDMHRYHUIORZ

HQFDVRFRQWUDULR

VSVS

SLOD>VS@YDORU

(OLPLQDFLQ3RS

VLVS HQWRQFHV

PHQVDMHXQGHUIORZ

HQFDVRFRQWUDULR

[SLOD>VS@

VSVS

81,'$',,,/,67$6(1/$=$'$6

8QDOLVWDHQOD]DGDRHQFDGHQDGDHVXQDFROHFFLQGHHOHPHQWRVQRGRVHQ

GRQGHFDGDXQRFRQWLHQHGDWRV\XQHQODFHROLJD

8QQQRGRHVXQDVHFXHQFLDGHFDUDFWHUHVHQPHPRULDGLYLGLGDHQFDPSRVGH

FXDOTXLHUWLSR8QQRGRVLHPSUHFRQWLHQHODGLUHFFLQGHPHPRULDGHOVLJXLHQWH

QRGRGHLQIRUPDFLQVLHVWHH[LVWH

8QDSXQWDGRUHVODGLUHFFLQGHPHPRULDGHXQQRGR

/DILJXUDVLJXLHQWHPXHVWUDODHVWUXFWXUDGHXQQRGR

(OFDPSROLJDTXHHVGHWLSRSXQWHURHVHOTXHVHXVDSDUDHVWDEOHFHUODOLJD

FRQHOVLJXLHQWHQRGRGHODOLVWD6LHOQRGRIXHUDHOOWLPRHVWHFDPSRUHFLEH

FRPRYDORU1,/YDFR

$FRQWLQXDFLQVHPXHVWUDHOHVTXHPDGHXQDOLVWD

2SHUDFLRQHVHQ/LVWDV(QOD]DGDV

/DVRSHUDFLRQHVTXHSRGHPRVUHDOL]DUVREUHXQDOLVWDHQOD]DGDVRQODV

VLJXLHQWHV

Recorrido. Esta operacin consiste en visitar cada uno de los nodos que forman la lista . Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dar la direccin del tercer nodo, y as sucesivamente.

Insercin. Esta operacin consiste en agregar un nuevo nodo a la lista. Para esta operacin se pueden considerar tres casos:

o Insertar un nodo al inicio.o Insertar un nodo antes o despus de cierto nodo.o Insertar un nodo al final.

Borrado. La operacin de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:

o Eliminar el primer nodo. o Eliminar el ltimo nodo. o Eliminar un nodo con cierta informacin. o Eliminar el nodo anterior o posterior al nodo cierta con informacin.

Bsqueda. Esta operacin consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.

/LVWDV/LQHDOHV

(QHVWDVHFFLQVHPRVWUDUQDOJXQRVDOJRULWPRVVREUHOLVWDVOLQHDOHVVLQQRGR

GHFDEHFHUD\FRQQRGRGHFDEHFHUD

8QDOLVWDFRQQRGRGHFDEHFHUDHVDTXHOODHQODTXHHOSULPHUQRGRGHODOLVWD

FRQWHQGUHQVXFDPSRGDWRDOJQYDORUTXHORGLIHUHQFHGHORVGHPVQRGRV

FRPRHWF8QHMHPSORGHOLVWDFRQQRGRGHFDEHFHUDHVHOVLJXLHQWH

(QHOFDVRGHXWLOL]DUOLVWDVFRQQRGRGHFDEHFHUDXVDUHPRVHODSXQWDGRU&$%

SDUDKDFHUUHIHUHQFLDDODFDEH]DGHODOLVWD

3DUDHOFDVRGHODVOLVWDVVLQQRGRGHFDEHFHUDVHXVDUODH[SUHVLQ723

SDUDUHIHUHQFLDUDOSULPHUQRGRGHODOLVWD\723GDWR723OLJDSDUDKDFHU

UHIHUHQFLDDOGDWRDOPDFHQDGR\DODOLJDDOVLJXLHQWHQRGRUHVSHFWLYDPHQWH

$OJRULWPRGH&UHDFLQ

WRS1,/

UHSLWH

QHZS

OHHUSGDWR

VLWRS 1,/HQWRQFHV

WRSS

HQFDVRFRQWUDULR

TOLJDS

SOLJD1,/

TS

PHQVDMHRWURQRGR"

OHHUUHVSXHVWD

KDVWDUHVSXHVWD QR

$OJRULWPRSDUD5HFRUULGR

SWRS

PLHQWUDVS!1,/KD]

HVFULEHSGDWR

SSOLJD

$OJRULWPRSDUDLQVHUWDUDOILQDO

SWRS

PLHQWUDVSOLJD!1,/KD]

SSOLJD

QHZT

SOLJDT

TOLJD1,/

$OJRULWPRSDUDLQVHUWDUDQWHVGHVSXVGH;LQIRUPDFLQ

SWRS

PHQVDMHDQWHVGHVSXHV

OHHUHVSXHVWD

VLDQWHVHQWRQFHV

PLHQWUDVS!1,/KD]

VLSGDWR [HQWRQFHV

QHZT

OHHUTGDWR

TOLJDS

VLS WRSHQWRQFHV

WRST

HQFDVRFRQWUDULR

UOLJDT

SQLO

HQFDVRFRQWUDULR

US

SSOLQN

VLGHVSXHVHQWRQFHV

SWRS

PLHQWUDVS!1,/KD]

VLSGDWR [HQWRQFHV

QHZT

OHHUTGDWR

TOLJDSOLJD

SOLJDT

S1,/

HQFDVRFRQWUDULR

SSOLJD

SWRS

PLHQWUDVSOLJD!1,/KD]

SSOLJD

QHZT

SOLJDT

TOLJD1,/

$OJRULWPRSDUDERUUDUXQQRGR

SWRS

OHHUYDORUBDBERUUDU

PLHQWUDVS!1,/KD]

VLSGDWR YDORUBDBERUUDUHQWRQFHV

VLS WRSHQWRQFHV

VLSOLJD 1,/HQWRQFHV

WRS1,/

HQFDVRFRQWUDULR

WRSOLJDWRSOLJD

HQFDVRFRQWUDULR

TOLJDSOLJD

GLVSRVHS

S1,/

HQFDVRFRQWUDULR

TS

SSOLJD

$OJRULWPRGHFUHDFLQGHXQDOLVWDFRQQRGRGHFDEHFHUD

QHZFDE

FDEGDWR

FDEOLJD1,/

TFDE

UHSLWH

QHZS

OHHUSGDWR

SOLJD1,/

TS

PHQVDMHRWURQRGR"

OHHUUHVSXHVWD

KDVWDUHVSXHVWD QR

$OJRULWPRGHH[WUDFFLQHQXQDOLVWDFRQQRGRGHFDEHFHUD

OHHUYDORUBDBERUUDU

SFDE

TFDEOLJD

PLHQWUDVT!1,/KD]

VLTGDWR YDORUBDBERUUDUHQWRQFHV

STOLJD

GLVSRVHT

T1,/

HQFDVRFRQWUDULR

ST

TTOLJD

/LVWDV'REOHV

8QDOLVWDGREOHGREOHPHQWHOLJDGDHVXQDFROHFFLQGHQRGRVHQODFXDO

FDGDQRGRWLHQHGRVSXQWHURVXQRGHHOORVDSXQWDQGRDVXSUHGHFHVRUOL\

RWURDVXVXFHVRUOG3RUPHGLRGHHVWRVSXQWHURVVHSRGUDYDQ]DUR

UHWURFHGHUDWUDYVGHODOLVWDVHJQVHWRPHQODVGLUHFFLRQHVGHXQRXRWUR

SXQWHUR

/DHVWUXFWXUDGHXQQRGRHQXQDOLVWDGREOHHVODVLJXLHQWH

([LVWHQGRVWLSRVGHOLVWDVGREOHPHQWHOLJDGDV

Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodo como el derecho del ltimo nodo apuntan a NIL.

Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al ltimo nodo de la lista, y el puntero derecho del ltimo nodo apunta al primer nodo de la lista.

'HELGRDTXHODVOLVWDVGREOHVFLUFXODUHVVRQPVHILFLHQWHVORVDOJRULWPRVTXH

HQHVWDVHFFLQVHWUDWHQVHUQVREUHOLVWDVGREOHVFLUFXODUHV

(QODILJXUDVLJXLHQWHVHPXHVWUDXQHMHPSORGHXQDOLVWDGREOHPHQWHOLJDGD

OLQHDOTXHDOPDFHQDQPHURV

(QODILJXUDVLJXLHQWHVHPXHVWUDXQHMHPSORGHXQDOLVWDGREOHPHQWHOLJDGD

FLUFXODUTXHDOPDFHQDQPHURV

$FRQWLQXDFLQPRVWUDUHPRVDOJXQRVDOJRULWPRVVREUHOLVWDVHQOD]DGDV&RPR

\DVHPHQFLRQOODPDUHPRVOLDOSXQWHURL]TXLHUGR\OGDOSXQWHURGHUHFKR

WDPELQXVDUHPRVHODSXQWDGRUWRSSDUDKDFHUUHIHUHQFLDDOSULPHUQRGRHQOD

OLVWD\SSDUDUHIHUHQFLDUDOQRGRSUHVHQWH

$OJRULWPRGHFUHDFLQ

WRS1,/

UHSLWH

VLWRS 1,/HQWRQFHV

QHZS

OHHSGDWR

SOGS

SOLS

WRSS

HQFDVRFRQWUDULR

QHZS

OHHSGDWR

SOGWRS

SOLS

SOGOLS

PHQVDMHRWURQRGR"

OHHUHVSXHVWD

KDVWDUHVSXHVWD QR

$OJRULWPRSDUDUHFRUUHUODOLVWD

5(&255,'2$/$'(5(&+$

SWRS

UHSLWH

HVFULEHSGDWR

SSOG

KDVWDS WRS

5(&255,'2$/$,=48,(5'$

SWRS

UHSLWH

HVFULEHSGDWR

SSOL

KDVWDS WRSOL

$OJRULWPRSDUDLQVHUWDUDQWHVGH;LQIRUPDFLQ

SWRS

PHQVDMHDQWHVGH"

OHH[

UHSLWH

VLSGDWR [HQWRQFHV

QHZT

OHHUTGDWR

VLS WRSHQWRQFHV

WRST

TOGS

TOLSOL

SOGOLT

SOLT

SWRS

HQFDVRFRQWUDULR

SSOG

KDVWDS WRS

$OJRULWPRSDUDLQVHUWDUGHVSXHVGH;LQIRUPDFLQ

SWRS

PHQVDMHGHVSXHVGH"

OHH[

UHSLWH

VLSGDWR [HQWRQFHV

QHZT

OHHTGDWR

TOGSOG

TOLS

SOLOGT

SOGT

SWRS

HQFDVRFRQWUDULR

SSOG

KDVWDS WRS

$OJRULWPRSDUDERUUDUXQQRGR

SWRS

PHQVDMH9DORUDERUUDU

OHHYDORUBDBERUUDU

UHSLWH

VLSGDWR YDORUBDBERUUDUHQWRQFHV

SOGOLSOG

SOLOGSOL

VLS WRSHQWRQFHV

VLSOG SOLHQWRQFHV

WRSQLO

HQFDVRFRQWUDULR

WRSWRSOG

GLVSRVHS

SWRS

HQFDVRFRQWUDULR

SSOG

KDVWDS WRS

/LVWDV&LUFXODUHV

/DVOLVWDVFLUFXODUHVWLHQHQODFDUDFWHUVWLFDGHTXHHOOWLPRHOHPHQWRGHOD

PLVPDDSXQWDDOSULPHUR

/DVLJXLHQWHILJXUDHVXQDUHSUHVHQWDFLQJUILFDGHXQDOLVWDFLUFXODU

(QVHJXLGDVHPRVWUDUQORVDOJRULWPRVPVFRPXQHVHQOLVWDVFLUFXODUHV$O

LJXDOTXHHQODVVHFFLRQHVDQWHULRUHVXWLOL]DUHPRVHODSXQWDGRUWRSSDUDKDFHU

UHIHUHQFLDDOSULPHUQRGRHQODOLVWD

$OJRULWPRGHFUHDFLQ

UHSLWH

QHZS

OHHSGDWR

VLWRS QLOHQWRQFHV

WRSS

TS

HQFDVRFRQWUDULR

TOLJDS

TS

SOLJDWRS

PHQVDMHRWURQRGR"

OHHUHVSXHVWD

KDVWDUHVSXHVWD QR

$OJRULWPRSDUDUHFRUUHUODOLVWD

SWRS

UHSLWH

HVFULEHSGDWR

SSOLJD

KDVWDS WRS

$OJRULWPRSDUDLQVHUWDUDQWHVGH;LQIRUPDFLQ

QHZS

OHHSGDWR

VLWRS QLOHQWRQFHV

WRSS

SOLJDWRS

HQFDVRFRQWUDULR

PHQVDMHDQWHVGH"

OHH[

TWRS

UWRSOLJD

UHSLWH

VLTGDWR [HQWRQFHV

SOLJDT

UOLJDS

VLSOLJD WRSHQWRQFHV

WRSS

TTOLJD

UUOLJD

KDVWDT WRS

$OJRULWPRSDUDLQVHUWDUGHVSXVGH;LQIRUPDFLQ

QHZS

OHHSGDWR

PHQVDMHGHVSXVGH"

OHH[

TWRS

UWRSOLJD

UHSLWH

VLTGDWR [HQWRQFHV

TOLJDS

SOLJDU

TTOLJD

UUOLJD

KDVWDT WRS

$OJRULWPRSDUDERUUDU

PHQVDMHYDORUDERUUDU

OHHYDORUBDBERUUDU

TWRS

UWRS

SWRS

PLHQWUDVTOLJD!WRSKD]

TTOLJD

UHSLWH

VLSGDWR YDORUBDBERUUDUHQWRQFHV

VLS WRSHQWRQFHV

VLWRSOLJD WRSHQWRQFHV

WRS1,/

HQFDVRFRQWUDULR

WRSWRSOLJD

TOLJDWRS

HQFDVRFRQWUDULR

UOLJDSOLJD

GLVSRVHS

SWRS

HQFDVRFRQWUDULR

US

SSOLJD

KDVWDS WRS

/LVWDV2UWRJRQDOHV

(QHVWHWLSRGHOLVWDVHXWLOL]DSDUDUHSUHVHQWDUPDWULFHV/RVQRGRVFRQWLHQHQ

FXDWURDSXQWDGRUHV8QRSDUDDSXQWDUDOQRGRL]TXLHUGROLRWURSDUDDSXQWDUDO

GHUHFKROGRWURDOQRGRLQIHULRUOE\SRUOWLPRXQDSXQWDGRUDOQRGR

VXSHULRUOD

&UHDFLQGHXQDOLVWDRUWRJRQDO

WRSQLO

PHQVDMHQPHURGHUHQJORQHV

OHHQPUHRBUHQJORQHV

PHQVDMHQPHURGHFROXPQDV

OHHQPHURBFROXPQDV

GHVGH\ KDVWDQPHURBUHQJORQHVKD]

QHZS

OHHSGDWR

SOLS

SOGS

VLWRS 1,/HQWRQFHV

WRSS

WRSOES

HQFDVRFRQWUDULR

SODWRSOD

SOEODS

SOEWRS

WRSODS

TWRS

GHVGH\ KDVWDQPHURBFROXPQDVKD]

V1,/

GHVGHM KDVWDQPHURBUHQJORQHVKD]

QHZT

SOGT

SOLTOL

SOGOLS

TOLS

VLV 1,/HQWRQFHV

VS

SODS

SOES

HQFDVRFRQWUDULR

SODVOD

SOEODS

SOEV

VODS

TTOE

$OJRULWPRSDUDUHFRUUHUXQDOLVWDRUWRJRQDO

TWRS

UHSLWH

ST

UHSLWH

HVFULEHSGDWR

SSOG

KDVWDS T

TTOE

KDVWDT WRS

%RUUDGRHQOLVWDVRUWRJRQDOHV

TWRS

PHQVDMHYDORUDERUUDU

OHHYDORUBDBERUUDU

UHSLWH

ST

UHSLWH

VLSGDWR YDORUBDBERUUDUHQWRQFHV

VLS WRSHQWRQFHV

SGDWR

HQFDVRFRQWUDULR

DX[S

SOGOLSOG

SOLOGSOL

SODOESOD

SOEODSOE

GLVSRVHDX[

ST

HQFDVRFRQWUDULR

SSOG

KDVWDS T

TTOE

KDVWDT WRS

81,'$',9(6758&785$612/,1($/(6

$ORVDUEROHVRUGHQDGRVGHJUDGRGRVVHOHVFRQRFHFRPRDUEROHVELQDULRV\D

TXHFDGDQRGRGHOUEROQRWHQGUPVGHGRVGHVFHQGLHQWHVGLUHFWRV/DV

DSOLFDFLRQHVGHORVDUEROHVELQDULRVVRQPX\YDULDGDV\DTXHVHOHVSXHGH

XWLOL]DUSDUDUHSUHVHQWDUXQDHVWUXFWXUDHQODFXDOHVSRVLEOHWRPDUGHFLVLRQHV

FRQGRVRSFLRQHVHQGLVWLQWRVSXQWRV

/DUHSUHVHQWDFLQJUILFDGHXQUEROELQDULRHVODVLJXLHQWH

5HSUHVHQWDFLQHQ0HPRULD

+D\GRVIRUPDVWUDGLFLRQDOHVGHUHSUHVHQWDUXQUEROELQDULRHQPHPRULD

Por medio de datos tipo punteros tambin conocidos como variables dinmicas o listas.

Por medio de arreglos.

6LQHPEDUJRODPVXWLOL]DGDHVODSULPHUDSXHVWRTXHHVODPVQDWXUDOSDUD

WUDWDUHVWHWLSRGHHVWUXFWXUDV

/RVQRGRVGHOUEROELQDULRVHUQUHSUHVHQWDGRVFRPRUHJLVWURVTXH

FRQWHQGUQFRPRPQLPRWUHVFDPSRV(QXQFDPSRVHDOPDFHQDUOD

LQIRUPDFLQGHOQRGR/RVGRVUHVWDQWHVVHXWLOL]DUQSDUDDSXQWDUDOVXEDUERO

L]TXLHUGR\GHUHFKRGHOVXEDUEROHQFXHVWLQ

&DGDQRGRVHUHSUHVHQWDJUILFDPHQWHGHODVLJXLHQWHPDQHUD

(ODOJRULWPRGHFUHDFLQGHXQUEROELQDULRHVHOVLJXLHQWH

3URFHGLPLHQWRFUHDUTQRGR

LQLFLR

PHQVDMH5DPDL]TXLHUGD"

OHHUHVSXHVWD

VLUHVSXHVWD VLHQWRQFHV

QHZS

TOLQLO

FUHDUS

HQFDVRFRQWUDULR

TOLQLO

PHQVDMH5DPDGHUHFKD"

OHHUHVSXHVWD

VLUHVSXHVWD VLHQWRQFHV

QHZS

TOGS

FUHDUS

HQFDVRFRQWUDULR

TOGQLO

ILQ

,1,&,2

QHZS

UDL]S

FUHDUS

),1

&ODVLILFDFLQGH$UEROHV%LQDULRV

([LVWHQFXDWURWLSRVGHUEROELQDULR

A. B. Distinto. A. B. Similares. A. B. Equivalentes. A. B. Completos.

$FRQWLQXDFLQVHKDUXQDEUHYHGHVFULSFLQGHORVGLIHUHQWHVWLSRVGHUERO

ELQDULRDVFRPRXQHMHPSORGHFDGDXQRGHHOORV

$%',67,172

Se dice que dos rboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:

$%6,0,/$5(6

Dos arboles binarios son similares cuando sus estructuras son idnticas, pero la informacin que contienen sus nodos es diferente. Ejemplo:

$%(48,9$/(17(6

Son aquellos arboles que son similares y que adems los nodos contienen la misma informacin. Ejemplo:

$%&203/(726

Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho.

5HFRUULGRGHXQ$UERO%LQDULR

+D\WUHVPDQHUDGHUHFRUUHUXQUEROHQLQRUGHQSUHRUGHQ\SRVWRUGHQ&DGD

XQDGHHOODVWLHQHXQDVHFXHQFLDGLVWLQWDSDUDDQDOL]DUHOUEROFRPRVHSXHGH

YHUDFRQWLQXDFLQ

1. INORDENo Recorrer el subarbol izquierdo en inorden.o Examinar la raz. o Recorrer el subarbol derecho en inorden.

2. PREORDENo Examinar la raz. o Recorrer el subarbol izquierdo en preorden.o recorrer el subarbol derecho en preorden.

3. POSTORDENo Recorrer el subarbol izquierdo en postorden.o Recorrer el subarbol derecho en postorden.o Examinar la raz.

$FRQWLQXDFLQVHPXHVWUDXQHMHPSORGHORVGLIHUHQWHVUHFRUULGRVHQXQUERO

ELQDULR

Inorden: GDBHEIACJKF 3UHRUGHQ$%'*(+,&)-.

3RVWRUGHQ*'+,(%.-)&$

$UEROHV(QKHEUDGRV

([LVWHXQWLSRHVSHFLDOGHUEROELQDULROODPDGRHQKHEUDGRHOFXDOFRQWLHQH

KHEUDVTXHSXHGHQHVWDUDODGHUHFKDRDODL]TXLHUGD(OVLJXLHQWHHMHPSORHV

XQUEROELQDULRHQKHEUDGRDODGHUHFKD

ARBOL ENHEBRADO A LA DERECHA. Este tipo de rbol tiene un apuntador a la derecha que apunta a un nodo antecesor.

ARBOL ENHEBRADO A LA IZQUIERDA. Estos arboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden.

&RQWUROGH$FFHVRDORV(OHPHQWRVGHXQ$UUHJOR

(Q&HODFFHVRDORVHOHPHQWRVGHXQDUUHJORWLHQHTXHVHUFRQWURODGRSRUHO

SURJUDPDGRU\DTXHHOOHQJXDMHQRUHVWULQJHODSRVLELOLGDGGHDFFHVDUD

SRVLFLRQHVGHPHPRULDTXHHVWQPVDEDMRGHODOWLPDSRVLFLQUHVHUYDGD

SDUDHODUUHJOR/RPLVPRVXFHGHFXDQGRVHPDQHMDQFDGHQDVGRQGHHO

SURJUDPDGRUWLHQHODUHVSRQVDELOLGDGGHFRQWURODUHODFFHVRDORVFDUDFWHUHVGH

ODFDGHQDWRPDQGRFRPROPLWHHOWHUPLQDGRUQXOR(QHOOLVWDGRVH

SUHVHQWDXQHMHPSORGHDFFHVRDORVE\WHVFRORFDGRVDEDMRGHOWHUPLQDGRU

QXORGHXQDFDGHQDGDGDSRUHOXVXDULR

LQFOXGH3DUDJHWV\SXWV

LQFOXGH3DUDFOUVFU\JRWR[\

LQFOXGH3DUDVWUOHQ

YRLGPDLQ

^

FKDUQRPEUH>@

FOUVFU

JRWR[\

SXWV&XOHVWXQRPEUH"

JRWR[\

JHWVQRPEUH

FOUVFU

JRWR[\

SXWV(/(0(172&$5$&7(5',5(&&,21

IRULQW[ [[QRPEUH>[@QRPEUH>[@QRPEUH>[@X"F GSULQWI"QRPEUH>G@

JRWR[\[[[

&RORFDFLQGHORVHOHPHQWRVGHXQDFDGHQDHQPHPRULD5$0

$UEROHVHQ0RQWQ

(VWDVHFFLQFRQVLVWHHQWUDQVIRUPDUXQERVTXHHQXQUEROELQDULR

(QWHQGHUHPRVFRPRERVTXHDXQFRQMXQWRQRUPDOPHQWHRUGHQDGRGHGRVR

PVUEROHVJHQHUDOHV

/DVHULHGHSDVRVTXHGHEHPRVVHJXLUSDUDORJUDUODFRQYHUVLQGHXQERVTXH

HQXQUEROELQDULRHVODVLJXLHQWH

1. Enlazar horizontalmente las races de los distintos rboles generales. 2. Enlazar los hijos de cada nodo en forma horizontal (los hermanos). 3. Enlazar verticalmente el nodo padre con el hijo que se encuentra ms a la

izquierda. Adems debe eliminarse el vnculo de ese padre con el resto de sus hijos.

4. Debe rotarse el diagrama resultante aproximadamente 45 grados hacia la izquierda y as se obtendr el rbol binario correspondiente.

$UEROHVELQDULRVGHEXVTXHGD

8QUEROGHEVTXHGDELQDULDHVXQDHVWUXFWXUDDSURSLDGDSDUDPXFKDVGHODV

DSOLFDFLRQHVTXHVHKDQGLVFXWLGRDQWHULRUPHQWHFRQOLVWDV/DYHQWDMDHVSHFLDO

GHXWLOL]DUXQDUEROHVTXHVHIDFLOLWDODEVTXHGD

8QUEROELQDULRGHEVTXHGDHVDTXHOHQHOTXHHOKLMRGHODL]TXLHUGDVL

H[LVWHGHFXDOTXLHUQRGRFRQWLHQHXQYDORUPVSHTXHRTXHHOQRGRSDGUH\

HOKLMRGHODGHUHFKDVLH[LVWHFRQWLHQHXQYDORUPVJUDQGHTXHHOQRGR

SDGUH

8QHMHPSORGHDUEROELQDULRGHEVTXHGDHVHOVLJXLHQWH

/RVDUEROHVUHSUHVHQWDQODVHVWUXFWXUDVQROLQHDOHV\GLQPLFDVGHGDWRVPV

LPSRUWDQWHVHQFRPSXWDFLQ'LQPLFDVSRUTXHODVHVWUXFWXUDVGHUERO

SXHGHQFDPELDUGXUDQWHODHMHFXFLQGHXQSURJUDPD1ROLQHDOHVSXHVWRTXH

DFDGDHOHPHQWRGHOUEROSXHGHQVHJXLUOHYDULRVHOHPHQWRV

/RVDUEROHVSXHGHQVHUFRQVWUXLGRVFRQHVWUXFWXUDVHVWWLFDV\GLQPLFDV/DV

HVWWLFDVVRQDUUHJORVUHJLVWURV\FRQMXQWRVPLHQWUDVTXHODVGLQPLFDVHVWQ

UHSUHVHQWDGDVSRUOLVWDVLa definicin de rbol es la siguiente: es una estructura jerrquica aplicada sobre una coleccin de elementos u objetos llamados nodos; uno de los cuales es conocido como raz. adems se crea una relacin o parentesco entre los nodos dando lugar a trminos como padre, hijo, hermano, antecesor, sucesor, ansestro, etc.. Formalmente se define un rbol de tipo T como una estructura homognea que es la concatenacin de un elemento de tipo T junto con un nmero finito de arboles disjuntos, llamados subarboles. Una forma particular de rbol puede ser la estructura vaca. /DILJXUDVLJXLHQWHUHSUHVHQWDDXQUEROJHQHUDO

6HXWLOL]DODUHFXUVLQSDUDGHILQLUXQUEROSRUTXHUHSUHVHQWDODIRUPDPV

DSURSLDGD\SRUTXHDGHPVHVXQDFDUDFWHUVWLFDLQKHUHQWHGHORVPLVPRV

/RVDUEROHVWLHQHQXQDJUDQYDULHGDGGHDSOLFDFLRQHV3RUHMHPSORVHSXHGHQ

XWLOL]DUSDUDUHSUHVHQWDUIUPXODVPDWHPWLFDVSDUDRUJDQL]DUDGHFXDGDPHQWH

ODLQIRUPDFLQSDUDFRQVWUXLUXQUEROJHQHDOJLFRSDUDHODQOLVLVGHFLUFXLWRV

HOFWULFRV\SDUDQXPHUDUORVFDSWXORV\VHFFLRQHVGHXQOLEUR

/DWHUPLQRORJDTXHSRUORUHJXODUVHXWLOL]DSDUDHOPDQHMRGHDUEROHVHVOD

VLJXLHQWH

HIJO. X es hijo de Y, s y solo s el nodo X es apuntado por Y. Tambin se dice que X es descendiente directo de Y.

PADRE. X es padre de Y s y solo s el nodo X apunta a Y. Tambin se dice que X es antecesor de Y.

HERMANO. Dos nodos sern hermanos si son descendientes directos de un mismo nodo.

HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).

NODO INTERIOR. Es un nodo que no es raz ni terminal. GRADO. Es el nmero de descendientes directos de un determinado nodo. GRADO DEL ARBOL Es el mximo grado de todos los nodos del rbol. NIVEL. Es el nmero de arcos que deben ser recorridos para llegar a un

determinado nodo. Por definicin la raz tiene nivel 1. ALTURA. Es el mximo nmero de niveles de todos los nodos del rbol. PESO. Es el nmero de nodos del rbol sin contar la raz. LONGITUD DE CAMINO. Es el nmero de arcos que deben ser recorridos

para llegar desde la raz al nodo X. Por definicin la raz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y as sucesivamente.

7UDQVIRUPDFLQGHXQ$UERO*HQHUDOHQXQ$UERO

%LQDULR

(QHVWDVHFFLQHVWDEOHFHUHPRVORVPHFDQLVPRVQHFHVDULRVSDUDFRQYHUWLUXQ

UEROJHQHUDOHQXQUEROELQDULR3DUDHVWRGHEHPRVVHJXLUORVSDVRVTXHVH

GHVFULEHQDFRQWLQXDFLQ

1. Enlazar los hijos de cada nodo en forma horizontal (los hermanos). 2. Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra ms a

la izquierda. Adems, debe eliminarse el vnculo de ese padre con el resto de sus hijos.

3. Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y as se obtendr el rbol binario correspondiente.

*5$)26

8QJUDIRGLULJLGR*FRQVLVWHHQXQFRQMXQWRGHYUWLFHV9\XQFRQMXQWRGH

DUFRVRDULVWDV$/RVYHUWLFHVHGHQRPLQDQWDPELQQRGRVRSXQWRV

8QDUFRHVXQSDURUGHQDGRGHYUWLFHV9:GRQGH9HVHOYUWLFHLQLFLDO\:

HVHOYUWLFHWHUPLQDOGHODUFR8QDUFRVHH[SUHVDFRPR9!:\VH

UHSUHVHQWDGHODVLJXLHQWHPDQHUD

/RVYUWLFHGHXQJUDIRSXHGHQXVDUVHSDUDUHSUHVHQWDUREMHWRV/RVDUFRVVH

XWLOL]DQSDUDUHSUHVHQWDUUHODFLRQHVHQWUHHVWRVREMHWRV

/DVDSOLFDFLRQHVPVLPSRUWDQWHVGHORVJUDIRVVRQODVVLJXLHQWHV

Rutas entre ciudades. Determinar tiempos mximos y mnimos en un proceso. Flujo y control en un programa.

/DWHUPLQRORJDTXHPDQHMDUHPRVUHJXODUPHQWHSDUDHOXVRGHJUDIRVHVOD

VLJXLHQWH

CAMINO.Es una secuencia de vrtices V1, V2, V3, ... , Vn, tal que cada uno de estos V1-&gtV2, V2-&gtV3, V1-&gtV3.

LONGITUD DE CAMINO. Es el nmero de arcos en ese camino. CAMINO SIMPLE. Es cuando todos sus vrtices, excepto tal vez el primero y el ltimo son

distintos. CICLO SIMPLE. Es un camino simple de longitud por lo menos de uno que empieza y termina

en el mismo vrtice. ARISTAS PARALELAS. Es cuando hay ms de una arista con un vrtice inicial y uno terminal

dados. GRAFO CICLICO. Se dice que un grafo es cclico cuando contiene por lo menos un ciclo. GRAFO ACICLICO. Se dice que un grafo es aciclco cuando no contiene ciclos. GRAFO CONEXO. Un grafo G es conexo, si y solo si existe un camino simple en cualesquiera

dos nodos de G. GRAFO COMPLETO FUERTEMENTE CONEXO.Un grafo dirigido G es completo si

para cada par de nodos (V,W) existe un camino de V a W y de W a V (forzosamente tendrn que cumplirse ambas condiciones), es decir que cada nodo G es adyacente a todos los dems nodos de G.

GRAFO UNILATERALMENTE CONEXO.Un grafo G es unilateralmente conexo si para cada par de nodos (V,W) de G hay un camino de V a W o un camino de W a V.

GRAFO PESADO ETIQUETADO. Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo un valor de cualquier tipo de dato. Tambin a este grafo se le denomina red de actividades, y el nmero asociado al arco se le denomina factor de peso.

VERTICE ADYACENTE. Un nodo o vrtice V es adyacente al nodo W si existe un arco de m a n.

GRADO DE SALIDA.El grado de salida de un nodo V de un grafo G, es el nmero de arcos o aristas que empiezan en V.

GRADO DE ENTRADA.El grado de entrada de un nodo V de un grafo G, es el nmero de aristas que terminan en V.

NODO FUENTE.Se le llama as a los nodos que tienen grado de salida positivo y un grado de entrada nulo.

NODO SUMIDERO.Se le llama sumidero al nodo que tiene grado de salida nulo y un grado de entrada positivo.

5HSUHVHQWDFLQ(Q0HPRULD6HFXHQFLDO

/RVJUDIRVVHUHSUHVHQWDQHQPHPRULDVHFXHQFLDOPHGLDQWHPDWULFHVGH

DG\DFHQFLD

8QDPDWU]GHDG\DFHQFLDHVXQDPDWU]GHGLPHQVLQQQHQGRQGHQHVHO

QPHURGHYUWLFHVTXHDOPDFHQDYDORUHVERROHDQRVGRQGHPDWU]0>LM@HV

YHUGDGHURVL\VRORVLH[LVWHXQDUFRTXHYD\DGHOYUWLFH\DOYUWLFHM

9HDPRVHOVLJXLHQWHJUDIRGLULJLGR

/DPDWU]GHDG\DFHQFLDTXHVHREWXYRDSDUWLUGHOJUDIRDQWHULRUHVOD

VLJXLHQWH

5HSUHVHQWDFLQHQ0HPRULD(QOD]DGD

/RVJUDIRVVHUHSUHVHQWDQHQPHPRULDHQOD]DGDPHGLDQWHOLVWDVGH

DG\DFHQFLD

8QDOLVWDGHDG\DFHQFLDVHGHILQHGHODVLJXLHQWHPDQHUD3DUDXQYUWLFHLHV

XQDOLVWDHQFLHUWRRUGHQIRUPDGDSRUWRGRVORVYUWLFHVDG\DFHQWHV>DL@6H

SXHGHUHSUHVHQWDUXQJUDIRSRUPHGLRGHXQDUUHJORGRQGHFDEH]DGHLHVXQ

DSXQWDGRUDODOLVWDGHDG\DFHQFLDDOYUWLFHL

9HDPRVHOVLJXLHQWHJUDIRGLULJLGR

/DOLVWDGHDG\DFHQFLDTXHVHREWXYRDSDUWLUGHOJUDIRDQWHULRUHVODVLJXLHQWH

2SHUDFLRQHV6REUH*UDIRV

(QHVWDVHFFLQDQDOL]DUHPRVDOJXQDVGHODVRSHUDFLRQHVVREUHJUDIRVFRPR

Creacin. Insercin. Bsqueda. Eliminacin.

En esta seccin, continuaremos utilizando los apuntadores que se usaron en las secciones anteriores. TOP para hacer referencia al primer nodo, LD para indicar liga derecha y LA para indicar liga abajo, por ltimo usaremos los apuntadores P y Q para hacer referencia a los nuevos nodos que vayan a ser usados.

$/*25,702'(&5($&,21

UHSLWH

VLWRS 1,/HQWRQFHV

QHZWRS

WRSOD1,/

WRSOG1,/

OHHWRSGDWR

TWRS

HQFDVRFRQWUDULR

QHZS

SOG1,/

SOD1,/

TODS

OHHSGDWR

TS

PHQVDMHRWURYHUWLFH"

OHHUHVSXHVWD

KDVWDUHSXHVWD QR

SWRS

PLHQWUDVS!1,/KD]

PHQVDMHWLHQHYUWLFHVDG\DFHQWHVSGDWR"

OHHUHVSXHVWD

VLUHVSXHWD VLHQWRQFHV

UHSLWH

QHZT

OHHTGDWR

TOGSOG

SOGT

PHQVDMHRWURYUWLFH"

OHHUHVSXHVWD

KDVWDUHVSXHVWD QR

SSOD

$/*25,702'(,16(5&,21

PHQVDMHYDORUDLQVHUWDU"

OHHYDORUBDBLQVHUWDU

VLWRS!1,/HQWRQFHV

SWRS

PLHQWUDVSOD!1,/KD]

SSOD

QHZT

OHHTGDWR

SODT

TOD1,/

PHQVDMH+D\YUWLFHVDG\DFHQWHV"

OHHUHVSXHVWD

VLUHVSXHVWD VLHQWRQFHV

PHQVDMH&XDQWRVYUWLFHV"

OHHQPHURBYUWLFHV

GHVGHL KDVWDQPHURBYUWLFHVKD]

QHZS

OHHSGDWR

TOGS

TTOG

HQFDVRFRQWUDULR

PHQVDMHQRH[LVWHOLVWD

$/*25,702'(%8648('$

PHQVDMHYUWLFHDEXVFDU

OHHYUWLFHBDBEXVFDU

SWRS

UHSLWH

VLSGDWR YUWLFHBDBEXVFDUHQWRQFHV

UHSLWH

SSOG

HVFULEHSGDWR

KDVWDSOG 1,/

HQFDVRFRQWUDULR

SOD

KDVWDS 1,/

$/*25,702'(%255$'2

PHQVDMHYUWLFHDERUUDU"

OHHYUWLFHBDBERUUDU

S/WWRS

US

TS

VZIDOVR

UHSLWH

VLSGDWR YUWLFHBDBERUUDUHQWRQFHV

VLS WRSHQWRQFHV

WRSWRSOD

UWRS

VZYHUGDGHUR

HQFDVRFRQWUDULR

UODSOD

UHSLWH

SSOG

GLVSRVHT

TS

KDVWDS 1,/

VLVZ YHUGDGHURHQWRQFHV

SU

TS

HQFDVRFRQWUDULR

SUOD

TS

HQFDVRFRQWUDULR

US

UHSLWH

TSOG

VLTGDWR YUWLFHBDBERUUDUHQWRQFHV

SOGTOG

GLVSRVHT

TS

HQFDVRFRQWUDULR

SSOG

KDVWDS 1,/

&DPLQR0QLPR

6HGHQRPLQDFDPLQRPQLPRHQWUHGRVYUWLFHV9\:DOFDPLQRSWLPRHQWUH

DPERVYUWLFHV3DUDGHWHUPLQDUHOFDPLQRPQLPRHQWUHGRVYUWLFHVVHXWLOL]D

HOVLJXLHQWHDOJRULWPRGHVGHL KDVWDQPHURBYUWLFHVKD]

GHVGHM KDVWDQPHURBYUWLFHVKD]

VLZ>LM@ HQWRQFHV

T>>LM@LQILQLWR

HQFDVRFRQWUDULR

T>LM@Z>LM@

GHVGHN KDVWDQPHURBYUWLFHVKD]

GHVGHL KDVWDQPHURBYUWLFHVKD]

GHVGHM KDVWDQPHURBYUWLFHVKD]

T>LM@PLQT>LM@T>LN@T>NM@