6530100
Description
Flashcards by Carlos Uribe G, updated more than 1 year ago
|
Created by Carlos Uribe G
over 7 years ago
|
|
| Question | Answer |
| QUE ES: Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Esto son definiciones simples. Pero las características que implican no lo son tanto. | |
| DEFINICIÓN: -Nodo hijo -Nodo padre -Nodo raíz -Nodo hoja -Nodo rama | SINTAXIS struct nodo { int dato; struct nodo *rama1; struct nodo *rama2; struct nodo *rama3; }; O generalizando más: #define ORDEN 5 struct nodo { int dato; struct nodo *rama[ORDEN]; }; |
| Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'. Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'. Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'. Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'. Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'. | ORDEN es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. |
| GRADO el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos. | NIVEL : se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3. |
| ALTURA la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc. | DECLARACIONES Para C, y basándonos en la declaración de nodo que hemos visto más arriba, trabajaremos con los siguientes tipos: typedef struct _nodo { int dato; struct _nodo *rama[ORDEN]; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Arbol; |
| Al igual que hicimos con las listas que hemos visto hasta ahora, declaramos un tipo tipoNodo para declarar nodos, y un tipo pNodo para es el tipo para declarar punteros a un nodo. Arbol es el tipo para declarar árboles de orden ORDEN. | |
| Arboles Binarios | ¿Qué es un árbol? Un árbol es una estructura de datos no lineal puesto que cada elemento apunta a uno o varios elementos del mismo tipo; esto es dado un elemento, no hay un único camino a seguir. El elemento que apunta a otro es llamado padre, mientras que el elemento apuntado se conoce como hijo. Todos los elementos tienen un padre a excepción de la raíz. Puede decirse que un árbol esta formado por subárboles resaltando así su naturaleza recursiva. |
| QUE ES UN ÁRBOL BINARIO Un ÁRBOL BINARIO es aquel es el que cada elemento apunta como máximo a otros 2 elementos, comúnmente llamados hijo izquierdo y hijo derecho. | |
| ÁRBOL BINARIO DE BÚSQUEDA Un árbol binario de buque da o ABB, es un árbol binario en el cual para todo elemento, los elementos mayores a él, se ubican en su rama derecha, mientras que los elementos menores van en su rama izquierda. Cada elemento se almacena una sola vez por lo que no existen elementos repetidos. | |
| Cada elemento(nodo) de un árbol ABB cuenta con tres campos: - Dato(numero, letra, palabra, etc), en este caso usaremos un numero(entero). - Puntero al nodo derecho - Puntero al nodo izquierdo | |
| RECORRIDOS DE ÁRBOL Es la manera recursiva como pasaremos por cada nodo del árbol, existes tres formas: | Enorden: Si visitamos primero hijo izquierdo, luego el padre y finalmente el hijo derecho Pre orden: Primero el padre, luego el hijo izquierdo y finalmente el hijo derecho. Postorden: Primero hijo izquierdo, luego el hijo derecho y finalmente el padre |
| OPERACIONES EN ARBOL BINARIO | VEREMOS LAS OPERACIONES BASICAS |
| Inserción El procedimiento de inserción en un árbol binario de búsqueda es muy sencillo, únicamente hay que tener cuidado de no romper la estructura ni el orden del árbol. | |
| Árbol en anchura: 4, 2, 8, 1, 3, 6, 9 | |
| Borrar El borrado en árboles binarios de búsqueda es otra operación bastante sencilla excepto en un caso. Vamos a ir estudiando los distintos casos. Tras realizar la búsqueda del nodo a eliminar observamos que el nodo no tiene hijos. Este es el caso más sencillo, únicamente habrá que borrar el elemento y ya habremos concuído la operación. | |
| Búsqueda La búsqueda Silaina consiste en acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. | Otras operaciones En los árboles de búsqueda la operación buscar es muy eficiente. El algoritmo compara el elemento a buscar con la raíz, si es menor continua la búsqueda por la rama izquierda, si es mayor continua por la izquierda. Este procedimiento se realiza recursivamente hasta que se encuentra el nodo o hasta que se llega al final del árbol. |
Want to create your own Flashcards for free with GoConqr? Learn more.