Рубрики

Удалить последний листовой узел в двоичном дереве

Для заданного двоичного дерева задача состоит в том, чтобы найти и УДАЛИТЬ последний конечный узел.

Конечный узел — это узел без дочерних элементов. Последним конечным узлом будет узел, который был пройден последним в последовательности во время обхода уровня порядка . Задача состоит в том, чтобы идентифицировать этот последний посещенный узел и удалить этот конкретный узел.

Примеры:

 
Input: 
Given Tree is: 
          6
       /     \
      5       4
    /   \       \
   1     2       5 

Level Order Traversal is: 6 5 4 1 2 5
Output: 
After deleting the last node (5),
the tree would look like as follows. 

          6
       /     \
      5       4
    /   \  
   1     2 
Level Order Traversal is: 6 5 4 1 2

Input: 
Given tree is: 
           1
        /     \
      3        10
    /   \     /   \
   2     15   4     5                        
        /                    
       1    
Level Order Traversal is: 1 3 10 2 15 4 5 1
Output: 
After deleting the last node (1),
the tree would look like as follows.

           1
        /     \
      3        10
    /   \     /   \
   2     15   4     5                        

Level Order Traversal is: 1 3 10 2 15 4 5

Эта проблема немного отличается от удаления конечного узла со значением как X, в котором мы сразу получаем значение последнего конечного узла (X), который должен быть удален, на основании которого мы выполняем проверки и помечаем родительский узел как нулевой для его удаления.

Этот подход идентифицирует последний существующий листовой узел на последнем уровне дерева и удаляет его.

Подход 1: Обход узлов последнего уровня и отслеживание родительского и пройденного узла.

Этот подход будет проходить через каждый узел, пока мы не достигнем последнего уровня данного двоичного дерева. Во время обхода мы отслеживаем последний пройденный узел и его Parent.

После завершения обхода проверьте, есть ли у родителя Right Child, если да, установите его в NULL. Если нет, установите левый указатель на NULL

Ниже приведена реализация подхода:

Джава

// Java реализация подхода

public class DeleteLastNode {

  

    // Tree Node

    static class Node {

  

        Node left, right;

        int data;

  

        Node(int data)

        {

            this.data = data;

        }

    }

  

    // Способ выполнения обхода заказа

    public void inorder(Node root)

    {

        if (root == null)

            return;

  

        inorder(root.left);

        System.out.print(root.data + " ");

        inorder(root.right);

    }

  

    // Для отслеживания последней обработки

    // узел родительский и сам узел.

    public static Node lastNode;

    public static Node parentOfLastNode;

  

    // Метод получения высоты дерева

    public int height(Node root)

    {

  

        if (root == null)

            return 0;

  

        int lheight = height(root.left) + 1;

        int rheight = height(root.right) + 1;

  

        return Math.max(lheight, rheight);

    }

  

    // Метод для удаления последнего конечного узла

    public void deleteLastNode(Node root)

    {

  

        int levelOfLastNode = height(root);

  

        // Получить все узлы на последнем уровне

        getLastNodeAndItsParent(root,

                                levelOfLastNode,

                                null);

  

        if (lastNode != null

            && parentOfLastNode != null) {

  

            if (parentOfLastNode.right != null)

                parentOfLastNode.right = null;

            else

                parentOfLastNode.left = null;

        }

        else

            System.out.println("Empty Tree");

    }

  

    // Способ слежения за родителями

    // каждого узла

    public void getLastNodeAndItsParent(Node root,

                                        int level,

                                        Node parent)

    {

  

        if (root == null)

            return;

  

        // Последний обработанный узел в

        // Уровень Order Traversal должен

        // быть удаляемым узлом.

        // Это будет хранить последний

        // обработанный узел и его родитель.

        if (level == 1) {

            lastNode = root;

            parentOfLastNode = parent;

        }

        getLastNodeAndItsParent(root.left,

                                level - 1,

                                root);

        getLastNodeAndItsParent(root.right,

                                level - 1,

                                root);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

  

        Node root = new Node(6);

        root.left = new Node(5);

        root.right = new Node(4);

        root.left.left = new Node(1);

        root.left.right = new Node(2);

        root.right.right = new Node(5);

  

        DeleteLastNode deleteLastNode = new DeleteLastNode();

  

        System.out.println("Inorder traversal "

                           + "before deletion "

                           + "of last node : ");

  

        deleteLastNode.inorder(root);

  

        deleteLastNode.deleteLastNode(root);

  

        System.out.println("\nInorder traversal "

                           + "after deletion of "

                           + "last node : ");

        deleteLastNode.inorder(root);

    }

}

C #

// C # реализация вышеуказанного подхода

using System;

      

class GFG

{

  

    // Tree Node

    public class Node

    {

        public Node left, right;

        public int data;

  

        public Node(int data)

        {

            this.data = data;

        }

    }

  

    // Способ выполнения обхода заказа

    public void inorder(Node root)

    {

        if (root == null)

            return;

  

        inorder(root.left);

        Console.Write(root.data + " ");

        inorder(root.right);

    }

  

    // Для отслеживания последней обработки

    // узел родительский и сам узел.

    public static Node lastNode;

    public static Node parentOfLastNode;

  

    // Метод получения высоты дерева

    public int height(Node root)

    {

        if (root == null)

            return 0;

  

        int lheight = height(root.left) + 1;

        int rheight = height(root.right) + 1;

  

        return Math.Max(lheight, rheight);

    }

  

    // Метод для удаления последнего конечного узла

    public void deleteLastNode(Node root)

    {

        int levelOfLastNode = height(root);

  

        // Получить все узлы на последнем уровне

        getLastNodeAndItsParent(root,

                                levelOfLastNode,

                                null);

  

        if (lastNode != null && 

            parentOfLastNode != null)

        {

            if (parentOfLastNode.right != null)

                parentOfLastNode.right = null;

            else

                parentOfLastNode.left = null;

        }

        else

            Console.WriteLine("Empty Tree");

    }

  

    // Способ слежения за родителями

    // каждого узла

    public void getLastNodeAndItsParent(Node root,

                                        int level,

                                        Node parent)

    {

        if (root == null)

            return;

  

        // Последний обработанный узел в

        // Уровень Order Traversal должен

        // быть удаляемым узлом.

        // Это будет хранить последний

        // обработанный узел и его родитель.

        if (level == 1)

        {

            lastNode = root;

            parentOfLastNode = parent;

        }

        getLastNodeAndItsParent(root.left,

                                level - 1,

                                root);

        getLastNodeAndItsParent(root.right,

                                level - 1,

                                root);

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        Node root = new Node(6);

        root.left = new Node(5);

        root.right = new Node(4);

        root.left.left = new Node(1);

        root.left.right = new Node(2);

        root.right.right = new Node(5);

  

        GFG deleteLastNode = new GFG();

  

        Console.WriteLine("Inorder traversal "

                            "before deletion "

                             "of last node : ");

  

        deleteLastNode.inorder(root);

  

        deleteLastNode.deleteLastNode(root);

  

        Console.WriteLine("\nInorder traversal "

                            "after deletion of "

                                  "last node : ");

        deleteLastNode.inorder(root);

    }

}

  
// Этот код предоставлен 29AjayKumar

Выход:

Inorder traversal before deletion of last node : 
1 5 2 6 4 5 
Inorder traversal after deletion of last node : 
1 5 2 6 4

Сложность времени:
Поскольку каждый узел будет пройден один раз, затраченное время будет линейным по отношению к числу узлов в данном дереве.

Подход 2: Выполнение обхода уровня по заданному двоичному дереву с использованием очереди и отслеживания родительского и последнего пройденного узла.

Это нерекурсивный способ достижения вышеуказанного подхода 1. Мы выполняем обход уровня заказа, используя очередь и отслеживая каждый посещенный узел и его родительский элемент. Последний посещенный узел будет последним узлом, который должен быть удален.

Ниже приведена реализация подхода:

Джава

// реализация Java

import java.util.LinkedList;

import java.util.Queue;

  

  

public class DeleteLastNode {

      

    // Tree Node

    static class Node {

  

        Node left, right;

        int data;

  

        Node(int data)

        {

            this.data = data;

        }

    

  

    // Функция для обхода дерева по порядку

    public void inorder(Node root)

    {

        if (root == null)

            return;

  

        inorder(root.left);

        System.out.print(root.data + " ");

        inorder(root.right);

    }

  

    // Чтобы отслеживать последние

    // обработанные узлы родителя

    // и сам узел.

    public static Node lastLevelLevelOrder;

    public static Node parentOfLastNode;

  

    // Метод для удаления последнего узла

    // из дерева

    public void deleteLastNode(Node root)

    {

  

        // Если дерево пусто, оно

        // вернется без

        // любое удаление

        if (root == null)

            return;

  

        // Очередь будет нужна

        // поддерживать порядок уровня

        // обход узлов

        Queue<Node> queue = new LinkedList<>();

  

        queue.offer(root);

  

        // Обход будет

        // продолжаем до всех

        // узлы пройдены один раз

        while (!queue.isEmpty()) {

  

            Node temp = queue.poll();

  

            // Если остался ребенок

            if (temp.left != null) {

                queue.offer(temp.left);

  

                // Для каждого пройденного узла

                // мы бы проверили, если это

                // листовой узел, проверяя, если

                // текущий узел имеет потомков

                if (temp.left.left == null

                    && temp.left.right == null) {

  

                    // Для каждого конечного узла

                    // столкнулись, мы бы

                    // сохранить не как

                    // "Узел ранее посещенных листьев.

                    lastLevelLevelOrder = temp.left;

                    parentOfLastNode = temp;

                }

            }

  

            if (temp.right != null) {

                queue.offer(temp.right);

  

                if (temp.right.left == null

                    && temp.right.right == null) {

  

                    // Для каждого конечного узла

                    // столкнулись, мы бы

                    // сохранить не как

                    // "Узел ранее посещенных листьев.

                    lastLevelLevelOrder = temp.right;

                    parentOfLastNode = temp;

                }

            }

        }

  

        // Выход из вышеприведенного цикла.

        // мы бы наверняка

        // последний посещенный узел, который

        // должен быть удален и его

        // родительский узел.

  

        if (lastLevelLevelOrder != null

            && parentOfLastNode != null) {

  

            // Если последний узел правый дочерний

            // родителя, сделать правильный узел

            // его родителя как NULL или

            // сделать левый узел пустым

            if (parentOfLastNode.right != null)

                parentOfLastNode.right = null;

            else

                parentOfLastNode.left = null;

        }

        else

            System.out.println("Empty Tree");

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

  

        Node root = new Node(6);

        root.left = new Node(5);

        root.right = new Node(4);

        root.left.left = new Node(1);

        root.left.right = new Node(2);

        root.right.right = new Node(5);

  

        DeleteLastNode deleteLastNode

            = new DeleteLastNode();

  

        System.out.println("Inorder traversal "

                           + "before deletion of "

                           + "last node : ");

        deleteLastNode.inorder(root);

  

        deleteLastNode.deleteLastNode(root);

  

        System.out.println("\nInorder traversal "

                           + "after deletion "

                           + "of last node : ");

  

        deleteLastNode.inorder(root);

    }

}

// C # реализация подхода

using System;

using System.Collections.Generic;

public class DeleteLastNode {

       

    // Tree Node

    public class Node {

   

        public Node left, right;

        public int data;

   

        public Node(int data)

