Construya un árbol binario a partir de un recorrido en orden y en orden previo
Escriba un algoritmo eficiente para construir un árbol binario a partir de la en orden y hacer un pedido secuencia.
Por ejemplo,
Input:
Inorder Traversal : { 4, 2, 1, 7, 5, 8, 3, 6 }
Preorder Traversal: { 1, 2, 4, 3, 5, 7, 8, 6 }
Output: Below binary tree
Inorder Traversal : { 4, 2, 1, 7, 5, 8, 3, 6 }
Preorder Traversal: { 1, 2, 4, 3, 5, 7, 8, 6 }
Output: Below binary tree
La idea es comenzar con el nodo raíz, que sería el primer elemento en la secuencia de preorden, y encontrar el límite de su subárbol izquierdo y derecho en la secuencia de orden. Para encontrar el límite, busque el índice del nodo raíz en la secuencia en orden. Todas las claves antes del nodo raíz en la secuencia en orden pasan a formar parte del subárbol izquierdo, y todas las claves después del nodo raíz pasan a formar parte del subárbol derecho. Repita esto recursivamentemente para todos los nodos del árbol y construya el árbol en el proceso.
Para ilustrar, considere la siguiente secuencia en orden y preorden:
Inorder : { 4, 2, 1, 7, 5, 8, 3, 6 }
Preorder : { 1, 2, 4, 3, 5, 7, 8, 6 }
Preorder : { 1, 2, 4, 3, 5, 7, 8, 6 }
La raíz será el primer elemento en la secuencia de preorden, es decir, 1. A continuación, ubique el índice del nodo raíz en la secuencia en orden. Ya que 1 es el nodo raíz, todos los nodos anteriores 1 en la secuencia en orden debe incluirse en el subárbol izquierdo, es decir, {4, 2} y todos los nodos después 1 debe incluirse en el subárbol derecho, es decir, {7, 5, 8, 3, 6}. Ahora el problema se reduce a construir los subárboles izquierdo y derecho y vincularlos al nodo raíz.
Left subtree:
Inorder : {4, 2}
Preorder : {2, 4}
Right subtree:
Inorder : {7, 5, 8, 3, 6}
Preorder : {3, 5, 7, 8, 6}
Inorder : {4, 2}
Preorder : {2, 4}
Right subtree:
Inorder : {7, 5, 8, 3, 6}
Preorder : {3, 5, 7, 8, 6}
La idea es seguir recursivamentemente el enfoque anterior hasta que se construya el árbol completo. Esto se demuestra a continuación en C, C++, Java y Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <stdio.h> #include <stdlib.h> // Estructura de datos para almacenar un nodo de árbol binario struct Node { int key; struct Node *left, *right; }; // Función para crear un nuevo nodo de árbol binario con una clave dada struct Node* newNode(int key) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->key = key; node->left = node->right = NULL; return node; } // Función recursivo para realizar un recorrido en orden en un árbol binario dado void inorderTraversal(struct Node* root) { if (root == NULL) { return; } inorderTraversal(root->left); printf("%d ", root->key); inorderTraversal(root->right); } // Función recursivo para realizar un recorrido de preorden en un árbol binario dado void preorderTraversal(struct Node* root) { if (root == NULL) { return; } printf("%d ", root->key); preorderTraversal(root->left); preorderTraversal(root->right); } // Función recursivo para construir un árbol binario a partir de un dado // secuencia en orden y preorden struct Node* construct(int inorder[], int start, int end, int preorder[], int *pIndex) { // caso base if (start > end) { return NULL; } // El siguiente elemento en `preorder[]` será el nodo raíz de // subárbol formado por secuencia representada por `inorder[start, end]` struct Node* node = newNode(preorder[(*pIndex)++]); // busca el índice del nodo raíz en la secuencia `inorder[]` para determinar el // límite izquierdo y derecho del subárbol int i; for (i = start; i <= end; i++) { if (inorder[i] == node->key) { break; } } // construye recursivamentemente el subárbol izquierdo node->left = construct(inorder, start, i - 1, preorder, pIndex); // construye recursivamentemente el subárbol derecho node->right = construct(inorder, i + 1, end, preorder, pIndex); // devuelve el nodo actual return node; } // Construir un árbol binario a partir de recorridos en orden y preorden. // Esta función asume que la entrada es válida, es decir, dada // La secuencia en orden y preorden forma un árbol binario. struct Node* constructTree(int inorder[], int preorder[], int n) { // `pIndex` almacena el índice del siguiente nodo sin procesar en una secuencia de preorden; // el nodo raíz está presente en el índice 0 en una secuencia de preorden int pIndex = 0; return construct(inorder, 0, n - 1, preorder, &pIndex); } int main() { /* Construimos el siguiente árbol 1 / \ / \ 2 3 / / \ / / \ 4 5 6 / \ / \ 7 8 */ int inorder[] = { 4, 2, 1, 7, 5, 8, 3, 6 }; int preorder[] = { 1, 2, 4, 3, 5, 7, 8, 6 }; int n = sizeof(inorder)/sizeof(inorder[0]); struct Node* root = constructTree(inorder, preorder, n); // atravesar el árbol construido printf("The inorder traversal is "); inorderTraversal(root); printf("\nThe preorder traversal is "); preorderTraversal(root); return 0; } |
Resultado:
The inorder traversal is 4 2 1 7 5 8 3 6
The preorder traversal is 1 2 4 3 5 7 8 6
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <iostream> #include <vector> #include <unordered_map> using namespace std; // Estructura de datos para almacenar un nodo de árbol binario struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Función recursivo para realizar un recorrido en orden en un árbol binario dado void inorderTraversal(Node* root) { if (root == nullptr) { return; } inorderTraversal(root->left); cout << root->key << ' '; inorderTraversal(root->right); } // Función recursivo para realizar un recorrido posterior al orden en un árbol binario dado void preorderTraversal(Node* root) { if (root == nullptr) { return; } cout << root->key << ' '; preorderTraversal(root->left); preorderTraversal(root->right); } // Función recursivo para construir un árbol binario a partir de un dado // secuencia en orden y preorden Node* construct(int start, int end, vector<int> const &preorder, int &pIndex, unordered_map<int, int> &map) { // caso base if (start > end) { return nullptr; } // El siguiente elemento en `preorder[]` será el nodo raíz del subárbol // formado por una secuencia representada por `inorder[start, end]` Node *root = new Node(preorder[pIndex++]); // obtener el índice del nodo raíz en secuencia `inorder[]` para determinar el // límite izquierdo y derecho del subárbol int index = map[root->key]; // construye recursivamentemente el subárbol izquierdo root->left = construct(start, index - 1, preorder, pIndex, map); // construye recursivamentemente el subárbol derecho root->right = construct(index + 1, end, preorder, pIndex, map); // devuelve el nodo actual return root; } // Construir un árbol binario a partir de recorridos en orden y preorden. // Esta función asume que la entrada es válida // es decir, la secuencia dada en orden y preorden forma un árbol binario Node* construct(vector<int> const &inorder, vector<int> const &preorder) { // obtener el número total de nodos en el árbol int n = inorder.size(); // crea un mapa para encontrar eficientemente el índice de cualquier elemento en // una secuencia dada en orden unordered_map<int, int> map; for (int i = 0; i < n; i++) { map[inorder[i]] = i; } // `pIndex` almacena el índice del siguiente nodo sin procesar en preorden; // comienza con el nodo raíz (presente en el índice 0) int pIndex = 0; return construct(0, n - 1, preorder, pIndex, map); } int main() { /* Construimos el siguiente árbol 1 / \ / \ 2 3 / / \ / / \ 4 5 6 / \ / \ 7 8 */ vector<int> inorder = { 4, 2, 1, 7, 5, 8, 3, 6 }; vector<int> preorder = { 1, 2, 4, 3, 5, 7, 8, 6 }; Node* root = construct(inorder, preorder); // atravesar el árbol construido cout << "The inorder traversal is "; inorderTraversal(root); cout << "\nThe preorder traversal is "; preorderTraversal(root); return 0; } |
Resultado:
The inorder traversal is 4 2 1 7 5 8 3 6
The preorder traversal is 1 2 4 3 5 7 8 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
import java.util.HashMap; import java.util.Map; import java.util.concurrent.atomic.AtomicInteger; // Una clase para almacenar un nodo de árbol binario class Node { int key; Node left, right; public Node(int key) { this.key = key; left = right = null; } } class Main { // Función recursivo para realizar un recorrido en orden en un árbol binario dado public static void inorderTraversal(Node root) { if (root == null) { return; } inorderTraversal(root.left); System.out.print(root.key + " "); inorderTraversal(root.right); } // Función recursivo para realizar un recorrido posterior al orden en un árbol binario dado public static void preorderTraversal(Node root) { if (root == null) { return; } System.out.print(root.key + " "); preorderTraversal(root.left); preorderTraversal(root.right); } // Función recursivo para construir un árbol binario a partir de un dado // secuencia en orden y preorden public static Node construct(int start, int end, int[] preorder, AtomicInteger pIndex, Map<Integer, Integer> map) { // caso base if (start > end) { return null; } // El siguiente elemento en `preorder[]` será el nodo raíz del subárbol // formado por una secuencia representada por `inorder[start, end]` Node root = new Node(preorder[pIndex.getAndIncrement()]); // obtener el índice del nodo raíz en secuencia `inorder[]` para determinar el // límite izquierdo y derecho del subárbol int index = map.get(root.key); // construye recursivamentemente el subárbol izquierdo root.left = construct(start, index - 1, preorder, pIndex, map); // construye recursivamentemente el subárbol derecho root.right = construct(index + 1, end, preorder, pIndex, map); // devuelve el nodo actual return root; } // Construir un árbol binario a partir de recorridos en orden y preorden. // Esta función asume que la entrada es válida, es decir, dada // La secuencia en orden y preorden forma un árbol binario. public static Node construct(int[] inorder, int[] preorder) { // crea un mapa para encontrar eficientemente el índice de cualquier elemento en // una secuencia dada en orden Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { map.put(inorder[i], i); } // `pIndex` almacena el índice del siguiente nodo sin procesar en un pedido previo // secuencia. Comenzamos con el nodo raíz (presente en el índice 0). AtomicInteger pIndex = new AtomicInteger(0); return construct(0, inorder.length - 1, preorder, pIndex, map); } public static void main(String[] args) { /* Construimos el siguiente árbol 1 / \ / \ 2 3 / / \ / / \ 4 5 6 / \ / \ 7 8 */ int[] inorder = { 4, 2, 1, 7, 5, 8, 3, 6 }; int[] preorder = { 1, 2, 4, 3, 5, 7, 8, 6 }; Node root = construct(inorder, preorder); // atravesar el árbol construido System.out.print("The inorder traversal is "); inorderTraversal(root); System.out.print("\nThe preorder traversal is "); preorderTraversal(root); } } |
Resultado:
The inorder traversal is 4 2 1 7 5 8 3 6
The preorder traversal is 1 2 4 3 5 7 8 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
# Una clase para almacenar un nodo de árbol binario class Node: # Constructor def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Función recursivo para realizar un recorrido en orden en un árbol binario dado def inorderTraversal(root): if root is None: return inorderTraversal(root.left) print(root.data, end=' ') inorderTraversal(root.right) # Función recursivo para realizar un recorrido posterior al pedido en un árbol binario dado def preorderTraversal(root): if root is None: return print(root.data, end=' ') preorderTraversal(root.left) preorderTraversal(root.right) # Función recursivo para construir un árbol binario a partir de un # orden y secuencia de preorden def construct(start, end, preorder, pIndex, d): # Caja base if start > end: return None, pIndex # El siguiente elemento en `preorder[]` será el nodo raíz del subárbol # formado por secuencia representada por `inorder[start, end]` root = Node(preorder[pIndex]) pIndex = pIndex + 1 # obtener el índice del nodo raíz para determinar el # límite de subárbol izquierdo y derecho index = d[root.data] # construye recursivamentemente el subárbol izquierdo root.left, pIndex = construct(start, index - 1, preorder, pIndex, d) # construye recursivamentemente el subárbol derecho root.right, pIndex = construct(index + 1, end, preorder, pIndex, d) # retorno nodo actual return root, pIndex # Construya un árbol binario a partir de recorridos en orden y en preorden. # Esta función asume que la entrada es válida # es decir, dada la secuencia en orden y preorden forma un árbol binario def constructTree(inorder, preorder): # crear un diccionario para encontrar eficientemente el índice de cualquier elemento en # una secuencia dada en orden d = {} for i, e in enumerate(inorder): d[e] = i # `pIndex` almacena el índice del siguiente nodo sin procesar en una secuencia de preorden; # comienza con el nodo raíz (presente en el índice 0) pIndex = 0 return construct(0, len(inorder) - 1, preorder, pIndex, d)[0] if __name__ == '__main__': ''' Construct the following tree 1 / \ / \ 2 3 / / \ / / \ 4 5 6 / \ / \ 7 8 ''' inorder = [4, 2, 1, 7, 5, 8, 3, 6] preorder = [1, 2, 4, 3, 5, 7, 8, 6] root = constructTree(inorder, preorder) # atravesar el árbol construido print('The inorder traversal is ', end='') inorderTraversal(root) print('\nThe preorder traversal is ', end='') preorderTraversal(root) |
Resultado:
The inorder traversal is 4 2 1 7 5 8 3 6
The preorder traversal is 1 2 4 3 5 7 8 6
La complejidad temporal de la solución C++, Java y Python es O(n), dónde n es el número total de nodos en el árbol binario. Ellos requieren O(n) espacio extra para hashing y recursividad. La complejidad temporal de la solución C es O(n2) y requiere O(n) espacio adicional para la pila de llamadas.
Ver también:
Construya un árbol binario completo a partir de una secuencia de orden previo y posterior