Eliminación en un árbol binario

Posted on by Rudeus Greyrat

Dado un árbol binario, elimine un Node de él asegurándose de que el árbol se encoja desde la parte inferior (es decir, el Node eliminado se reemplaza por el Node más inferior y más a la derecha). Esto es diferente de la eliminación de BST . Aquí no tenemos ningún orden entre los elementos, por lo que los reemplazamos con el último elemento.

Ejemplos:

Eliminar 10 en el árbol de abajo

       10
     / \         
  20 30

Salida:    
       30
     /             
 20     

Eliminar 20 debajo del árbol
       10
     / \         
 20 30
            \
            40

Salida:    
       10
         \             
         30
           \
            40   

Algoritmo:

  1. Comenzando en la raíz, busque el Node más profundo y más a la derecha en el árbol binario y el Node que desea eliminar. 
  2. Reemplace los datos del Node más profundo a la derecha con el Node que se eliminará. 
  3. Luego elimine el Node más profundo a la derecha.

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

C++

// C++ program to delete element in binary tree
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has key, pointer to left
child and a pointer to right child */
struct Node {
    int key;
    struct Node *left, *right;
};
 
/* function to create a new node of tree and
return pointer */
struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};
 
/* Inorder traversal of a binary tree*/
void inorder(struct Node* temp)
{
    if (!temp)
        return;
    inorder(temp->left);
    cout << temp->key << " ";
    inorder(temp->right);
}
 
/* function to delete the given deepest node
(d_node) in binary tree */
void deletDeepest(struct Node* root,
                  struct Node* d_node)
{
    queue<struct Node*> q;
    q.push(root);
 
    // Do level order traversal until last node
    struct Node* temp;
    while (!q.empty()) {
        temp = q.front();
        q.pop();
        if (temp == d_node) {
            temp = NULL;
            delete (d_node);
            return;
        }
        if (temp->right) {
            if (temp->right == d_node) {
                temp->right = NULL;
                delete (d_node);
                return;
            }
            else
                q.push(temp->right);
        }
 
        if (temp->left) {
            if (temp->left == d_node) {
                temp->left = NULL;
                delete (d_node);
                return;
            }
            else
                q.push(temp->left);
        }
    }
}
 
/* function to delete element in binary tree */
Node* deletion(struct Node* root, int key)
{
    if (root == NULL)
        return NULL;
 
    if (root->left == NULL && root->right == NULL) {
        if (root->key == key)
            return NULL;
        else
            return root;
    }
 
    queue<struct Node*> q;
    q.push(root);
 
    struct Node* temp;
    struct Node* key_node = NULL;
 
    // Do level order traversal to find deepest
    // node(temp) and node to be deleted (key_node)
    while (!q.empty()) {
        temp = q.front();
        q.pop();
 
        if (temp->key == key)
            key_node = temp;
 
        if (temp->left)
            q.push(temp->left);
 
        if (temp->right)
            q.push(temp->right);
    }
 
    if (key_node != NULL) {
        int x = temp->key;
        deletDeepest(root, temp);
        key_node->key = x;
    }
    return root;
}
 
// Driver code
int main()
{
    struct Node* root = newNode(10);
    root->left = newNode(11);
    root->left->left = newNode(7);
    root->left->right = newNode(12);
    root->right = newNode(9);
    root->right->left = newNode(15);
    root->right->right = newNode(8);
 
    cout << "Inorder traversal before deletion : ";
    inorder(root);
 
    int key = 11;
    root = deletion(root, key);
 
    cout << endl;
    cout << "Inorder traversal after deletion : ";
    inorder(root);
 
    return 0;
}

Java

// Java program to delete element
// in binary tree
import java.util.LinkedList;
import java.util.Queue;
 
class GFG{
     
// A binary tree node has key, pointer to
// left child and a pointer to right child
static class Node
{
    int key;
    Node left, right;
     
    // Constructor
    Node(int key)
    {
        this.key = key;
        left = null;
        right = null;
    }
}
 
static Node root;
static Node temp = root;
 
// Inorder traversal of a binary tree
static void inorder(Node temp)
{
    if (temp == null)
        return;
 
    inorder(temp.left);
    System.out.print(temp.key + " ");
    inorder(temp.right);
}
 
// Function to delete deepest
// element in binary tree
static void deleteDeepest(Node root,
                          Node delNode)
{
    Queue<Node> q = new LinkedList<Node>();
    q.add(root);
     
    Node temp = null;
     
    // Do level order traversal until last node
    while (!q.isEmpty())
    {
        temp = q.peek();
        q.remove();
         
        if (temp == delNode)
        {
            temp = null;
            return;
             
        }
        if (temp.right!=null)
        {
            if (temp.right == delNode)
            {
                temp.right = null;
                return;
        }
        else
            q.add(temp.right);
    }
 
    if (temp.left != null)
    {
        if (temp.left == delNode)
        {
            temp.left = null;
            return;
        }
        else
            q.add(temp.left);
    }
}
}
 
// Function to delete given element
// in binary tree
static void delete(Node root, int key)
{
    if (root == null)
        return;
         
    if (root.left == null &&
       root.right == null)
    {
        if (root.key == key)
        {
              root=null;
              return;
        }
        else
            return;
    }
     
    Queue<Node> q = new LinkedList<Node>();
    q.add(root);
    Node temp = null, keyNode = null;
     
    // Do level order traversal until
    // we find key and last node.
    while (!q.isEmpty())
    {
        temp = q.peek();
        q.remove();
         
        if (temp.key == key)
            keyNode = temp;
 
        if (temp.left != null)
            q.add(temp.left);
 
        if (temp.right != null)
            q.add(temp.right);
    }
 
    if (keyNode != null)
    {
        int x = temp.key;
        deleteDeepest(root, temp);
        keyNode.key = x;
    }
}
 
// Driver code
public static void main(String args[])
{
    root = new Node(10);
    root.left = new Node(11);
    root.left.left = new Node(7);
    root.left.right = new Node(12);
    root.right = new Node(9);
    root.right.left = new Node(15);
    root.right.right = new Node(8);
 
    System.out.print("Inorder traversal " +
                     "before deletion:");
    inorder(root);
 
    int key = 11;
    delete(root, key);
 
    System.out.print("\nInorder traversal " +
                     "after deletion:");
    inorder(root);
}
}
 
// This code is contributed by Ravi Kant Verma

Python3

# Python3 program to illustrate deletion in a Binary Tree
  
# class to create a node with data, left child and right child.
class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
  
# Inorder traversal of a binary tree
def inorder(temp):
    if(not temp):
        return
    inorder(temp.left)
    print(temp.data, end = " ")
    inorder(temp.right)
  
# function to delete the given deepest node (d_node) in binary tree
def deleteDeepest(root,d_node):
    q = []
    q.append(root)
    while(len(q)):
        temp = q.pop(0)
        if temp is d_node:
            temp = None
            return
        if temp.right:
            if temp.right is d_node:
                temp.right = None
                return
            else:
                q.append(temp.right)
        if temp.left:
            if temp.left is d_node:
                temp.left = None
                return
            else:
                q.append(temp.left)
  
# function to delete element in binary tree
def deletion(root, key):
    if root == None :
        return None
    if root.left == None and root.right == None:
        if root.key == key :
            return None
        else :
            return root
    key_node = None
    q = []
    q.append(root)
    temp = None
    while(len(q)):
        temp = q.pop(0)
        if temp.data == key:
            key_node = temp
        if temp.left:
            q.append(temp.left)
        if temp.right:
            q.append(temp.right)
    if key_node :
        x = temp.data
        deleteDeepest(root,temp)
        key_node.data = x
    return root
  
# Driver code
if __name__=='__main__':
    root = Node(10)
    root.left = Node(11)
    root.left.left = Node(7)
    root.left.right = Node(12)
    root.right = Node(9)
    root.right.left = Node(15)
    root.right.right = Node(8)
    print("The tree before the deletion:")
    inorder(root)
    key = 11
    root = deletion(root, key)
    print()
    print("The tree after the deletion;")
    inorder(root)
      
# This code is contributed by Monika Anandan

C#

// C# program to delete element
// in binary tree
 
