Dadas dos arrays que representan recorridos previos y posteriores al pedido de un árbol binario completo, construya el árbol binario. Árbol binario completo es un árbol binario donde cada Node tiene 0 o 2 hijos.
Ilustración: Los siguientes son ejemplos de árboles completos.
1 / \ 2 3 / \ / \ 4 5 6 7 1 / \ 2 3 / \ 4 5 / \ 6 7 1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9
No es posible construir un árbol binario general a partir de recorridos previos y posteriores al pedido (consulte esto ). Pero si sabemos que el árbol binario está lleno, podemos construir el árbol sin ambigüedad. Entendamos esto con la ayuda del siguiente ejemplo.
Consideremos las dos arrays dadas como pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7} y post[] = {8, 9, 4, 5, 2, 6, 7 , 3, 1};
En pre[], el elemento más a la izquierda es la raíz del árbol. Dado que el árbol está lleno y el tamaño de la array es mayor que 1, el valor junto a 1 en pre[], debe ser hijo izquierdo de la raíz. Entonces sabemos que 1 es raíz y 2 es hijo izquierdo. ¿Cómo encontrar todos los Nodes en el subárbol izquierdo? Sabemos que 2 es la raíz de todos los Nodes en el subárbol izquierdo. Todos los Nodes antes del 2 en post[] deben estar en el subárbol izquierdo. Ahora sabemos que 1 es raíz, los elementos {8, 9, 4, 5, 2} están en el subárbol izquierdo y los elementos {6, 7, 3} están en el subárbol derecho.
1 / \ / \ {8, 9, 4, 5, 2} {6, 7, 3}
Seguimos recursivamente el enfoque anterior y obtenemos el siguiente árbol.
1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9
Implementación:
C++
// Program for construction of Full Binary Tree #include <bits/stdc++.h> using namespace std; // A binary tree node has data, pointer to left child // and a pointer to right child class node { public: int data; node* left; node* right; }; // A utility function to create a node node* newNode(int data) { node* temp = new node(); temp->data = data; temp->left = temp->right = NULL; return temp; } // A recursive function to construct Full from pre[] and // post[]. preIndex is used to keep track of index in pre[]. // l is low index and h is high index for the current // subarray in post[] node* constructTreeUtil(int pre[], int post[], int* preIndex, int l, int h, int size) { // Base case if (*preIndex >= size || l > h) return NULL; // The first node in preorder traversal is root. So take // the node at preIndex from preorder and make it root, // and increment preIndex node* root = newNode(pre[*preIndex]); ++*preIndex; // If the current subarray has only one element, no need // to recur if (l == h) return root; // Search the next element of pre[] in post[] int i; for (i = l; i <= h; ++i) if (pre[*preIndex] == post[i]) break; // Use the index of element found in postorder to divide // postorder array in two parts. Left subtree and right // subtree if (i <= h) { root->left = constructTreeUtil(pre, post, preIndex, l, i, size); root->right = constructTreeUtil(pre, post, preIndex, i + 1, h - 1, size); } return root; } // The main function to construct Full Binary Tree from // given preorder and postorder traversals. This function // mainly uses constructTreeUtil() node* constructTree(int pre[], int post[], int size) { int preIndex = 0; return constructTreeUtil(pre, post, &preIndex, 0, size - 1, size); } // A utility function to print inorder traversal of a Binary // Tree void printInorder(node* node) { if (node == NULL) return; printInorder(node->left); cout << node->data << " "; printInorder(node->right); } // Driver program to test above functions int main() { int pre[] = { 1, 2, 4, 8, 9, 5, 3, 6, 7 }; int post[] = { 8, 9, 4, 5, 2, 6, 7, 3, 1 }; int size = sizeof(pre) / sizeof(pre[0]); node* root = constructTree(pre, post, size); cout << "Inorder traversal of the constructed tree: \n"; printInorder(root); return 0; }
C
/* program for construction of full binary tree */ #include <stdio.h> #include <stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node *left; struct node *right; }; // A utility function to create a node struct node* newNode (int data) { struct node* temp = (struct node *) malloc( sizeof(struct node) ); temp->data = data; temp->left = temp->right = NULL; return temp; } // A recursive function to construct Full from pre[] and post[]. // preIndex is used to keep track of index in pre[]. // l is low index and h is high index for the current subarray in post[] struct node* constructTreeUtil (int pre[], int post[], int* preIndex, int l, int h, int size) { // Base case if (*preIndex >= size || l > h) return NULL; // The first node in preorder traversal is root. So take the node at // preIndex from preorder and make it root, and increment preIndex struct node* root = newNode ( pre[*preIndex] ); ++*preIndex; // If the current subarray has only one element, no need to recur if (l == h) return root; // Search the next element of pre[] in post[] int i; for (i = l; i <= h; ++i) if (pre[*preIndex] == post[i]) break; // Use the index of element found in postorder to divide // postorder array in two parts. Left subtree and right subtree if (i <= h) { root->left = constructTreeUtil (pre, post, preIndex, l, i, size); root->right = constructTreeUtil (pre, post, preIndex, i + 1, h-1, size); } return root; } // The main function to construct Full Binary Tree from given preorder and // postorder traversals. This function mainly uses constructTreeUtil() struct node *constructTree (int pre[], int post[], int size) { int preIndex = 0; return constructTreeUtil (pre, post, &preIndex, 0, size - 1, size); } // A utility function to print inorder traversal of a Binary Tree void printInorder (struct node* node) { if (node == NULL) return; printInorder(node->left); printf("%d ", node->data); printInorder(node->right); } // Driver program to test above functions int main () { int pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7}; int post[] = {8, 9, 4, 5, 2, 6, 7, 3, 1}; int size = sizeof( pre ) / sizeof( pre[0] ); struct node *root = constructTree(pre, post, size); printf("Inorder traversal of the constructed tree: \n"); printInorder(root); return 0; }
Java
// Java program for construction // of full binary tree public class fullbinarytreepostpre { // variable to hold index in pre[] array static int preindex; static class node { int data; node left, right; public node(int data) { this.data = data; } } // A recursive function to construct Full // from pre[] and post[]. preIndex is used // to keep track of index in pre[]. l is // low index and h is high index for the // current subarray in post[] static node constructTreeUtil(int pre[], int post[], int l, int h, int size) { // Base case if (preindex >= size || l > h) return null; // The first node in preorder traversal is // root. So take the node at preIndex from // preorder and make it root, and increment // preIndex node root = new node(pre[preindex]); preindex++; // If the current subarray has only one // element, no need to recur or // preIndex > size after incrementing if (l == h || preindex >= size) return root; int i; // Search the next element of pre[] in post[] for (i = l; i <= h; i++) { if (post[i] == pre[preindex]) break; } // Use the index of element found in // postorder to divide postorder array // in two parts. Left subtree and right subtree if (i <= h) { root.left = constructTreeUtil(pre, post, l, i, size); root.right = constructTreeUtil(pre, post, i + 1, h-1, size); } return root; } // The main function to construct Full // Binary Tree from given preorder and // postorder traversals. This function // mainly uses constructTreeUtil() static node constructTree(int pre[], int post[], int size) { preindex = 0; return constructTreeUtil(pre, post, 0, size - 1, size); } static void printInorder(node root) { if (root == null) return; printInorder(root.left); System.out.print(root.data + " "); printInorder(root.right); } public static void main(String[] args) { int pre[] = { 1, 2, 4, 8, 9, 5, 3, 6, 7 }; int post[] = { 8, 9, 4, 5, 2, 6, 7, 3, 1 }; int size = pre.length; node root = constructTree(pre, post, size); System.out.println("Inorder traversal of the constructed tree:"); printInorder(root); } } // This code is contributed by Rishabh Mahrsee
Python3
# Python3 program for construction of # full binary tree # A binary tree node has data, pointer # to left child and a pointer to right child class Node: def __init__(self, data): self.data = data self.left = None self.right = None # A recursive function to construct # Full from pre[] and post[]. # preIndex is used to keep track # of index in pre[]. l is low index # and h is high index for the # current subarray in post[] def constructTreeUtil(pre: list, post: list, l: int, h: int, size: int) -> Node: global preIndex # Base case if (preIndex >= size or l > h): return None # The first node in preorder traversal # is root. So take the node at preIndex # from preorder and make it root, and # increment preIndex root = Node(pre[preIndex]) preIndex += 1 # If the current subarray has only # one element, no need to recur if (l == h or preIndex >= size): return root # Search the next element # of pre[] in post[] i = l while i <= h: if (pre[preIndex] == post[i]): break i += 1 # Use the index of element # found in postorder to divide # postorder array in two parts. # Left subtree and right subtree if (i <= h): root.left = constructTreeUtil(pre, post, l, i, size) root.right = constructTreeUtil(pre, post, i + 1, h-1, size) return root # The main function to construct # Full Binary Tree from given # preorder and postorder traversals. # This function mainly uses constructTreeUtil() def constructTree(pre: list, post: list, size: int) -> Node: global preIndex return constructTreeUtil(pre, post, 0, size - 1, size) # A utility function to print # inorder traversal of a Binary Tree def printInorder(node: Node) -> None: if (node is None): return printInorder(node.left) print(node.data, end = " ") printInorder(node.right) # Driver code if __name__ == "__main__": pre = [ 1, 2, 4, 8, 9, 5, 3, 6, 7 ] post = [ 8, 9, 4, 5, 2, 6, 7, 3, 1 ] size = len(pre) preIndex = 0 root = constructTree(pre, post, size) print("Inorder traversal of " "the constructed tree: ") printInorder(root) # This code is contributed by sanjeev2552
C#
// C# program for construction // of full binary tree using System; class GFG { // variable to hold index in pre[] array public static int preindex; public class node { public int data; public node left, right; public node(int data) { this.data = data; } } // A recursive function to construct Full // from pre[] and post[]. preIndex is used // to keep track of index in pre[]. l is // low index and h is high index for the // current subarray in post[] public static node constructTreeUtil(int[] pre, int[] post, int l, int h, int size) { // Base case if (preindex >= size || l > h) { return null; } // The first node in preorder traversal is // root. So take the node at preIndex from // preorder and make it root, and increment // preIndex node root = new node(pre[preindex]); preindex++; // If the current subarray has only one // element, no need to recur or // preIndex > size after incrementing if (l == h || preindex >= size) { return root; } int i; // Search the next element // of pre[] in post[] for (i = l; i <= h; i++) { if (post[i] == pre[preindex]) { break; } } // Use the index of element found // in postorder to divide postorder // array in two parts. Left subtree // and right subtree if (i <= h) { root.left = constructTreeUtil(pre, post, l, i, size); root.right = constructTreeUtil(pre, post, i + 1, h-1, size); } return root; } // The main function to construct Full // Binary Tree from given preorder and // postorder traversals. This function // mainly uses constructTreeUtil() public static node constructTree(int[] pre, int[] post, int size) { preindex = 0; return constructTreeUtil(pre, post, 0, size - 1, size); } public static void printInorder(node root) { if (root == null) { return; } printInorder(root.left); Console.Write(root.data + " "); printInorder(root.right); } // Driver Code public static void Main(string[] args) { int[] pre = new int[] {1, 2, 4, 8, 9, 5, 3, 6, 7}; int[] post = new int[] {8, 9, 4, 5, 2, 6, 7, 3, 1}; int size = pre.Length; node root = constructTree(pre, post, size); Console.WriteLine("Inorder traversal of " + "the constructed tree:"); printInorder(root); } } // This code is contributed by Shrikant13
Javascript
<script> // Javascript program for construction // of full binary tree // variable to hold index in pre[] array var preindex = 0; class node { constructor(data) { this.data = data; } } // A recursive function to construct Full // from pre[] and post[]. preIndex is used // to keep track of index in pre[]. l is // low index and h is high index for the // current subarray in post[] function constructTreeUtil(pre, post, l, h, size) { // Base case if (preindex >= size || l > h) { return null; } // The first node in preorder traversal is // root. So take the node at preIndex from // preorder and make it root, and increment // preIndex var root = new node(pre[preindex]); preindex++; // If the current subarray has only one // element, no need to recur or // preIndex > size after incrementing if (l == h || preindex >= size) { return root; } var i; // Search the next element // of pre[] in post[] for (i = l; i <= h; i++) { if (post[i] == pre[preindex]) { break; } } // Use the index of element found // in postorder to divide postorder // array in two parts. Left subtree // and right subtree if (i <= h) { root.left = constructTreeUtil(pre, post, l, i, size); root.right = constructTreeUtil(pre, post, i + 1, h-1, size); } return root; } // The main function to construct Full // Binary Tree from given preorder and // postorder traversals. This function // mainly uses constructTreeUtil() function constructTree(pre, post, size) { preindex = 0; return constructTreeUtil(pre, post, 0, size - 1, size); } function printInorder(root) { if (root == null) { return; } printInorder(root.left); document.write(root.data + " "); printInorder(root.right); } // Driver Code var pre = [1, 2, 4, 8, 9, 5, 3, 6, 7]; var post = [8, 9, 4, 5, 2, 6, 7, 3, 1]; var size = pre.length; var root = constructTree(pre, post, size); document.write("Inorder traversal of " + "the constructed tree:<br>"); printInorder(root); </script>
Inorder traversal of the constructed tree: 8 4 9 2 5 1 6 3 7
Tiempo Complejidad: O(h), Espacio Auxiliar Espacio :O(h)
// h es la altura del árbol.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA