Рубрики

Удалить узлы от корневых до конечных путей длиной <K

Учитывая двоичное дерево и число k, удалите все узлы, которые лежат только от корневого до конечного пути (путей) длины меньше, чем k. Если узел X лежит на нескольких путях от корня к листу и если какой-либо из путей имеет длину пути> = k, то X не удаляется из двоичного дерева. Другими словами, узел удаляется, если все пути, проходящие через него, имеют длину меньше k.

Рассмотрим следующий пример двоичного дерева

               1
           /      \
         2          3
      /     \         \
    4         5        6
  /                   /
 7                   8 
Input: Root of above Binary Tree
       k = 4

Output: The tree should be changed to following  
           1
        /     \
      2          3
     /             \
   4                 6
 /                  /
7                  8
There are 3 paths 
i) 1->2->4->7      path length = 4
ii) 1->2->5        path length = 3
iii) 1->3->6->8    path length = 4 
There is only one path " 1->2->5 " of length smaller than 4.  
The node 5 is the only node that lies only on this path, so 
node 5 is removed.
Nodes 2 and 1 are not removed as they are parts of other paths
of length 4 as well.

If k is 5 or greater than 5, then whole tree is deleted. 

If k is 3 or less than 3, then nothing is deleted.

Мы настоятельно рекомендуем свернуть ваш браузер и попробовать это сами

Идея здесь состоит в том, чтобы использовать обратный порядок дерева. Перед удалением узла мы должны убедиться, что все дочерние элементы этого узла в более коротком пути уже удалены.
Есть 2 случая:
i) Этот узел становится листовым узлом, и в этом случае его необходимо удалить.
ii) Этот узел имеет другого потомка на пути с длиной пути> = k. В этом случае его не нужно удалять.

Реализация вышеуказанного подхода выглядит следующим образом:

C / C ++

// C ++ программа для удаления узлов от корневых до конечных путей длины <K
#include<iostream>

using namespace std;

  

struct Node

{

    int data;

    Node *left, *right;

};

  
// Новый узел дерева

Node *newNode(int data)

{

    Node *node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return node;

}

  
// Служебный метод, который фактически удаляет узлы, которые не являются
// на pathLen> = k. Этот метод также может изменить корень.

Node *removeShortPathNodesUtil(Node *root, int level, int k)

{

    // Базовое условие

    if (root == NULL)

        return NULL;

  

    // Пройдем по дереву по порядку следования, чтобы, если лист

    // длина пути узла меньше k, тогда этот узел и

    // все его потомки до узла, которые не являются

    // по другому пути удаляются.

    root->left = removeShortPathNodesUtil(root->left, level + 1, k);

    root->right = removeShortPathNodesUtil(root->right, level + 1, k);

  

    // Если root является листовым узлом и его уровень меньше k, то

    // удалить этот узел.

    // Это идет вверх и проверяет узлы предков также для

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

    // путь (ы) тоже.

    if (root->left == NULL && root->right == NULL && level < k)

    {

        delete root;

        return NULL;

    }

  

    // Return root;

    return root;

}

  
// Метод, который вызывает метод utitlity для удаления короткого пути
// узлы.

Node *removeShortPathNodes(Node *root, int k)

{

    int pathLen = 0;

    return removeShortPathNodesUtil(root, 1, k);

}

  
// Способ печати дерева по порядку.

void printInorder(Node *root)

{

    if (root)

    {

        printInorder(root->left);

        cout << root->data << " ";

        printInorder(root->right);

    }

}

  
// Метод драйвера.

int main()

{

    int k = 4;

    Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->left->left->left = newNode(7);

    root->right->right = newNode(6);

    root->right->right->left = newNode(8);

    cout << "Inorder Traversal of Original tree" << endl;

    printInorder(root);

    cout << endl;

    cout << "Inorder Traversal of Modified tree" << endl;

    Node *res = removeShortPathNodes(root, k);

    printInorder(res);

    return 0;

}

Джава

// Java-программа для удаления узлов от корневых до конечных путей длины <k

   
/ * Класс, содержащий левого и правого потомка текущего

   значение узла и ключа * /

class Node 

{

    int data;

    Node left, right;

   

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    // Служебный метод, который фактически удаляет узлы, которые не являются

    // на pathLen> = k. Этот метод также может изменить корень.

    Node removeShortPathNodesUtil(Node node, int level, int k) 

    {

        // Базовое условие

        if (node == null)

            return null;

              

        // Пройдем по дереву по порядку следования, чтобы, если лист

        // длина пути узла меньше k, тогда этот узел и

        // все его потомки до узла, которые не являются

        // по другому пути удаляются.

        node.left = removeShortPathNodesUtil(node.left, level + 1, k);

        node.right = removeShortPathNodesUtil(node.right, level + 1, k);

   

        // Если root является листовым узлом и его уровень меньше k, то

        // удалить этот узел.

        // Это идет вверх и проверяет узлы предков также для

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

        // путь (ы) тоже.

        if (node.left == null && node.right == null && level < k)

            return null;

   

        // Return root;

        return node;

    }

   

    // Метод, который вызывает метод utitlity для удаления короткого пути

    // узлы.

    Node removeShortPathNodes(Node node, int k) 

    {

        int pathLen = 0;

        return removeShortPathNodesUtil(node, 1, k);

    }

   

    // Способ печати дерева по порядку.

