Un árbol ordenado es un árbol orientado en el que los hijos de un Node están ordenados de alguna manera. Es un árbol enraizado en el que se especifica un ordenamiento para los hijos de cada vértice. Esto se llama un «árbol plano» porque el orden de los hijos es equivalente a una incrustación del … Continue reading «Combinatoria en árboles ordenados»
Hemos introducido el árbol de segmentos con un ejemplo simple en la publicación anterior. En esta publicación, el problema de consulta de rango mínimo se analiza como otro ejemplo en el que se puede usar el árbol de segmentos. El siguiente es el enunciado del problema: Tenemos un arreglo arr[0 . . . n-1]. Deberíamos … Continue reading «Árbol de segmentos | Conjunto 2 (consulta de rango mínimo)»
¿Qué es el lema del apretón de manos? El lema del apretón de manos se trata de un gráfico no dirigido. En todo grafo no dirigido finito, un número par de vértices siempre tendrá un grado impar. El lema del apretón de manos es una consecuencia de la fórmula de suma de grados (a veces … Continue reading «Lema del apretón de manos y propiedades interesantes del árbol»
Un árbol binario completo es un árbol binario donde cada nivel ‘l’ excepto el último tiene 2^l Nodes y los Nodes en el último nivel están todos alineados a la izquierda. Los árboles binarios completos se utilizan principalmente en estructuras de datos basadas en montón. Los Nodes en el árbol binario completo se insertan de izquierda … Continue reading «Árbol binario completo enlazado y su creación.»
Dos árboles son idénticos cuando tienen los mismos datos y la disposición de los datos también es la misma. Para identificar si dos árboles son idénticos, necesitamos atravesar ambos árboles simultáneamente, y mientras lo hacemos, necesitamos comparar los datos y los hijos de los árboles. Algoritmo: sameTree(tree1, tree2) 1. If both trees are empty then return … Continue reading «Escribir código para determinar si dos árboles son idénticos»
Dado un árbol con N Nodes y N-1 aristas, encuentre la altura máxima del árbol cuando cualquier Node en el árbol se considera como la raíz del árbol. El diagrama anterior representa un árbol con 11 Nodes y 10 aristas y el camino que nos da la altura máxima cuando se considera el Node 1 … Continue reading «Programación dinámica en árboles | conjunto 2»
Escriba una función para imprimir el recorrido en espiral de un árbol. Para el siguiente árbol, la función debe imprimir 1, 2, 3, 4, 5, 6, 7. Se le permite utilizar sólo una pila. Hemos visto soluciones recursivas e iterativas utilizando dos pilas . En esta publicación, se analiza una solución con una pila y … Continue reading «Recorrido de orden de nivel en forma de espiral | Usando una pila y una cola»
Dado un árbol binario , la tarea es imprimir todos los Nodes del árbol binario en Pre-order , Post-order y In-order iterativamente usando solo un recorrido de pila . Ejemplos: Aporte: Salida: Recorrido en orden previo : 1 2 3 Recorrido en orden: 2 1 3 Recorrido en orden posterior: 2 3 1 Aporte: Salida: … Continue reading «Recorrido en orden previo, posterior y en orden de un árbol binario usando una sola pila»
Dada una array de caracteres a[] que representa una expresión de prefijo. La tarea es construir un árbol de expresión para la expresión y luego imprimir la expresión de infijo y posfijo del árbol construido. Ejemplos: Entrada: a[] = “*+ab-cd” Salida: La expresión Infijo es: a + b * c – d La expresión Postfijo … Continue reading «Creación de un árbol de expresión a partir de una expresión de prefijo»
Dada una array arr[] y un entero K , la tarea es contar el número de sub-arrays que tienen OR bit a bit ≥ K. Ejemplos: Entrada: arr[] = { 1, 2, 3 } K = 3 Salida: 4 O bit a bit de subarrays: { 1 } = 1 { 1, 2 } = … Continue reading «El número de subarreglos tiene OR bit a bit >= K»