using System;
using System.Collections.Generic;
 
class GFG {
 
    // A binary tree node has key, pointer to
    // left child and a pointer to right child
    public class Node {
        public int key;
        public Node left, right;
 
        // Constructor
        public Node(int key)
        {
            this.key = key;
            left = null;
            right = null;
        }
    }
 
    static Node root;
 
    // Inorder traversal of a binary tree
     static void inorder(Node temp)
    {
        if (temp == null)
            return;
 
        inorder(temp.left);
        Console.Write(temp.key + " ");
        inorder(temp.right);
    }
 
    // Function to delete deepest
    // element in binary tree
    static void deleteDeepest(Node root, Node delNode)
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
 
        Node temp = null;
 
        // Do level order traversal until last node
        while (q.Count != 0) {
            temp = q.Peek();
            q.Dequeue();
 
            if (temp == delNode) {
                temp = null;
                return;
            }
            if (temp.right != null) {
                if (temp.right == delNode) {
                    temp.right = null;
                    return;
                }
 
                else
                    q.Enqueue(temp.right);
            }
 
            if (temp.left != null) {
                if (temp.left == delNode) {
                    temp.left = null;
                    return;
                }
                else
                    q.Enqueue(temp.left);
            }
        }
    }
 
    // Function to delete given element
    // in binary tree
    static void delete(Node root, int key)
    {
        if (root == null)
            return;
 
        if (root.left == null && root.right == null) {
            if (root.key == key) {
                root = null;
                return;
            }
            else
                return;
        }
 
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
        Node temp = null, keyNode = null;
 
        // Do level order traversal until
        // we find key and last node.
        while (q.Count != 0) {
            temp = q.Peek();
            q.Dequeue();
 
            if (temp.key == key)
                keyNode = temp;
 
            if (temp.left != null)
                q.Enqueue(temp.left);
 
            if (temp.right != null)
                q.Enqueue(temp.right);
        }
 
        if (keyNode != null) {
            int x = temp.key;
            deleteDeepest(root, temp);
            keyNode.key = x;
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        root = new Node(10);
        root.left = new Node(11);
        root.left.left = new Node(7);
        root.left.right = new Node(12);
        root.right = new Node(9);
        root.right.left = new Node(15);
        root.right.right = new Node(8);
 
        Console.Write("Inorder traversal "
                      + "before deletion: ");
        inorder(root);
 
        int key = 11;
        delete(root, key);
 
        Console.Write("\nInorder traversal "
                      + "after deletion: ");
        inorder(root);
    }
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Javascript

<script>
    // Javascript program to delete element in binary tree
     
    class Node
    {
        constructor(key) {
           this.left = null;
           this.right = null;
           this.key = key;
        }
    }
     
    let root;
    let temp = root;
 
    // Inorder traversal of a binary tree
    function inorder(temp)
    {
        if (temp == null)
            return;
 
        inorder(temp.left);
        document.write(temp.key + " ");
        inorder(temp.right);
    }
 
    // Function to delete deepest
    // element in binary tree
    function deleteDeepest(root, delNode)
    {
        let q = [];
        q.push(root);
 
        let temp = null;
 
        // Do level order traversal until last node
        while (q.length > 0)
        {
            temp = q[0];
            q.shift();
 
            if (temp == delNode)
            {
                temp = null;
                return;
 
            }
            if (temp.right!=null)
            {
                if (temp.right == delNode)
                {
                    temp.right = null;
                    return;
            }
            else
                q.push(temp.right);
        }
 
        if (temp.left != null)
        {
            if (temp.left == delNode)
            {
                temp.left = null;
                return;
            }
            else
                q.push(temp.left);
        }
    }
    }
 
    // Function to delete given element
    // in binary tree
    function Delete(root, key)
    {
        if (root == null)
            return;
 
        if (root.left == null &&
           root.right == null)
        {
            if (root.key == key)
            {
                  root=null;
                  return;
            }
            else
                return;
        }
 
        let q = [];
        q.push(root);
        let temp = null, keyNode = null;
 
        // Do level order traversal until
        // we find key and last node.
        while (q.length > 0)
        {
            temp = q[0];
            q.shift();
 
            if (temp.key == key)
                keyNode = temp;
 
            if (temp.left != null)
                q.push(temp.left);
 
            if (temp.right != null)
                q.push(temp.right);
        }
 
        if (keyNode != null)
        {
            let x = temp.key;
            deleteDeepest(root, temp);
            keyNode.key = x;
        }
    }
     
    root = new Node(10);
    root.left = new Node(11);
    root.left.left = new Node(7);
    root.left.right = new Node(12);
    root.right = new Node(9);
    root.right.left = new Node(15);
    root.right.right = new Node(8);
  
    document.write("Inorder traversal " +
                     "before deletion : ");
    inorder(root);
  
    let key = 11;
    Delete(root, key);
  
    document.write("</br>" + "Inorder traversal " +
                     "after deletion : ");
    inorder(root);
 
</script>
Producción

Inorder traversal before deletion : 7 11 12 10 15 9 8 
Inorder traversal after deletion : 7 8 12 10 15 9

Complejidad de tiempo: O(n) donde n no es ningún número de Nodes
Espacio auxiliar: O(n) tamaño de la cola

Nota: También podemos reemplazar los datos del Node que se eliminarán con cualquier Node cuyo hijo izquierdo y derecho apunte a NULL, pero solo usamos el Node más profundo para mantener el equilibrio de un árbol binario.

Nota importante : el código anterior no funcionará si el Node que se eliminará es el Node más profundo porque después de que la función deleteDeepest(root, temp) complete la ejecución, el key_node se elimina (ya que aquí key_node es igual a la temperatura ) y después de lo cual se reemplaza Los datos de key_node con los datos del Node más profundo (datos de temp ) arrojan un error de tiempo de ejecución.

Producción

Para evitar el error anterior y también para evitar hacer BFS dos veces (la primera iteración mientras se busca el Node más profundo a la derecha y la segunda mientras se elimina el Node más profundo a la derecha), podemos almacenar el Node principal durante el primer recorrido y después de establecer los datos del Node más profundo a la derecha en el Node necesitaba eliminarse, elimine fácilmente el Node más profundo más a la derecha.

Implementación:

C++

// C++ program to delete element in binary tree
#include <bits/stdc++.h>
using namespace std;
  
/* A binary tree node has key, pointer to left
child and a pointer to right child */
struct Node {
    int data;
    struct Node *left, *right;
};
  
/* function to create a new node of tree and
return pointer */
struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->data = key;
    temp->left = temp->right = NULL;
    return temp;
};
  
