6531490
Description
Flashcards by Yessica Mecatl Segundo, updated more than 1 year ago
|
Created by Yessica Mecatl Segundo
over 7 years ago
|
|
| Question | Answer |
| Un árbol es un conjunto finito de nodos. Es una estructura jerárquica aplicable sobre una colección de elementos u objetos llamados nodos; uno de los cuales aplicable sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. | Los árboles representan las estructuras no lineales y dinámicas. No lineales, puesto que a cada elemento del árbol pueden seguir varios elementos. Dinámicas, puesto que la estructura estructura árbol puede cambiar durante la ejecución del programa. |
| Características Todo árbol que no es vacío, tiene un único nodo raíz. Un nodo X es descendiente directo de un nodo Y, si el nodo X apunta al nodo Y. X es hijo de Y. Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es el padre de Y. | Se dice que todos los nodos que son descendientes descendientes directos directos(hijos) de un mismo nodo (padre), son hermanos. Todo nodo que no tiene ramificaciones (hijos) se conoce con el nombre de terminal u hoja. Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior. |
| Propiedades Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol. Nivel es el número de arcos que deben ser recorridos para llegar a un determinado determinado nodo. Por definición definición la raíz tiene nivel 1. | Altura del árbol es el máximo número de niveles de todos los nodos del árbol. Rama es un camino desde el nodo raíz a una hoja. |
| Un árbol binario es un conjunto finito de nodos, el cual puede ser vacío o un conjunto conjunto que consta de un nodo raíz enlazado enlazado a dos árboles árboles binarios disjuntos denominados subárbol izquierdo y subárbol derecho. | Terminología Un árbol binario está balanceado (equilibrado) si cada nodo tiene exactamente dos hijos o no tiene hijos y si cada hoja está al mismo nivel. |
| Dos árboles binarios son distintos cuando sus estructuras son diferentes | Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contiene sus nodos difiere entre sí. |
| Dos árboles binarios son equivalentes si son similares y además los nodos contienen la misma información. | Se define como un árbol en el que todos sus nodos, excepto los del último nivel, tienen dos hijos; el subárbol izquierdo y el subárbol derecho. |
| Recorridos Recorrer un árbol binario significa visitar los nodos del árbol en forma sistemática, de tal manera que todos los nodos del mismo sean visitados una sola vez. | Existen tres formas diferentes de efectuar el recorrido (todos de forma recursiva) los cuales son: Recorrido en Preorden Recorrido en Inorden Recorrido en Posorden |
| RECORRIDO EN PREORDEN Visitar raíz (escribir la información del nodo). Recorrer el subárbol izquierdo en preorden. Recorrer el subárbol derecho en preorden. | RECORRIDO EN INORDEN Recorrer el subárbol izquierdo en Inorden Visitar raíz (procesar el valor en el nodo). Recorrer el subárbol derecho en Inorden |
| RECORRIDO EN POSORDEN Recorrer el subárbol izquierdo en Posorden Recorrer el subárbol derecho en Posorden Visitar raíz (procesar el valor en el nodo). | Un árbol binario de búsqueda (que no tiene los valores duplicados de nodos) tienen la característica que los valores en cualquier subárbol izquierdo son menores que el valor en sus nodos padres y los valores en cualquier cualquier subárbol subárbol derecho derecho son mayores mayores que el valor en sus nodos padres. |
Want to create your own Flashcards for free with GoConqr? Learn more.