Tutorial de estructura de datos Lección 21 Definiciones y terminología de árboles y árboles binarios
Objetivo docente: Dominar los conceptos básicos y la terminología de árboles y árboles binarios, y las propiedades de los árboles binarios
Enfoque docente: La definición de árboles binarios, las propiedades de los árboles binarios
Dificultades de enseñanza: Propiedades de los árboles binarios
Contenido de la lección:
1. Definición de árbol:
Un árbol es un conjunto finito de n(ngt;=0) nodos. En cualquier árbol no vacío:
(1) Hay y solo hay un nodo específico llamado raíz
(2) Cuando ngt 1, el resto Los nodos pueden ser; dividido en m (mgt; 0) conjuntos finitos mutuamente disjuntos T1, T2,...Tm, cada uno de los cuales es en sí mismo un árbol y se denomina subárbol de la raíz.
2. Conceptos básicos de árboles :
Un nodo de árbol contiene un elemento de datos y varias ramas que apuntan a sus subárboles. 3. Definición de árbol binario
El árbol binario es otra estructura de árbol. Su característica es que cada nodo tiene como máximo dos subárboles (es decir, no hay nodos con grado mayor a 2 en el árbol binario). y Los subárboles de un árbol binario se pueden dividir en subárboles izquierdo y derecho, y su orden no se puede invertir arbitrariamente.
Un árbol binario con profundidad k y 2 (k) -1 nodos se denomina árbol binario completo, como se muestra en la Figura (a). Numere cada nodo como se muestra en la figura. con una profundidad de Un árbol binario de k con n nodos se llama árbol binario completo si y sólo si cada nodo corresponde a un nodo numerado del 1 al n en un árbol binario completo de profundidad k.
La definición de árbol binario es la siguiente:
ADT BinaryTree{
Objeto de datos D: D es una colección de elementos de datos con las mismas características.
Relación de datos R:
Operación básica P:
InitBiTree(amp; T);
DestroyBiTree(amp; T);
CreateBiTree(y T, definición);
ClearBiTree(y T);
BiTreeEmpty(T); (T);
Raíz(T);
Valor(T, e
Asignar(T, amp; e, valor); p> p>
Padre(T, e);
HijoIzquierdo(T, e);
HijoDerecho(T, e);
HermanoIzquierdo); (T , e);
RightSibling(T, e);
InsertChild(T, p, LR, c
DeleteChild(T, p); , LR
PreOrderTraverse(T, visita());
InOrderTraverse(T, visita()
PostOrderTraverse(T, visita()); );
LevelOrderTraverse(T, Visit());
}ADT BinaryTree
3. Propiedades de los árboles binarios
Propiedad 1 : En un árbol binario Hay como máximo 2 nodos de potencia i-1 en la i-ésima capa (igt; = 1).
Propiedad 2: Un árbol binario con profundidad k tiene como máximo 2 k-ésima potencia menos 1 nodo (kgt; = 1).
Propiedad 3: Para cualquier árbol binario T, si el número de nodos terminales es n0 y el número de nodos con grado 2 es n2, entonces n0=n2 1.
Propiedad 4: La profundidad de un árbol binario completo con n nodos es |log2n 1
Propiedad 5: Si para los nodos de un árbol binario completo con n nodos Numerados por nivel| , entonces para cualquier nodo i (1=lt; i=lt; n):
(1) Si i=1, entonces el nodo i es la raíz del árbol binario, no Parents si igt; 1, entonces el padre PADRE (i) es el nodo i/2
(2) Si 2igt; entonces el nodo i no tiene un hijo izquierdo (el nodo i es un nodo hoja); el hijo LCHILD(i) es el nodo 2i
(3) Si 2i 1gt;n, entonces el nodo i no tiene el hijo correcto, de lo contrario su hijo derecho RCHILD(i) es el nodo 2i 1
lt;/i=lt;n) tiene:
El número de subárboles que posee un nodo se denomina grado del nodo.
Los nodos con grado 0 se denominan hojas o nodos terminales.
Los nodos con un grado distinto de 0 se denominan nodos no terminales o nodos ramificados.
El grado de un árbol es el valor de grado de cada nodo del árbol.
La raíz del subárbol de un nodo se llama hijo del nodo y, en consecuencia, el nodo se llama padre del hijo.
Los hijos de unos mismos padres se llaman hermanos.
Los antepasados de un nodo son todos los nodos de las ramas desde la raíz hasta el nodo.
Cualquier nodo en el subárbol enraizado en un nodo se denomina descendiente de ese nodo.
La jerarquía de nodos se define desde la raíz. La raíz es el primer nivel y los hijos de la raíz son el segundo nivel. Los nodos cuyos padres están en el mismo nivel son primos entre sí. El nivel de los nodos en el árbol se llama profundidad o altura del árbol.
Si los subárboles de los nodos del árbol se ven ordenados de izquierda a derecha, el árbol se denomina árbol ordenado; de lo contrario, se denomina árbol desordenado.
Un bosque es una colección de m (mgt; = 0) árboles disjuntos.