/* Inorder traversal of a binary tree*/
void inorder(struct Node* temp)
{
    if (!temp)
        return;
    inorder(temp->left);
    cout << temp->data << " ";
    inorder(temp->right);
}
  
struct Node* deletion(struct Node* root, int key)
{
    if(root==NULL)
        return NULL;
    if(root->left==NULL && root->right==NULL)
    {
        if(root->data==key)
            return NULL;
        else
            return root;
    }
    Node* key_node=NULL;
    Node* temp;
    Node* last;
    queue<Node*> q;
    q.push(root);
    // Do level order traversal to find deepest
    // node(temp), node to be deleted (key_node)
      // and parent of deepest node(last)
    while(!q.empty())
    {
        temp=q.front();
        q.pop();
        if(temp->data==key)
            key_node=temp;
        if(temp->left)
        {
            last=temp;//storing the parent node
            q.push(temp->left);
        }
        if(temp->right)
        {
            last=temp;// storing the parent node
            q.push(temp->right);
        }
             
         
    }
      if(key_node!=NULL)
    {
        key_node->data=temp->data;//replacing key_node's data to deepest node's data
        if(last->right==temp)
            last->right=NULL;
        else
            last->left=NULL;
        delete(temp);
     }
    return root;
}
  // Driver code
int main()
{
    struct Node* root = newNode(9);
    root->left = newNode(2);
    root->left->left = newNode(4);
    root->left->right = newNode(7);
    root->right = newNode(8);
     
  
    cout << "Inorder traversal before deletion : ";
    inorder(root);
  
    int key = 7;
    root = deletion(root, key);
  
    cout << endl;
    cout << "Inorder traversal after deletion : ";
    inorder(root);
  
    return 0;
}

C#

// This code is designed to delete a node in a Binary Tree
 
using System;
 
namespace BinaryTreeDeletion {
 
public class TreeNode {
    public int Data;
    public TreeNode leftNode;
    public TreeNode rightNode;
}
public class BinaryTreeOperations {
    TreeNode rootNode;
 
    TreeNode parentNode;
 
    int NodeToDelete;
    int NodeToBeReplaceWith;
    bool NodeValueReplaced = false;
 
    // Driver code
    public static void Main()
    {
        BinaryTreeOperations obj
            = new BinaryTreeOperations();
        obj.AddNode(7);
        obj.AddNode(2);
        obj.AddNode(3);
        obj.AddNode(1);
        obj.AddNode(10);
        obj.AddNode(5);
        obj.AddNode(8);
 
        Console.WriteLine(
            "Inorder Traversal before Deletion : ");
        obj.PrintInorderTraversalData(obj.rootNode);
 
        obj.DeleteNode(5);
 
        Console.WriteLine("");
        Console.WriteLine(
            "Inorder Traversal after Deletion : ");
        obj.PrintInorderTraversalData(obj.rootNode);
    }
 
    void PrintInorderTraversalData(TreeNode Node)
    {
        if (Node != null) {
            PrintInorderTraversalData(Node.leftNode);
            Console.Write(Node.Data + " ");
            PrintInorderTraversalData(Node.rightNode);
        }
    }
 
    public void AddNode(int Value)
    {
        TreeNode beforeNode = null;
        TreeNode afterNode = this.rootNode;
        while (afterNode != null) {
            beforeNode = afterNode;
            if (Value < afterNode.Data)
                afterNode = afterNode.leftNode;
            else if (Value > afterNode.Data)
                afterNode = afterNode.rightNode;
            else
                return;
        }
 
        TreeNode newNode = new TreeNode();
        newNode.Data = Value;
 
        if (this.rootNode == null)
            rootNode = newNode;
        else {
            if (Value < beforeNode.Data) {
                beforeNode.leftNode = newNode;
            }
            else {
                beforeNode.rightNode = newNode;
            }
        }
    }
 
    void DeleteNode(int Value)
    {
        if (rootNode == null) {
            return;
        }
        NodeToBeReplaceWith = FindDeepestNode(rootNode);
        NodeToDelete = Value;
        Search(rootNode);
    }
 
    int FindDeepestNode(TreeNode rootnode)
    {
        if (rootnode.leftNode == null
            && rootnode.rightNode == null) {
            int deepestVal = rootnode.Data;
            parentNode.leftNode = null;
            parentNode.rightNode = null;
            return deepestVal;
        }
 
        parentNode = rootnode;
 
        return FindDeepestNode(rootnode.rightNode != null
                                   ? rootnode.rightNode
                                   : rootnode.leftNode);
    }
 
    void Search(TreeNode node)
    {
        if (!NodeValueReplaced) {
            SearchAndReplace(node.leftNode);
        }
        if (!NodeValueReplaced) {
            SearchAndReplace(node.rightNode);
        }
    }
 
    void SearchAndReplace(TreeNode rootnode)
    {
        if (rootnode == null) {
            return;
        }
        if (rootnode.Data == NodeToDelete) {
            rootnode.Data = NodeToBeReplaceWith;
            NodeValueReplaced = true;
            return;
        }
        if (!NodeValueReplaced) {
            SearchAndReplace(rootnode.leftNode);
        }
 
        if (!NodeValueReplaced) {
            SearchAndReplace(rootnode.rightNode);
        }
    }
}
}
 
// This code is contributed by Prakher Mehrotra
Producción

Inorder traversal before deletion : 4 2 7 9 8 
Inorder traversal after deletion : 4 2 9 8

Complejidad de tiempo: O(n) donde n no es ningún número de Nodes
Espacio auxiliar: O(n) tamaño de la cola

Este artículo es una contribución de Yash Singla y Peehoo Jain . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

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

Deja una respuesta

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