A partir de ser vivo en la raíz, tal árbol se ramifican a los mamíferos, aves, vida marina, etc />
Árbol como estructura de datos
Un árbol es una estructura de datos que se hace de los nodos y enlaces, como una lista enlazada. La diferencia entre ellos radica en la forma en que se organizan.
- El nodo superior del árbol se llama el root y todos los demás nodos se ramifican desde ésta li>
- Cada nodo del árbol puede tener cierta cantidad de
. Cada nodo hijo puede a su vez ser el nodo padre a sus hijos, etc. - nodos hijos pueden tener vínculos sólo a partir de un solo padre
- Cualquier nodo más alto que el padre se llama antepasado nodo.
- nodos que no tienen hijos son llamados hojas (nodo hoja)
- Cualquier nodo que no es ni una raíz, ni una hoja se denomina nodo interior
- La altura de un árbol se define como el longitud de la ruta más larga de la raíz a una hoja i n ese árbol (incluida la ruta raíz)
Un interno nodo (también conocido como un nodo interno, inode para abreviar, o nodo rama) es cualquier nodo de un árbol que tiene nodos secundarios. Del mismo modo, un nodo externo (también conocido como un nodo exterior, nodo hoja o nodo terminal) es cualquier nodo que no tiene hijos nodos.
Binary Tree
Así, cada nodo puede tener ningún niño, un niño o dos niños.
Los punteros nos ayudan a identificar si se trata de un hijo de la izquierda o un niño bien.
(o)
Aplicación de un árbol binario
Antes de definir cualquier algoritmo formales, echemos un vistazo a una posible aplicación de un árbol binario
Considere un conjunto de números:. 25,63,13, 72,18,32,59,67.
Supongamos que guardamos estos números en los nodos individuales de una lista enlazada. Para buscar un elemento en particular, tenemos que ir a través de la lista, y tal vez hemos Togo hasta el final de la lista también. Por lo tanto si había un número n, nuestra complejidad búsqueda sería O (n).
¿Es porque los números no están en ningún orden determinado? Ahora supongamos que orden los siguientes números:
13,18,25,32,59,63,67,72. y almacenarlos en otra lista enlazada.
¿Cuál sería la complejidad búsqueda ahora? Es posible que se sorprenda al descubrir que todavía es O (n) .
Simplemente no se puede aplicar de búsqueda binaria en una lista enlazada con O (log n) complejidad. Usted todavía tiene que ir
través de cada enlace para localizar un número determinado. Así que una estructura ligada lineal no nos está ayudando en absoluto.
![un dibujo de un pequeño árbol binario](http://cslibrary.stanford.edu/110/binarytree.gif)
El árbol que se muestra más arriba es un árbol binario de búsqueda – el nodo «raíz» es un 5, y sus nodos subárbol izquierdo (1, 3, 4) son <= 5, y sus nodos subárbol derecho (6, 9) son> 5. De forma recursiva, cada uno de los subárboles también debe obedecer las restricciones árbol de búsqueda binaria: en el (1, 3, 4) sub árbol, el 3 es la raíz, el 1 <= 3 y 4> 3. Ten cuidado con la redacción exacta de los problemas – un «árbol binario de búsqueda» es diferente de un «árbol binario».
Los nodos en el borde inferior del árbol tienen subárboles vacíos y se llaman nodos «hoja» (1, 4, 6), mientras que los otros son nodos «internos» (3, 5, 9).
Tree Terminologías
Longitud de una ruta de acceso: La longitud de un camino es el número de nodos en el camino
El grado de un nodo es el número de aristas conectadas al nodo .
o ¿Cuántos nodos secundarios están conectados a ese nodo