Definiciones Fundamentales

• Nodo: Elemento básico que almacena datos y puede apuntar a nodos secundarios.
• Nodo raíz: Nodo inicial sin padre, punto de entrada del árbol.
• Nodo hijo: Nodo directamente conectdao a un nodo padre.
• Nodo padre: Nodo que tiene al menos un hijo.
• Nodo hermano: Nodos que comparten el mismo padre.
• Nodo hoja: Nodo sin hijos, ubicado en los extremos del árbol.
• Subárbol: Conjunto formado por un nodo y todos sus descendientes.
• Profundidad: Distancia desde el nodo raíz hasta un nodo específico, medida en número de aristas.
• Altura: Máxima profundidad del árbol, desde la raíz hasta la hoja más lejana.
• Nodo ancestro: Cualquier nodo en el camino desde la raíz hasta un nodo dado, incluyendo su padre.
• Nodo descendiente: Todos los nodos que se derivan de un nodo específico a través de sus hijos.

Recorridos de Árboles

Los recorridos permiten visitar todos los nodos de un árbol en un orden específico:

• Recorrido inorden: Se visita el subárbol izquierdo, luego el nodo raíz, y finalmente el subárbol derecho.
• Recorrido preorden: Se visita el nodo raíz primero, seguido por el subárbol izquierdo y el derecho.
• Recorrido postorden: Se visitan los subárboles izquierdo y derecho antes que el nodo raíz.

Cálculo de la Profundidad de un Árbol Binario

Para determinar la profundidad máxima de un árbol binario, se puede usar un algoritmo de búsqueda en profundidad (DFS). A continuación, un ejemplo en C++ con estructuras modificadas:

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 200010;
int nodeCount, maxHeight;
struct TreeNode {
    int leftChild, rightChild;
} treeNodes[MAXN];
void depthFirstSearch(int nodeId, int currentHeight) {
    if (nodeId == 0) return;
    maxHeight = max(maxHeight, currentHeight);
    depthFirstSearch(treeNodes[nodeId].leftChild, currentHeight + 1);
    depthFirstSearch(treeNodes[nodeId].rightChild, currentHeight + 1);
}
int main() {
    cin >> nodeCount;
    for (int idx = 1; idx <= nodeCount; idx++) {
        cin >> treeNodes[idx].leftChild >> treeNodes[idx].rightChild;
    }
    depthFirstSearch(1, 1);
    cout << maxHeight;
    return 0;
}

Este enfoque utiliza una estructura de nodos para representar el árbol y calcula la altura máxima mediante DFS.

Construcción y Recorrido de Árboles a partir de Secuencias

Se pueden reconstruir árboles binarios usando secuencias de recorrido, como preorden e inorden. Aquí un ejemplo en C++:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 200010;
string inorderSeq, preorderSeq;
void reconstructTree(int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) return;
    char rootVal = preorderSeq[preStart];
    int rootPos = inorderSeq.find(rootVal);
    reconstructTree(preStart + 1, preStart + (rootPos - inStart), inStart, rootPos - 1);
    reconstructTree(preStart + (rootPos - inStart) + 1, preEnd, rootPos + 1, inEnd);
    cout << rootVal;
}
int main() {
    cin >> inorderSeq >> preorderSeq;
    int seqLength = inorderSeq.size() - 1;
    reconstructTree(0, seqLength, 0, seqLength);
    return 0;
}

Recorrrido Preorden de un Árbol Binario con Mapa

Otro enfoque utiliza un mapa para almacenar las relaciones padre-hijo y realiza un recorrido preorden recursivo:

#include <iostream>
#include <map>
using namespace std;
char rootNode;
map<char, pair<char, char>> treeMap;
void preorderTraversal(char nodeId) {
    cout << nodeId;
    if (treeMap[nodeId].first != '*') preorderTraversal(treeMap[nodeId].first);
    if (treeMap[nodeId].second != '*') preorderTraversal(treeMap[nodeId].second);
}
int main() {
    int n;
    cin >> n;
    char left, right;
    cin >> rootNode >> left >> right;
    treeMap[rootNode] = {left, right};
    for (int i = 1; i < n; i++) {
        char node, l, r;
        cin >> node >> l >> r;
        treeMap[node] = {l, r};
    }
    preorderTraversal(rootNode);
    return 0;
}

Cálculo de Caminos y Ancestro Común Más Bajo (LCA)

Para problemas como la distancia entre nodos o el LCA, se puede usar BFS y precomputación. Ejemplo en C++:

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 200010;
int adjList[MAXN], nextEdge[MAXN], head[MAXN], depth[MAXN], width;
int parentTable[MAXN][16], distances[MAXN];
void addEdge(int from, int to) {
    static int edgeIdx = 0;
    adjList[edgeIdx] = to;
    nextEdge[edgeIdx] = head[from];
    head[from] = edgeIdx++;
}
void breadthFirstSearch() {
    memset(distances, 0x3f, sizeof(distances));
    queue<int> q;
    q.push(1);
    distances[1] = 1;
    distances[0] = 0;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int i = head[current]; i != -1; i = nextEdge[i]) {
            int neighbor = adjList[i];
            if (distances[neighbor] > distances[current] + 1) {
                distances[neighbor] = distances[current] + 1;
                depth = max(depth, distances[neighbor]);
                parentTable[neighbor][0] = current;
                q.push(neighbor);
                for (int k = 1; k <= 15; k++) {
                    parentTable[neighbor][k] = parentTable[parentTable[neighbor][k-1]][k-1];
                }
            }
        }
    }
}
int findLCA(int u, int v) {
    if (distances[u] < distances[v]) swap(u, v);
    for (int k = 15; k >= 0; k--) {
        if (distances[parentTable[u][k]] >= distances[v]) u = parentTable[u][k];
    }
    if (u == v) return u;
    for (int k = 15; k >= 0; k--) {
        if (parentTable[u][k] != parentTable[v][k]) {
            u = parentTable[u][k];
            v = parentTable[v][k];
        }
    }
    return parentTable[u][0];
}
int main() {
    int n, m;
    memset(head, -1, sizeof(head));
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }
    breadthFirstSearch();
    int startNode, endNode;
    cin >> startNode >> endNode;
    int lcaNode = findLCA(startNode, endNode);
    int pathLength = (distances[startNode] - distances[lcaNode]) * 2 + distances[endNode] - distances[lcaNode];
    cout << depth << endl << width << endl << pathLength;
    return 0;
}

Este código calcula la profundidad máxima, el ancho del árbol y la distancia entre dos nodos usando LCA.