Dada una array pre[] , que representa el recorrido Preorder de un Perfect Binary Tree que consta de N Nodes, la tarea es construir un Perfect Binary Tree a partir del Preorder Traversal dado y devolver la raíz del árbol.
Ejemplos:
Entrada: pre[] = {1, 2, 4, 5, 3, 6, 7}
Salida:
1
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7Entrada: pre[] = {1, 2, 3}
Salida:
1
/ \
/ \
2 3
En general, para construir un árbol binario, no podemos hacerlo usando solo el recorrido de orden previo, pero aquí se da una condición adicional de que el árbol binario es un árbol binario perfecto. Podemos usar esa condición extra.
Para el árbol binario perfecto, cada Node tiene 2 o 0 hijos, y todos los Nodes hoja están presentes en el mismo nivel. Y el recorrido en preorden de un árbol binario contiene primero la raíz, luego el recorrido en preorden del subárbol izquierdo, luego el recorrido en preorden del subárbol derecho. Entonces, para el árbol binario perfecto, la raíz debe tener el mismo número de hijos en ambos subárboles, por lo que el número (digamos, n) de elementos después de la raíz en el recorrido de preorden debe ser par (2 * número de Nodes en un subárbol, ya que es perfecto árbol binario) . Y dado que cada subárbol tiene el mismo número de Nodes para el árbol binario perfecto, podemos encontrar el recorrido en orden previo del subárbol izquierdo (que es la mitad de la array después de la raíz en el recorrido en orden previo de todo el árbol),
Entonces, el primer elemento en el recorrido preordenado es la raíz, construiremos un Node como la raíz con este elemento, luego podemos encontrar fácilmente los recorridos preordenados de los subárboles izquierdo y derecho de la raíz, y construiremos recursivamente los subárboles izquierdo y derecho. subárboles derechos de la raíz.
Enfoque: El problema dado se puede resolver usando recursividad . Siga los pasos a continuación para resolver el problema:
- Cree una función, digamos BuildPerfectBT_helper con parámetros como preStart , preEnd , pre[] donde preStart representa el índice inicial de la array pre[] y preEnd representa el índice final de la array pre[] y realiza los siguientes pasos:
- Si el valor de preStart es mayor que preEnd , devuelve NULL .
- Inicialice la raíz como pre[preStart] .
- Si el valor de preStart es el mismo que el de preEnd , devuelva root .
- Inicialice 4 variables, digamos leftPreStart como preStart + 1 , rightPreStart como leftPreStart + (preEnd – leftPreStart+1)/2 , leftPreEnd como rightPreStart – 1 y rightPreEnd como preEnd .
- Modifique el valor de root->left llamando recursivamente a la función buildPerfectBT_helper() con los parámetros leftPreStart , leftPreEnd y pre[] .
- Modifique el valor de root->right llamando recursivamente a la función buildPerfectBT_helper() con los parámetros rightPreStart , rightPreEnd y pre[] .
- Después de realizar los pasos anteriores, devuelva root .
- Después de crear el árbol binario perfecto, imprima el recorrido en orden del árbol .
A continuación se muestra la ilustración de los pasos anteriores discutidos:
Paso 1: construir ([1, 2, 4, 5, 3, 6, 7])
Paso 2:
1
/ \
/ \
construir ([2, 4, 5]) construir ([3, 6, 7])Ahora, el primer elemento (1 aquí) es raíz, luego el subarreglo después del primer elemento (que es [2,4,5,3,6,7] aquí) contiene los recorridos preordenados de los subárboles izquierdo y derecho. Y sabemos que el recorrido en preorden del subárbol izquierdo es la primera mitad, es decir, [2,4,5], y el recorrido en preorden del subárbol derecho es la segunda mitad, es decir, [3,6,7]. Ahora construya recursivamente los subárboles izquierdo y derecho.
Paso 3:
1___________|_________________
/ \
/ \
2 3
______/___________ _______\____________
/ \ / \
/ \ / \
build([4]) build([5]) build([6]) build([7])
Paso 4:
1
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure of the tree struct Node { int data; Node *left, *right; Node(int val) { data = val; left = right = NULL; } }; // Function to create a new node with // the value val Node* getNewNode(int val) { Node* newNode = new Node(val); newNode->data = val; newNode->left = newNode->right = NULL; // Return the newly created node return newNode; } // Function to create the Perfect // Binary Tree Node* buildPerfectBT_helper(int preStart, int preEnd, int pre[]) { // If preStart > preEnd return NULL if (preStart > preEnd) return NULL; // Initialize root as pre[preStart] Node* root = getNewNode(pre[preStart]); ; // If the only node is left, // then return node if (preStart == preEnd) return root; // Parameters for further recursion int leftPreStart = preStart + 1; int rightPreStart = leftPreStart + (preEnd - leftPreStart + 1) / 2; int leftPreEnd = rightPreStart - 1; int rightPreEnd = preEnd; // Recursive Call to build the // subtree of root node root->left = buildPerfectBT_helper( leftPreStart, leftPreEnd, pre); root->right = buildPerfectBT_helper( rightPreStart, rightPreEnd, pre); // Return the created root return root; } // Function to build Perfect Binary Tree Node* buildPerfectBT(int pre[], int size) { return buildPerfectBT_helper(0, size - 1, pre); } // Function to print the Inorder of // the given Tree void printInorder(Node* root) { // Base Case if (!root) return; // Left Recursive Call printInorder(root->left); // Print the data cout << root->data << " "; // Right Recursive Call printInorder(root->right); } // Driver Code int main() { int pre[] = { 1, 2, 4, 5, 3, 6, 7 }; int N = sizeof(pre) / sizeof(pre[0]); // Function Call Node* root = buildPerfectBT(pre, N); // Print Inorder Traversal cout << "\nInorder traversal of the tree: "; printInorder(root); return 0; }
Java
// Java program for the above approach public class Main { // Structure of the tree static class Node { public int data; public Node left, right; public Node(int val) { data = val; left = right = null; } } // Function to create a new node with // the value val static Node getNewNode(int val) { Node newNode = new Node(val); // Return the newly created node return newNode; } // Function to create the Perfect // Binary Tree static Node buildPerfectBT_helper(int preStart, int preEnd, int[] pre) { // If preStart > preEnd return NULL if (preStart > preEnd) return null; // Initialize root as pre[preStart] Node root = getNewNode(pre[preStart]); // If the only node is left, // then return node if (preStart == preEnd) return root; // Parameters for further recursion int leftPreStart = preStart + 1; int rightPreStart = leftPreStart + (preEnd - leftPreStart + 1) / 2; int leftPreEnd = rightPreStart - 1; int rightPreEnd = preEnd; // Recursive Call to build the // subtree of root node root.left = buildPerfectBT_helper( leftPreStart, leftPreEnd, pre); root.right = buildPerfectBT_helper( rightPreStart, rightPreEnd, pre); // Return the created root return root; } // Function to build Perfect Binary Tree static Node buildPerfectBT(int[] pre, int size) { return buildPerfectBT_helper(0, size - 1, pre); } // Function to print the Inorder of // the given Tree static void printInorder(Node root) { // Base Case if (root == null) return; // Left Recursive Call printInorder(root.left); // Print the data System.out.print(root.data + " "); // Right Recursive Call printInorder(root.right); } public static void main(String[] args) { int[] pre = { 1, 2, 4, 5, 3, 6, 7 }; int N = pre.length; // Function Call Node root = buildPerfectBT(pre, N); // Print Inorder Traversal System.out.print("Inorder traversal of the tree: "); printInorder(root); } } // This code is contributed by suresh07.
Python3
# Python3 program for the above approach # Structure of the tree class Node: def __init__(self, val): self.data = val self.left = None self.right = None # Function to create a new node with # the value val def getNewNode(val): newNode = Node(val) # Return the newly created node return newNode # Function to create the Perfect # Binary Tree def buildPerfectBT_helper(preStart, preEnd, pre): # If preStart > preEnd return NULL if (preStart > preEnd): return None # Initialize root as pre[preStart] root = getNewNode(pre[preStart]) # If the only node is left, # then return node if (preStart == preEnd): return root # Parameters for further recursion leftPreStart = preStart + 1 rightPreStart = leftPreStart + int((preEnd - leftPreStart + 1) / 2) leftPreEnd = rightPreStart - 1 rightPreEnd = preEnd # Recursive Call to build the # subtree of root node root.left = buildPerfectBT_helper(leftPreStart, leftPreEnd, pre) root.right = buildPerfectBT_helper(rightPreStart, rightPreEnd, pre) # Return the created root return root # Function to build Perfect Binary Tree def buildPerfectBT(pre, size): return buildPerfectBT_helper(0, size - 1, pre) # Function to print the Inorder of # the given Tree def printInorder(root): # Base Case if (root == None): return # Left Recursive Call printInorder(root.left) # Print the data print(root.data, "", end = "") # Right Recursive Call printInorder(root.right) pre = [ 1, 2, 4, 5, 3, 6, 7 ] N = len(pre) # Function Call root = buildPerfectBT(pre, N) # Print Inorder Traversal print("Inorder traversal of the tree: ", end = "") printInorder(root) # This code is contributed by decode2207.
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Structure of the tree class Node { public int data; public Node left, right; public Node(int val) { data = val; left = right = null; } } // Function to create a new node with // the value val static Node getNewNode(int val) { Node newNode = new Node(val); // Return the newly created node return newNode; } // Function to create the Perfect // Binary Tree static Node buildPerfectBT_helper(int preStart, int preEnd, int[] pre) { // If preStart > preEnd return NULL if (preStart > preEnd) return null; // Initialize root as pre[preStart] Node root = getNewNode(pre[preStart]); // If the only node is left, // then return node if (preStart == preEnd) return root; // Parameters for further recursion int leftPreStart = preStart + 1; int rightPreStart = leftPreStart + (preEnd - leftPreStart + 1) / 2; int leftPreEnd = rightPreStart - 1; int rightPreEnd = preEnd; // Recursive Call to build the // subtree of root node root.left = buildPerfectBT_helper( leftPreStart, leftPreEnd, pre); root.right = buildPerfectBT_helper( rightPreStart, rightPreEnd, pre); // Return the created root return root; } // Function to build Perfect Binary Tree static Node buildPerfectBT(int[] pre, int size) { return buildPerfectBT_helper(0, size - 1, pre); } // Function to print the Inorder of // the given Tree static void printInorder(Node root) { // Base Case if (root == null) return; // Left Recursive Call printInorder(root.left); // Print the data Console.Write(root.data + " "); // Right Recursive Call printInorder(root.right); } static void Main() { int[] pre = { 1, 2, 4, 5, 3, 6, 7 }; int N = pre.Length; // Function Call Node root = buildPerfectBT(pre, N); // Print Inorder Traversal Console.Write("Inorder traversal of the tree: "); printInorder(root); } } // This code is contributed by mukesh07.
Javascript
<script> // Javascript program for the above approach // Structure of the tree class Node { constructor(val) { this.left = null; this.right = null; this.data = val; } } // Function to create a new node with // the value val function getNewNode(val) { let newNode = new Node(val); // Return the newly created node return newNode; } // Function to create the Perfect // Binary Tree function buildPerfectBT_helper(preStart, preEnd, pre) { // If preStart > preEnd return NULL if (preStart > preEnd) return null; // Initialize root as pre[preStart] let root = getNewNode(pre[preStart]); // If the only node is left, // then return node if (preStart == preEnd) return root; // Parameters for further recursion let leftPreStart = preStart + 1; let rightPreStart = leftPreStart + parseInt((preEnd - leftPreStart + 1) / 2); let leftPreEnd = rightPreStart - 1; let rightPreEnd = preEnd; // Recursive Call to build the // subtree of root node root.left = buildPerfectBT_helper( leftPreStart, leftPreEnd, pre); root.right = buildPerfectBT_helper( rightPreStart, rightPreEnd, pre); // Return the created root return root; } // Function to build Perfect Binary Tree function buildPerfectBT(pre, size) { return buildPerfectBT_helper(0, size - 1, pre); } // Function to print the Inorder of // the given Tree function printInorder(root) { // Base Case if (root == null) return; // Left Recursive Call printInorder(root.left); // Print the data document.write(root.data + " "); // Right Recursive Call printInorder(root.right); } let pre = [ 1, 2, 4, 5, 3, 6, 7 ]; let N = pre.length; // Function Call let root = buildPerfectBT(pre, N); // Print Inorder Traversal document.write("Inorder traversal of the tree: "); printInorder(root); // This code is contributed by divyesh072019. </script>
Inorder traversal of the tree: 4 2 5 1 6 3 7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sourashis69 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA