¿Qué es el nodo raíz de un árbol?

Es el primer elemento de un árbol. Es el punto de partida de la estructura jerárquica.

¿Cuál es la diferencia entre un ciclo for y un ciclo while?

El ciclo for se utiliza cuando se conoce la cantidad exacta de veces que debe ejecutarse una instrucción. El while se usa cuando no se sabe cuántas veces se repetirá, pues el número depende de las proposiciones dentro del ciclo y el ciclo termina cuando la condición se vuelve falsa.

Árboles binarios, AVL y B: conceptos y recorridos con ejemplos en C++

Q: ¿Qué hace la función getch en C++?

Lee un solo carácter directamente desde el teclado, sin mostrarlo en pantalla, y retorna ese carácter.

Resumen

Este documento repasa las estructuras de árboles más usadas: árboles binarios de búsqueda (ABB), árboles AVL con sus rotaciones y árboles B. Incluye la terminología básica de árboles y los tres tipos de recorridos (preorden, inorden y postorden). También recoge algunos conceptos de programación en C++, como los ciclos for y while, las estructuras o registros, la instrucción switch y la función getch.

Puntos clave

Un árbol binario de búsqueda tiene como máximo un hijo izquierdo y un hijo derecho por nodo, y al recorrerlo en inorden se obtiene la lista ordenada.
Un árbol AVL está equilibrado: en todos los nodos, las alturas de sus ramas izquierda y derecha no difieren en más de una unidad.
El reequilibrio de un AVL se realiza de abajo hacia arriba mediante rotaciones simples o dobles, a la derecha o a la izquierda.
Los árboles B aparecen habitualmente en bases de datos y sistemas de archivos, y sus nodos pueden tener más de dos hijos.
Los recorridos de árboles son preorden (raíz primero), inorden (raíz en medio) y postorden (raíz al final).
El ciclo for se usa cuando se conoce el número exacto de repeticiones, mientras que el while se usa cuando ese número depende de lo que ocurre dentro del ciclo.
Una estructura o registro permite agrupar datos de distintos tipos, a diferencia de los arreglos, que solo almacenan datos del mismo tipo.

Resumen generado con IA a partir del documento. Ponte a prueba

Árboles Binarios de Búsqueda (ABB)

Un árbol binario de búsqueda (ABB) es una estructura de datos donde cada nodo tiene, como máximo, un hijo a la izquierda y uno a la derecha. Para construir los algoritmos, consideramos que cada nodo tiene un registro con un valor clave a través del cual efectuaremos la búsqueda.

Propiedades: Al listar los nodos del ABB en inorden, obtenemos la lista de nodos ordenados.

Árboles AVL

Los árboles AVL son árboles equilibrados. Para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha, o viceversa.

Rotaciones

El reequilibrio se realiza de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos tipos de rotaciones: rotación simple o rotación doble, y ambos pueden ser a la derecha o a la izquierda.

Árboles B

Los árboles B son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos.

Son árboles binarios de búsqueda en los cuales cada nodo puede poseer más de dos hijos, existiendo una relación de orden entre ellos.

Conceptos de Programación en C++

Ciclo For

El ciclo for en C++ es uno de los más usados para repetir una secuencia de instrucciones, sobre todo cuando se conoce la cantidad exacta de veces que se quiere ejecutar una instrucción simple o compuesta.

Ciclo While

La estructura algorítmica "mientras", comúnmente conocida como while, es adecuada para utilizar en un ciclo cuando no sabemos el número de veces que este se ha de repetir. Dicho número depende de las proposiciones dentro del ciclo.

En este ciclo, el cuerpo de instrucciones se ejecuta mientras una condición permanezca como verdadera. En el momento en que la condición se convierte en falsa, el ciclo termina.

Estructura o Registro

Mientras que las variables simples pueden almacenar un dato de información y los arreglos pueden almacenar conjuntos de ellos del mismo tipo, una estructura o registro permite almacenar diferentes tipos de datos.

Instrucción Switch

La instrucción switch es una instrucción de decisión múltiple donde el compilador prueba y busca el valor contenido en una variable entera o carácter contra una lista de constantes. Cuando la computadora encuentra un valor de igualdad entre la variable y una constante, entonces se ejecuta el grupo de instrucciones asociadas.

Getch

La función getch lee un solo carácter directamente desde el teclado, sin mostrarlo en pantalla. Retorna el carácter leído.

Terminología de Árboles

La organización de los datos en una estructura jerárquica o de niveles se denomina árbol.

Nodo raíz: Es el primer elemento de un árbol.
Nodo padre: Nodo que tiene al menos un hijo.
Hijo derecho: Nodo que se encuentra al lado derecho de otro nodo.
Hijo izquierdo: Nodo que está al lado izquierdo de otro nodo.
Nodo hoja: Nodo que no tiene hijos.
Nodo hermano: Nodos que comparten el mismo padre.
Ancestros: Nodo padre de un nodo o el padre de algún nodo ancestro.
Nodo descendiente: El hijo de un nodo o el hijo de otro descendiente.
Subárbol izquierdo: Todos los descendientes por la izquierda de un nodo.
Subárbol derecho: Todos los descendientes por la derecha de un nodo.
Nivel de un nodo: Distancia desde la raíz.

Recorridos de Árboles

Preorden (Orden Previo): Se recorre primero la raíz y luego cada uno de los hijos (A1, A2…AK) en orden previo.

Inorden (Orden Simétrico): Se recorre primero A1, luego la raíz y luego cada uno de los hijos (A2…AK) en orden simétrico. Este nombre cobra mayor sentido en los árboles binarios.

Postorden (Orden Posterior): Se recorre primero cada uno de los hijos y, por último, la raíz.