Распечатать леса двоичного дерева после удаления заданных узлов

Опубликовано: 8 Января, 2022

Для двоичного дерева и массива arr [], состоящего из значений удаляемых узлов, задача состоит в том, чтобы распечатать Inorder Traversal лесов после удаления узлов.

Примеры:

Input: arr[] = {10, 5} 
 

        10
       /  
      20   30
     /     
    4   5    7

Output: 
4 20 
30 7
Input: arr[] = {5} 
 

         1
       /   
      5     6
     /       
    10       12

Output: 
10 
1 6 12

Подход: выполните следующие шаги, чтобы решить проблему:

  1. Выполните поступорядоченный обход двоичного дерева.
  2. Для каждого узла проверьте, содержит ли он значение, которое нужно удалить.
  3. Если окажется, что это правда, сохраните его дочерний элемент как корень леса. Распечатайте лес Inorder Traversal.

Below is the implementation of above approach:

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.r
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022