Construya un árbol binario perfecto a partir de un recorrido de pedido anticipado

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 7

Entrada: 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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *