Imprima los bosques de un árbol binario después de eliminar los Nodes dados

Posted on by Rudeus Greyrat

Dado un árbol binario y una array arr[] que consta de valores de Nodes que se eliminarán, la tarea es imprimir el recorrido en orden de los bosques después de eliminar los Nodes.

Ejemplos:

Entrada: arr[] = {10, 5} 
 

        10
       /  \
      20   30
     / \    \
    4   5    7

Salida: 
4 20 
30 7
Entrada: arr[] = {5} 
 

         1
       /   \
      5     6
     /       \
    10       12

Salida: 
10 
1 6 12

Enfoque: siga los pasos a continuación para resolver el problema:

  1. Realice el recorrido posorden del árbol binario.
  2. Para cada Node, verifique si contiene el valor que se eliminará.
  3. Si se determina que es cierto, almacena a su hijo como la raíz del bosque. Imprimir el bosque por Inorder Traversal .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stores the nodes to be deleted
unordered_map<int, bool> mp;
 
// Structure of a Tree node
struct Node {
    int key;
    struct Node *left, *right;
};
 
// Function to create a new node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
 
// Function to check whether the node
// needs to be deleted or not
bool deleteNode(int nodeVal)
{
    return mp.find(nodeVal) != mp.end();
}
 
// Function to perform tree pruning
// by performing post order traversal
Node* treePruning(Node* root, vector<Node*>& result)
{
    if (root == NULL)
        return NULL;
 
    root->left = treePruning(root->left, result);
    root->right = treePruning(root->right, result);
 
    // If the node needs to be deleted
    if (deleteNode(root->key)) {
 
        // Store the its subtree
        if (root->left) {
            result.push_back(root->left);
        }
        if (root->right) {
            result.push_back(root->right);
        }
        return NULL;
    }
 
    return root;
}
 
// Perform Inorder Traversal
void printInorderTree(Node* root)
{
    if (root == NULL)
        return;
 
    printInorderTree(root->left);
    cout << root->key << " ";
    printInorderTree(root->right);
}
 
// Function to print the forests
void printForests(Node* root, int arr[], int n)
{
    for (int i = 0; i < n; i++) {
        mp[arr[i]] = true;
    }
 
    // Stores the remaining nodes
    vector<Node*> result;
 
    if (treePruning(root, result))
        result.push_back(root);
 
    // Print the inorder traversal of Forests
    for (int i = 0; i < result.size(); i++) {
        printInorderTree(result[i]);
        cout << endl;
    }
}
 
// Driver Code
int main()
{
 
    Node* root = newNode(1);
    root->left = newNode(12);
    root->right = newNode(13);
    root->right->left = newNode(14);
    root->right->right = newNode(15);
    root->right->left->left = newNode(21);
    root->right->left->right = newNode(22);
    root->right->right->left = newNode(23);
    root->right->right->right = newNode(24);
 
    int arr[] = { 14, 23, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printForests(root, arr, n);
}

Java

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
// Stores the nodes to be deleted
static HashMap<Integer,
                 Boolean> mp  = new HashMap<>();
 
// Structure of a Tree node
static class Node
{
    int key;
    Node left, right;
};
 
// Function to create a new node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return (temp);
}
 
// Function to check whether the node
// needs to be deleted or not
static boolean deleteNode(int nodeVal)
{
    return mp.containsKey(nodeVal);
}
 
// Function to perform tree pruning
// by performing post order traversal
static Node treePruning(Node root,
                        Vector<Node> result)
{
    if (root == null)
        return null;
 
    root.left = treePruning(root.left, result);
    root.right = treePruning(root.right, result);
 
    // If the node needs to be deleted
    if (deleteNode(root.key))
    {
 
        // Store the its subtree
        if (root.left != null)
        {
            result.add(root.left);
        }
        if (root.right != null)
        {
            result.add(root.right);
        }
        return null;
    }
    return root;
}
 
// Perform Inorder Traversal
static void printInorderTree(Node root)
{
    if (root == null)
        return;
 
    printInorderTree(root.left);
    System.out.print(root.key + " ");
    printInorderTree(root.right);
}
 
// Function to print the forests
static void printForests(Node root,
                         int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        mp.put(arr[i], true);
    }
 
    // Stores the remaining nodes
    Vector<Node> result  = new Vector<>();
 
    if (treePruning(root, result) != null)
        result.add(root);
 
    // Print the inorder traversal of Forests
    for (int i = 0; i < result.size(); i++)
    {
        printInorderTree(result.get(i));
        System.out.println();
    }
}
 