        {

            this.data = data;

        }

    

   

    // Функция для обхода дерева по порядку

    public void inorder(Node root)

    {

        if (root == null)

            return;

   

        inorder(root.left);

        Console.Write(root.data + " ");

        inorder(root.right);

    }

   

    // Чтобы отслеживать последние

    // обработанные узлы родителя

    // и сам узел.

    public static Node lastLevelLevelOrder;

    public static Node parentOfLastNode;

   

    // Метод для удаления последнего узла

    // из дерева

    public void deleteLastNode(Node root)

    {

   

        // Если дерево пусто, оно

        // вернется без

        // любое удаление

        if (root == null)

            return;

   

        // Очередь будет нужна

        // поддерживать порядок уровня

        // обход узлов

        Queue<Node> queue = new Queue<Node>();

   

        queue.Enqueue(root);

   

        // Обход будет

        // продолжаем до всех

        // узлы пройдены один раз

        while (queue.Count!=0) {

   

            Node temp = queue.Dequeue();

   

            // Если остался ребенок

            if (temp.left != null) {

                queue.Enqueue(temp.left);

   

                // Для каждого пройденного узла

                // мы бы проверили, если это

                // листовой узел, проверяя, если

                // текущий узел имеет потомков

                if (temp.left.left == null

                    && temp.left.right == null) {

   

                    // Для каждого конечного узла

                    // столкнулись, мы бы

                    // сохранить не как

                    // "Узел ранее посещенных листьев.

                    lastLevelLevelOrder = temp.left;

                    parentOfLastNode = temp;

                }

            }

   

            if (temp.right != null) {

                queue.Enqueue(temp.right);

   

                if (temp.right.left == null

                    && temp.right.right == null) {

   

                    // Для каждого конечного узла

                    // столкнулись, мы бы

                    // сохранить не как

                    // "Узел ранее посещенных листьев.

                    lastLevelLevelOrder = temp.right;

                    parentOfLastNode = temp;

                }

            }

        }

   

        // Выход из вышеприведенного цикла.

        // мы бы наверняка

        // последний посещенный узел, который

        // должен быть удален и его

        // родительский узел.

   

        if (lastLevelLevelOrder != null

            && parentOfLastNode != null) {

   

            // Если последний узел правый дочерний

            // родителя, сделать правильный узел

            // его родителя как NULL или

            // сделать левый узел пустым

            if (parentOfLastNode.right != null)

                parentOfLastNode.right = null;

            else

                parentOfLastNode.left = null;

        }

        else

            Console.WriteLine("Empty Tree");

    }

   

    // Код драйвера

    public static void Main(String[] args)

    {

   

        Node root = new Node(6);

        root.left = new Node(5);

        root.right = new Node(4);

        root.left.left = new Node(1);

        root.left.right = new Node(2);

        root.right.right = new Node(5);

   

        DeleteLastNode deleteLastNode

            = new DeleteLastNode();

   

        Console.WriteLine("Inorder traversal "

                           + "before deletion of "

                           + "last node : ");

        deleteLastNode.inorder(root);

   

        deleteLastNode.deleteLastNode(root);

   

        Console.WriteLine("\nInorder traversal "

                           + "after deletion "

                           + "of last node : ");

   

        deleteLastNode.inorder(root);

    }

}

  
// Этот код предоставлен Rajput-Ji

Выход:

Inorder traversal before deletion of last node : 
1 5 2 6 4 5 
Inorder traversal after deletion of last node : 
1 5 2 6 4

Сложность времени:

Поскольку каждый узел будет посещен один раз, время, затраченное на него, будет линейным по отношению к количеству узлов, присутствующих в дереве.
Вспомогательное пространство:
Поскольку мы будем поддерживать очередь для прохождения порядка уровней, потребляемое пространство будет ,

Рекомендуемые посты:

Удалить последний листовой узел в двоичном дереве

0.00 (0%) 0 votes