Please enable JavaScript.
Coggle requires JavaScript to display documents.
ÁRBOLES BINARIOS Alumno: Juarez Zarazua Jerssou ICO O4 Organización de…
ÁRBOLES BINARIOS
Alumno: Juarez Zarazua Jerssou
ICO O4
Organización de archivos
Un árbol binario es un conjunto finito de elementos, el cual está
vacío o dividido en tres subconjuntos separados:
• El primer subconjunto contiene un elemento único llamado
raíz del árbol.
• El segundo subconjunto es en sí mismo un árbol binario y
se le conoce como subárbol izquierdo del árbol original.
• El tercer subconjunto es también un árbol binario y se le
conoce como subárbol derecho del árbol original.
caracteristicas
A un nodo que no tiene hijos, se le conoce como hoja.
Un nodo n1 es un
ancestro
de un nodo n2 (y n2 es un
descendiente
de n1) si n1 es el padre de n2 o el padre de algun ancestro
Recorrer un árbol de la raíz hacia las hojas se denomina
descender el árbol y al sentido opuesto ascender el árbol.
Un
árbol estrictamente binario
es aquel en el que cada nodo no es hoja, tiene subárboles izquierdo y derecho que no están vacíos
El nivel de un nodo en un árbol binario se define del modo
siguiente:
1.La raíz del árbol tiene el nivel 0.
2.El nivel de cualquier otro nodo en el árbol es uno más que el nivel de su padre.
La
profundidad o altura
de un árbol binario es el máximo
nivel de cualquier hoja en el árbol.
Operaciones de arboles binarios
Si p es un apuntador a un nodo nd de un árbol binario:
1.La función info(p) regresa el contenido de nd.
2.La función left(p) regresa un apuntador al hijo izquierdo de
nd.
3.La función right(p) regresa un apuntador al hijo derecho de
nd.
4.La función father(p) regresa un apuntador al padre de nd.
5.La función brother(p) regresa un apuntador al hermano de nd.
6.La función isLeft(p) regresa true si nd es un hijo izquierdo de
algún otro nodo en el árbol, y false en caso contrario.
7.La función isRight(p) regresa true si nd es un hijo derecho de
algún otro nodo en el árbol, y false en caso contrario.
operaciones para la construcción de un árbol binario
makeTree(x)
crea un árbol que consta de un nodo único con un campo de información x, y regresa un apuntador a este nodo
setLeft(p,x)
crea un nuevo hijo izquierdo de
node(p)
con el campo de información x
setRight(p,x)
crea un nuevo hijo derecho de
node(p)
con el campo de informacion x
Un árbol binario de búsqueda (ABB) no tiene valores
duplicados en los nodos y además, tiene la característica de que:
1.Los valores en cualquier subárbol izquierdo son menores que el valor en su nodo padre.
2.Los valores en cualquier subárbol derecho son mayores que el valor en su nodo padre.