// Driver Code
public static void main(String[] args)
{
 
    Node root = newNode(1);
    root.left = newNode(12);
    root.right = newNode(13);
    root.right.left = newNode(14);
    root.right.right = newNode(15);
    root.right.left.left = newNode(21);
    root.right.left.right = newNode(22);
    root.right.right.left = newNode(23);
    root.right.right.right = newNode(24);
 
    int arr[] = { 14, 23, 1 };
    int n = arr.length;
    printForests(root, arr, n);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 Program to implement
# the above approach
  
# Stores the nodes to be deleted
mp = dict()
  
# Structure of a Tree node
class Node:
     
    def __init__(self, key):
         
        self.key = key
        self.left = None
        self.right = None
     
# Function to create a new node
def newNode(key):
 
    temp = Node(key)
    return temp
  
# Function to check whether the node
# needs to be deleted or not
def deleteNode(nodeVal):
 
    if nodeVal in mp:
        return True
    else:
        return False
 
# Function to perform tree pruning
# by performing post order traversal
def treePruning( root, result):
 
    if (root == None):
        return None;
  
    root.left = treePruning(root.left, result);
    root.right = treePruning(root.right, result);
  
    # If the node needs to be deleted
    if (deleteNode(root.key)):
  
        # Store the its subtree
        if (root.left):
            result.append(root.left);
         
        if (root.right):
            result.append(root.right);
         
        return None;
     
    return root;
 
# Perform Inorder Traversal
def printInorderTree(root):
 
    if (root == None):
        return;
  
    printInorderTree(root.left);
    print(root.key, end=' ')
    printInorderTree(root.right);
  
# Function to print the forests
def printForests(root, arr, n):
    for i in range(n):   
        mp[arr[i]] = True;
     
    # Stores the remaining nodes
    result = []
  
    if (treePruning(root, result)):
        result.append(root);
  
    # Print the inorder traversal of Forests
    for i in range(len(result)):
     
        printInorderTree(result[i]);
        print()
         
# Driver Code
if __name__=='__main__':
  
    root = newNode(1);
    root.left = newNode(12);
    root.right = newNode(13);
    root.right.left = newNode(14);
    root.right.right = newNode(15);
    root.right.left.left = newNode(21);
    root.right.left.right = newNode(22);
    root.right.right.left = newNode(23);
    root.right.right.right = newNode(24);
  
    arr = [ 14, 23, 1 ]
    n = len(arr)
    printForests(root, arr, n);
 
# This code is contributed by rutvik_56

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Stores the nodes to be deleted
static Dictionary<int,
                  Boolean> mp = new Dictionary<int,
                                               Boolean>();
 
// Structure of a Tree node
class Node
{
    public int key;
    public Node left, right;
};
 
// Function to create a new node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return (temp);
}
 
// Function to check whether the node
// needs to be deleted or not
static bool deleteNode(int nodeVal)
{
    return mp.ContainsKey(nodeVal);
}
 
// Function to perform tree pruning
// by performing post order traversal
static Node treePruning(Node root,
                        List<Node> result)
{
    if (root == null)
        return null;
 
    root.left = treePruning(root.left, result);
    root.right = treePruning(root.right, result);
 
    // If the node needs to be deleted
    if (deleteNode(root.key))
    {
 
        // Store the its subtree
        if (root.left != null)
        {
            result.Add(root.left);
        }
        if (root.right != null)
        {
            result.Add(root.right);
        }
        return null;
    }
    return root;
}
 
// Perform Inorder Traversal
static void printInorderTree(Node root)
{
    if (root == null)
        return;
 
    printInorderTree(root.left);
    Console.Write(root.key + " ");
    printInorderTree(root.right);
}
 
// Function to print the forests
static void printForests(Node root,
                         int []arr, int n)
{
    for(int i = 0; i < n; i++)
    {
        mp.Add(arr[i], true);
    }
 
    // Stores the remaining nodes
    List<Node> result = new List<Node>();
 
    if (treePruning(root, result) != null)
        result.Add(root);
 
    // Print the inorder traversal of Forests
    for(int i = 0; i < result.Count; i++)
    {
        printInorderTree(result[i]);
        Console.WriteLine();
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    Node root = newNode(1);
    root.left = newNode(12);
    root.right = newNode(13);
    root.right.left = newNode(14);
    root.right.right = newNode(15);
    root.right.left.left = newNode(21);
    root.right.left.right = newNode(22);
    root.right.right.left = newNode(23);
    root.right.right.right = newNode(24);
 
    int []arr = { 14, 23, 1 };
    int n = arr.Length;
    printForests(root, arr, n);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
    // Javascript Program to implement the above approach
     
    // Stores the nodes to be deleted
    let mp  = new Map();
 
    // Structure of a Tree node
    class Node
    {
        constructor(key) {
           this.left = this.right = null;
           this.key = key;
        }
    }
     
    // Function to create a new node
    function newNode(key)
    {
        let temp = new Node(key);
        return (temp);
    }
 
    // Function to check whether the node
    // needs to be deleted or not
    function deleteNode(nodeVal)
    {
        return mp.has(nodeVal);
    }
 
    // Function to perform tree pruning
    // by performing post order traversal
    function treePruning(root, result)
    {
        if (root == null)
            return null;
 
        root.left = treePruning(root.left, result);
        root.right = treePruning(root.right, result);
 
        // If the node needs to be deleted
        if (deleteNode(root.key))
        {
 
            // Store the its subtree
            if (root.left != null)
            {
                result.push(root.left);
            }
            if (root.right != null)
            {
                result.push(root.right);
            }
            return null;
        }
        return root;
    }
 
    // Perform Inorder Traversal
    function printInorderTree(root)
    {
        if (root == null)
            return;
 
        printInorderTree(root.left);
        document.write(root.key + " ");
        printInorderTree(root.right);
    }
 
    // Function to print the forests
    function printForests(root, arr, n)
    {
        for (let i = 0; i < n; i++)
        {
            mp.set(arr[i], true);
        }
 
        // Stores the remaining nodes
        let result  = [];
 
        if (treePruning(root, result) != null)
            result.push(root);
 
        // Print the inorder traversal of Forests
        for (let i = 0; i < result.length; i++)
        {
            printInorderTree(result[i]);
            document.write("</br>");
        }
    }
     
    let root = newNode(1);
    root.left = newNode(12);
    root.right = newNode(13);
    root.right.left = newNode(14);
    root.right.right = newNode(15);
    root.right.left.left = newNode(21);
    root.right.left.right = newNode(22);
    root.right.right.left = newNode(23);
    root.right.right.right = newNode(24);
  
    let arr = [ 14, 23, 1 ];
    let n = arr.length;
    printForests(root, arr, n);
 
</script>
Producción: 

21 
22 
12 
13 15 24

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por arpit7714 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 *