    void printInorder(Node node) 

    {

        if (node != null

        {

            printInorder(node.left);

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

            printInorder(node.right);

        }

    }

   

    // Программа драйвера для тестирования образцов

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        int k = 4;

        tree.root = new Node(1);

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

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

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

        tree.root.left.left.left = new Node(7);

        tree.root.right.right = new Node(6);

        tree.root.right.right.left = new Node(8);

        System.out.println("The inorder traversal of original tree is : ");

        tree.printInorder(tree.root);

        Node res = tree.removeShortPathNodes(tree.root, k);

        System.out.println("");

        System.out.println("The inorder traversal of modified tree is : ");

        tree.printInorder(res);

    }

}

   
// Этот код предоставлен Mayank Jaiswal

python3

# Python3 программа для удаления узлов в корне
# до листа путей длины <K

  
# Новый узел дерева

class newNode: 

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

          
# Служебный метод, который фактически удаляет
# узлы, которых нет в pathLen> = k.
# Этот метод также может изменить корень.

def removeShortPathNodesUtil(root, level, k) :

  

    # Базовое состояние

    if (root == None) :

        return None

  

    # Пройдите дерево по порядку заказа

    # так что если длина пути конечного узла

    # короче k, то этот узел и все

    # его потомков до узла, который

    # не по другому пути удаляются.

    root.left = removeShortPathNodesUtil(root.left, 

                                         level + 1, k) 

    root.right = removeShortPathNodesUtil(root.right, 

                                          level + 1, k) 

  

    # Если root является листовым узлом и его уровень

    # меньше k, тогда удалите этот узел.

    # Это идет вверх и проверить на предка

    # узлов также для того же условия до

    # находит узел, который является частью другого

    # пути тоже.

    if (root.left == None and

        root.right == None and level < k) : 

        return None

      

    # Возврат корня

    return root 

  
# Метод, который вызывает метод utitlity
# удалить узлы короткого пути.

def removeShortPathNodes(root, k) :

    pathLen = 0

    return removeShortPathNodesUtil(root, 1, k) 

  
# Способ печати дерева в
# на заказ моды.

def prInorder(root) :

  

    if (root) :

      

        prInorder(root.left) 

        print(root.data, end = " " )

        prInorder(root.right) 

      
Код водителя

if __name__ == '__main__':

    k = 4

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

    root.left.left = newNode(4

    root.left.right = newNode(5

    root.left.left.left = newNode(7

    root.right.right = newNode(6

    root.right.right.left = newNode(8

    print("Inorder Traversal of Original tree"

    prInorder(root) 

    print()

    print("Inorder Traversal of Modified tree"

    res = removeShortPathNodes(root, k) 

    prInorder(res)

  
# Этот код добавлен
# от SHUBHAMSINGH10

C #

using System;

  
// C # программа для удаления узлов от корневых до конечных путей длины <k

  
/ * Класс, содержащий левого и правого потомка текущего

   значение узла и ключа * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

    // Служебный метод, который фактически удаляет узлы, которые не являются

    // на pathLen> = k. Этот метод также может изменить корень.

    public virtual Node removeShortPathNodesUtil(Node node, int level, int k)

    {

        // Базовое условие

        if (node == null)

        {

            return null;

        }

  

        // Пройдем по дереву по порядку следования, чтобы, если лист

        // длина пути узла меньше k, тогда этот узел и

        // все его потомки до узла, которые не являются

        // по другому пути удаляются.

        node.left = removeShortPathNodesUtil(node.left, level + 1, k);

        node.right = removeShortPathNodesUtil(node.right, level + 1, k);

  

        // Если root является листовым узлом и его уровень меньше k, то

        // удалить этот узел.

        // Это идет вверх и проверяет узлы предков также для

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

        // путь (ы) тоже.

        if (node.left == null && node.right == null && level < k)

        {

            return null;

        }

  

        // Return root;

        return node;

    }

  

    // Метод, который вызывает метод utitlity для удаления короткого пути

    // узлы.

    public virtual Node removeShortPathNodes(Node node, int k)

    {

        int pathLen = 0;

        return removeShortPathNodesUtil(node, 1, k);

    }

  

    // Способ печати дерева по порядку.

    public virtual void printInorder(Node node)

    {

        if (node != null)

        {

            printInorder(node.left);

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

            printInorder(node.right);

        }

    }

  

    // Программа драйвера для тестирования образцов

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        int k = 4;

        tree.root = new Node(1);

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

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

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

        tree.root.left.left.left = new Node(7);

        tree.root.right.right = new Node(6);

        tree.root.right.right.left = new Node(8);

        Console.WriteLine("The inorder traversal of original tree is : ");

        tree.printInorder(tree.root);

        Node res = tree.removeShortPathNodes(tree.root, k);

        Console.WriteLine("");

        Console.WriteLine("The inorder traversal of modified tree is : ");

        tree.printInorder(res);

    }

}

  

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


Выход:

Inorder Traversal of Original tree
7 4 2 5 1 3 8 6
Inorder Traversal of Modified tree
7 4 2 1 3 8 6

Временная сложность вышеуказанного решения составляет O (n), где n — количество узлов в данном двоичном дереве.

Эта статья предоставлена Кумар Гаутам . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Удалить узлы от корневых до конечных путей длиной <K

0.00 (0%) 0 votes