Clase integral EU3

Matemática Discreta Ejercicios de Árboles dirigidos - búqueda 1. A continuación, se muestra el arreglo Left – Data – Right del árbol 𝑇 . ÍNDICE LEFT DATA RIGHT 1 2 2 3 A 0 3 4 B 11 4 5 C 10 5 6 D 7 6 0 E 0 7 8 F 9 8 0 G 0 9 0 H 0 10 0 I 0 11 0 J 12 12 13 K 17 13 14 L 16 14 0 M 15 15 0 N 0 16 0 O 0 17 0 P 0 Liste los nodos del árbol 𝐵(𝑇) en postorden, entreorden y preorden. 2. Determinar el valor de verdad de las siguientes afirmaciones: a) En un árbol dirigido (de al menos tres vértices), nunca se cumple que el listado de sus elementos en entreorden es idéntico al listado de sus elementos en postorden. b) Dado un árbol 𝑇 , en la lista de los elementos de 𝐵(𝑇) , en entreorden, siempre el último elemento es la raíz del árbol 𝑇 . c) Dado un árbol dirigido, todos los vértices del árbol tienen grado interno igual a 1. d) Un árbol dirigido es una relación asimétrica, conexa y acíclica. 3. El recorrido en PostOrden de un árbol binario es: DMLCTAISRUNOKB y al recorrerlo en EnOrden es: DMATLCBIKUSRON Se pide: a) Dibujar el árbol binario. b) Determinar el recorrido del árbol en PreOrden. 4. Dado el siguiente listado de los elementos de un árbol binario posicional 𝐵(𝑇) , determine el dígrafo del árbol T, además elabore el arreglo LEFT, DATA, RIGHT. ENTREORDEN: HJBCGFAIED POSTORDEN: JHCGBIAEFD Matemática Discreta 2 5. Dado el árbol T cuyos elementos son: {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺, 𝐻, 𝐼, 𝐽, 𝐾, 𝐿, 𝑀, 𝑁, 𝑂, 𝑃, 𝑄, 𝑅, 𝑆, 𝑇} , se tiene de manera incompleta, su dígrafo y el listado de sus elementos en posorden: POSORDEN J G A P T R E S Q N H K F I (a) Complete los elementos faltantes en el dígrafo del árbol T y en el listado en posorden. (b) Determine el dígrafo del árbol binario posicional B ( T ) (c) Determine el contenido de los arreglos LEFT, DATA y RIGHT. (d) Liste los nodos (vértices) del árbol B ( T ) en preorden y entreorden. 6. Abajo se muestran el árbol binario posicional B(T) y el listado en preorden de los elementos de B(T), correspondiente al árbol T ordenado cuyos vértices son: {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺, 𝐻, 𝐼, 𝐽, 𝐾, 𝐿, 𝑀, 𝑁, 𝑂} . (a) Completar los vértices del árbol B(T). (b) Dar el arreglo Left–Data–Right. (c) Trace el dígrafo del árbol T, determine la raíz, su tipo, su altura. (d) Liste los nodos (vértices) del árbol B(T) en entreorden y postorden. Preorden K D F B J N C M E T K D A T Q B L M N C O I O A G N B(T) H C Matemática Discreta 3 7. Abajo se muestran el árbol binario posicional B(T) y el arreglo Left – Data – Right correspondiente al árbol T. (a) Completar el arreglo Left – Data – Right y el árbol B(T). (b) Trace el dígrafo del árbol T, determine la raíz, su tipo, su altura. (c) Liste los nodos (vértices) del árbol ) ( T B en preorden, entreorden y postorden. ÍNDICE LEFT DATA RIGHT 1 14 2 A 6 3 B 4 C 7 5 3 D 6 E 13 7 F 8 G 9 H 12 10 I 16 11 J 12 K 13 L 14 5 M 15 N 16 11 O 8. Dado el arreglo LEFT, DATA, RIGHT correspondiente a un árbol binario posicional B(T): (a) obtenga el dígrafo del arbol original T, indicando la raíz y el tipo de n – árbol. (b) Liste los nodos (vértices) del árbol ) ( T B en preorden, entreorden y postorden. ÍNDICE LEFT DATA RIGHT 1 7 2 5 A 3 3 6 B 4 4 9 C 0 5 0 M 10 6 0 N 8 7 2 P 0 8 13 Q 11 9 0 S 0 10 0 T 0 11 0 U 12 12 0 W 0 13 0 X 0 9. Dado el árbol T cuyos elementos son: 𝑇 = { (𝐵, 𝐴), (𝐵, 𝐸), (𝐺, 𝐹), (𝐶, 𝐺), (𝐾, 𝐽), (𝐼, 𝐻), (𝐼, 𝐾), (𝑁, 𝑃), (𝑁, 𝑄), (𝑀, 𝐿), (𝑀, 𝑁), (𝑀, 𝑂), (𝐷, 𝐶), (𝐷, 𝐼), (𝐷, 𝑀), (𝐶, 𝐵) } (a) Trace el dígrafo del árbol T ordenado indicando la raíz y el tipo de n - árbol. (b) Trace el dígrafo del árbol binario posicional ) ( T B formado a partir del árbol T ordenado. (c) Determine el contenido de los arreglos LEFT, DATA y RIGHT. I O A G N C H B(T ) Matemática Discreta 4 (d) Liste los nodos (vértices) del árbol ) ( T B en preorden, entreorden y postorden.