Рубрики

Удалите все узлы, которые не лежат ни на одном пути с суммой> = k

Для заданного двоичного дерева полный путь определяется как путь от корня к листу. Сумма всех узлов на этом пути определяется как сумма этого пути. Учитывая число K, вы должны удалить (обрезать дерево) все узлы, которые не лежат ни на одном пути с суммой> = k.

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

Consider the following Binary Tree
          1 
      /      \
     2        3
   /   \     /  \
  4     5   6    7
 / \    /       /
8   9  12      10
   / \           \
  13  14         11
      / 
     15 

For input k = 20, the tree should be changed to following
(Nodes with values 6 and 8 are deleted)
          1 
      /      \
     2        3
   /   \        \
  4     5        7
   \    /       /
    9  12      10
   / \           \
  13  14         11
      / 
     15 

For input k = 45, the tree should be changed to following.
      1 
    / 
   2   
  / 
 4  
  \   
   9    
    \   
     14 
     /
    15 


Идея состоит в том, чтобы пройти по дереву и удалить узлы снизу вверх. Обходя дерево, рекурсивно рассчитайте сумму узлов от корневого до конечного узла каждого пути. Для каждого посещенного узла проверяется общая рассчитанная сумма по отношению к заданной сумме «k». Если сумма меньше, чем k, освободите (удалите) этот узел (конечный узел) и верните сумму обратно на предыдущий узел. Поскольку путь идет от корня к листу, а узлы удаляются снизу вверх, узел удаляется только тогда, когда удаляются все его потомки. Следовательно, когда узел удаляется, он должен быть листом в текущем двоичном дереве.

Ниже приводится реализация вышеуказанного подхода.

C ++

#include <stdio.h>
#include <stdlib.h>

  
// Вспомогательная функция для получения максимум двух целых

int max(int l, int r) { return (l > r ? l : r); }

  
// Узел двоичного дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Вспомогательная функция для создания нового узла двоичного дерева с заданными данными

struct Node* newNode(int data)

{

    struct Node* node = (struct Node*) malloc(sizeof(struct Node));

    node->data = data;

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

    return node;

}

  
// распечатать дерево в LVR (Inorder traversal).

void print(struct Node *root)

{

    if (root != NULL)

    {

        print(root->left);

        printf("%d ",root->data);

        print(root->right);

    }

}

  
/ * Основная функция, которая усекает двоичное дерево. * /

struct Node *pruneUtil(struct Node *root, int k, int *sum)

{

    // Базовый вариант

    if (root == NULL)  return NULL;

  

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

    // этот узел (включая этот узел)

    int lsum = *sum + (root->data);

    int rsum = lsum;

  

    // Рекурсивно обрезать левое и правое поддеревья

    root->left = pruneUtil(root->left, k, &lsum);

    root->right = pruneUtil(root->right, k, &rsum);

  

    // Получить максимум левой и правой сумм

    *sum = max(lsum, rsum);

  

    // Если максимум меньше k, то этот узел

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

    if (*sum < k)

    {

        free(root);

        root = NULL;

    }

  

    return root;

}

  
// Оболочка над pruneUtil ()

struct Node *prune(struct Node *root, int k)

{

    int sum = 0;

    return pruneUtil(root, k, &sum);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int k = 45;

    struct Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

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

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

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

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

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

  

    printf("Tree before truncation\n");

    print(root);

  

    root = prune(root, k); // к 45

  

    printf("\n\nTree after truncation\n");

    print(root);

  

    return 0;

}

Джава

// Java-программа для реализации
// вышеуказанный подход

import java.util.*; 

class GFG

{

  
// Полезная функция для получения
// максимум двух целых

static int max(int l, int r) 

    return (l > r ? l : r);

  
// Узел двоичного дерева

static class Node 

    int data; 

    Node left, right; 

}; 

  

static class INT

{

    int v;

INT(int a)

{

    v = a;

}
}

  
// Полезная функция для создания
// новый узел двоичного дерева с
// предоставленные данные

static Node newNode(int data) 

    Node node = new Node(); 

    node.data = data; 

    node.left = node.right = null

    return node; 

  
// распечатать дерево в LVR
// (Inorder traversal) way.

static void print(Node root) 

    if (root != null

    

        print(root.left); 

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

        print(root.right); 

    

  
// Основная функция, которая
// обрезает двоичное дерево.

static Node pruneUtil(Node root, int k, 

                      INT sum) 

    // Базовый вариант

    if (root == null) return null

  

    // Инициализация влево и вправо

    // суммы как сумма от корня до

    // этот узел (включая этот узел)

    INT lsum = new INT(sum.v + (root.data)); 

    INT rsum = new INT(lsum.v); 

  

    // рекурсивно обрезать влево

    // и правильные поддеревья

    root.left = pruneUtil(root.left, k, lsum); 

    root.right = pruneUtil(root.right, k, rsum); 

  

    // Получить максимум

    // левая и правая суммы

    sum.v = max(lsum.v, rsum.v); 

  

    // Если максимум меньше

    // чем к, то этот узел

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

    if (sum.v < k) 

    

  

        root = null

    

  

    return root; 

  
// Оболочка над pruneUtil ()

static Node prune(Node root, int k) 

    INT sum = new INT(0); 

    return pruneUtil(root, k, sum); 

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

public static void main(String args[])

    int k = 45

    Node root = newNode(1); 

    root.left = newNode(2); 

    root.right = newNode(3); 

    root.left.left = newNode(4); 

    root.left.right = newNode(5); 

    root.right.left = newNode(6); 

    root.right.right = newNode(7); 

    root.left.left.left = newNode(8); 

    root.left.left.right = newNode(9); 

    root.left.right.left = newNode(12); 

    root.right.right.left = newNode(10); 

    root.right.right.left.right = newNode(11); 

    root.left.left.right.left = newNode(13); 

    root.left.left.right.right = newNode(14); 

    root.left.left.right.right.left = newNode(15); 

  

    System.out.println("Tree before truncation\n"); 

    print(root); 

  

    root = prune(root, k); // к 45

  

    System.out.println("\n\nTree after truncation\n"); 

    print(root); 


}

  
// Этот код предоставлен Арнабом Кунду

python3

# Класс для создания нового двоичного дерева
# узел с заданными данными

class newNode:

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

  
# распечатать дерево LVR (Inorder traversal).

def Print(root):

    if (root != None):

        Print(root.left) 

        print(root.data, end = " "

        Print(root.right)

  
# Основная функция, которая усекает
# двоичное дерево.

def pruneUtil(root, k, Sum):

      

    # Базовый вариант

    if (root == None):

        return None

  

    # Инициализировать левую и правую суммы как

    # Сумма от корня до этого узла

    # (включая этот узел)

    lSum = [Sum[0] + (root.data)] 

    rSum = [lSum[0]] 

  

    # Рекурсивно обрезать влево и вправо

    # поддеревья

    root.left = pruneUtil(root.left, k, lSum) 

    root.right = pruneUtil(root.right, k, rSum) 

  

    # Получите максимум левой и правой сумм

    Sum[0] = max(lSum[0], rSum[0]) 

  

    # Если максимум меньше, чем k,

    # тогда этот узел должен быть удален

    if (Sum[0] < k[0]):

        root = None

    return root

  
# Обертка над pruneUtil ()

def prune(root, k):

    Sum = [0

    return pruneUtil(root, k, Sum)

  
Код водителя

if __name__ == '__main__':

    k = [45]

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

    root.left.left = newNode(4

    root.left.right = newNode(5

    root.right.left = newNode(6

    root.right.right = newNode(7

    root.left.left.left = newNode(8

    root.left.left.right = newNode(9

    root.left.right.left = newNode(12

    root.right.right.left = newNode(10

    root.right.right.left.right = newNode(11

    root.left.left.right.left = newNode(13

    root.left.left.right.right = newNode(14

    root.left.left.right.right.left = newNode(15

  

    print("Tree before truncation")

    Print(root) 

    print()

    root = prune(root, k) # к 45

  

    print("Tree after truncation")

    Print(root)

  
# Этот код предоставлен PranchalK

C #

using System;

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

public class GFG

{

  
// Полезная функция для получения
// максимум двух целых

public static int max(int l, int r)

{

    return (l > r ? l : r);

}

  
// Узел двоичного дерева

public class Node

{

    public int data;

    public Node left, right;

}

  

public class INT

{

    public int v;

public INT(int a)

{

    v = a;

}
}

  
// Полезная функция для создания
// новый узел двоичного дерева с
// предоставленные данные

public static Node newNode(int data)

{

    Node node = new Node();

    node.data = data;

    node.left = node.right = null;

    return node;

}

  
// распечатать дерево в LVR
// (Inorder traversal) way.

public static void print(Node root)

{

    if (root != null)

    {

        print(root.left);

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

        print(root.right);

    }

}

  
// Основная функция, которая
// обрезает двоичное дерево.

public static Node pruneUtil(Node root, int k, INT sum)

{

    // Базовый вариант

    if (root == null)

    {

        return null;

    }

  

    // Инициализация влево и вправо

    // суммы как сумма от корня до

    // этот узел (включая этот узел)

    INT lsum = new INT(sum.v + (root.data));

    INT rsum = new INT(lsum.v);

  

    // рекурсивно обрезать влево

    // и правильные поддеревья

    root.left = pruneUtil(root.left, k, lsum);

    root.right = pruneUtil(root.right, k, rsum);

  

    // Получить максимум

    // левая и правая суммы

    sum.v = max(lsum.v, rsum.v);

  

    // Если максимум меньше

    // чем к, то этот узел

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

    if (sum.v < k)

    {

  

        root = null;

    }

  

    return root;

}

  
// Оболочка над pruneUtil ()

public static Node prune(Node root, int k)

{

    INT sum = new INT(0);

    return pruneUtil(root, k, sum);

}

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

public static void Main(string[] args)

{

    int k = 45;

    Node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

    root.right.left = newNode(6);

    root.right.right = newNode(7);

    root.left.left.left = newNode(8);

    root.left.left.right = newNode(9);

    root.left.right.left = newNode(12);

    root.right.right.left = newNode(10);

    root.right.right.left.right = newNode(11);

    root.left.left.right.left = newNode(13);

    root.left.left.right.right = newNode(14);

    root.left.left.right.right.left = newNode(15);

  

    Console.WriteLine("Tree before truncation\n");

    print(root);

  

    root = prune(root, k); // к 45

  

    Console.WriteLine("\n\nTree after truncation\n");

    print(root);

}
}

  

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


Выход:

Tree before truncation
8 4 13 9 15 14 2 12 5 1 6 3 10 11 7

Tree after truncation
4 9 15 14 2 1

Сложность времени: O (n), решение выполняет один обход заданного двоичного дерева.

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

Спасибо Вики за предложение этого решения в комментариях ниже.

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Узел двоичного дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Вспомогательная функция для создания нового двоичного файла
// Узел дерева с заданными данными

struct Node* newNode(int data)

{

    struct Node* node =

    (struct Node*) malloc(sizeof(struct Node));

    node->data = data;

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

    return node;

}

  
// распечатать дерево в LVR (Inorder traversal).

void print(struct Node *root)

{

    if (root != NULL)

    {

        print(root->left);

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

        print(root->right);

    }

}

  
/ * Основная функция, которая усекает двоичное дерево. * /

struct Node *prune(struct Node *root, int sum)

{

    // Базовый вариант

    if (root == NULL) return NULL;

  

    // Повтор для левого и правого поддеревьев

    root->left = prune(root->left, sum - root->data);

    root->right = prune(root->right, sum - root->data);

  

    // Если мы дойдем до листа, данные которого меньше суммы,

    // удаляем лист. Важно отметить

    // это нелистовый узел, который может стать листом, когда его

    // дети удалены.

    if (root->left==NULL && root->right==NULL)

    {

        if (root->data < sum)

        {

            free(root);

            return NULL;

        }

    }

  

    return root;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int k = 45;

    struct Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

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

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

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

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

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

  

    cout << "Tree before truncation\n";

    print(root);

  

    root = prune(root, k); // к 45

  

    cout << "\n\nTree after truncation\n";

    print(root);

  

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

#include <stdio.h>
#include <stdlib.h>

  
// Узел двоичного дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Вспомогательная функция для создания нового двоичного файла
// Узел дерева с заданными данными

struct Node* newNode(int data)

{

    struct Node* node =

       (struct Node*) malloc(sizeof(struct Node));

    node->data = data;

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

    return node;

}

  
// распечатать дерево в LVR (Inorder traversal).

void print(struct Node *root)

{

    if (root != NULL)

    {

        print(root->left);

        printf("%d ",root->data);

        print(root->right);

    }

}

  
/ * Основная функция, которая усекает двоичное дерево. * /

struct Node *prune(struct Node *root, int sum)

{

    // Базовый вариант

    if (root == NULL) return NULL;

  

    // Повтор для левого и правого поддеревьев

    root->left = prune(root->left, sum - root->data);

    root->right = prune(root->right, sum - root->data);

  

    // Если мы дойдем до листа, данные которого меньше суммы,

    // удаляем лист. Важно отметить

    // это нелистовый узел, который может стать листом, когда его

    // дети удалены.

    if (root->left==NULL && root->right==NULL)

    {

        if (root->data < sum)

        {

            free(root);

            return NULL;

        }

    }

  

    return root;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int k = 45;

    struct Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

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

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

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

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

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

  

    printf("Tree before truncation\n");

    print(root);

  

    root = prune(root, k); // к 45

  

    printf("\n\nTree after truncation\n");

    print(root);

  

    return 0;

}

Джава

// Java-программа для удаления всех узлов, которые не
// лежим на пути с суммой> = k

  
// Класс, представляющий узел двоичного дерева

class Node {

    int data;

    Node left;

    Node right;

  

    // Конструктор для создания нового узла

    public Node(int data) {

        this.data = data;

        left = null;

        right = null;

    }

}

  
// класс для усечения двоичного дерева

class BinaryTree {

    Node root;

  

    // рекурсивный метод для усечения двоичного дерева

    public Node prune(Node root, int sum) {

  

        // базовый вариант

        if (root == null)

            return null;

  

        // повторить для левого и правого поддерева

        root.left = prune(root.left, sum - root.data);

        root.right = prune(root.right, sum - root.data);

  

        // если узел - это листовой узел, данные которого меньше

        // чем сумма удаляем лист. Важно

        // следует отметить, что неконечный узел может стать

        // лист, когда его дочерние элементы удалены.

        if (isLeaf(root)) {

            if (sum > root.data)

                root = null;

        }

  

        return root;

    

  

    // служебный метод, чтобы проверить, является ли узел листом

    public boolean isLeaf(Node root) {

        if (root == null)

            return false;

        if (root.left == null && root.right == null)

            return true;

        return false;

    }

  

    // для обхода печати

    public void print(Node root) {

  

        // базовый вариант

        if (root == null)

            return;

  

        print(root.left);

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

        print(root.right);

    }

}

  
// Класс драйвера для проверки вышеуказанной функции

public class GFG {

    public static void main(String args[]) {

  

        BinaryTree tree = new BinaryTree();

  

        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.right.left = new Node(6);

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

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

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

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

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

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

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

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

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

  

        System.out.println("Tree before truncation");

        tree.print(tree.root);

  

        tree.prune(tree.root, 45);

  

        System.out.println("\nTree after truncation");

        tree.print(tree.root);

    }

}

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

python3

«»»
Программа Python для удаления всех узлов, которые не
лежат на любом пути с суммой> = k
«»»

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

class Node:

      

    # конструктор для создания узла дерева

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Функция для удаления всех узлов, которые не
# лежать на пути сумм

def prune(root, sum):

  

    # Базовый вариант

    if root is None:

        return None

  

    # Повтор для левого и правого поддерева

    root.left = prune(root.left, sum - root.data)

    root.right = prune(root.right, sum - root.data)

  

    # если узел является листом и сумма найдена больше

    # чем данные, чем удалить узел Важно

    # нужно помнить, что неконечный узел

    # может стать листом, когда его дети

    # удалено

    if root.left is None and root.right is None:

        if sum > root.data:

            return None

  

    return root

  
# обход заказа

def inorder(root):

    if root is None:

        return

    inorder(root.left)

    print(root.data, "", end="")

    inorder(root.right)

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.left = Node(6)

root.right.right = Node(7)

root.left.left.left = Node(8)

root.left.left.right = Node(9)

root.left.right.left = Node(12)

root.right.right.left = Node(10)

root.right.right.left.right = Node(11)

root.left.left.right.left = Node(13)

root.left.left.right.right = Node(14)

root.left.left.right.right.left = Node(15)

  

print("Tree before truncation")

inorder(root)

prune(root, 45)

print("\nTree after truncation")

inorder(root)

  
# Этот код предоставлен Shweta Singh

C #

using System;

  
// C # программа для удаления всех узлов, которые не
// лежим на пути с суммой> = k

  
// Класс, представляющий узел двоичного дерева

public class Node

{

    public int data;

    public Node left;

    public Node right;

  

    // Конструктор для создания нового узла

    public Node(int data)

    {

        this.data = data;

        left = null;

        right = null;

    }

}

  
// класс для усечения двоичного дерева

public class BinaryTree

{

    public Node root;

  

    // рекурсивный метод для усечения двоичного дерева

    public virtual Node prune(Node root, int sum)

    {

  

        // базовый вариант

        if (root == null)

        {

            return null;

        }

  

        // повторить для левого и правого поддерева

        root.left = prune(root.left, sum - root.data);

        root.right = prune(root.right, sum - root.data);

  

        // если узел - это листовой узел, данные которого меньше

        // чем сумма удаляем лист. Важно

        // следует отметить, что неконечный узел может стать

        // лист, когда его дочерние элементы удалены.

        if (isLeaf(root))

        {

            if (sum > root.data)

            {

                root = null;

            }

        }

  

        return root;

    }

  

    // служебный метод, чтобы проверить, является ли узел листом

    public virtual bool isLeaf(Node root)

    {

        if (root == null)

        {

            return false;

        }

        if (root.left == null && root.right == null)

        {

            return true;

        }

        return false;

    }

  

    // для обхода печати

    public virtual void print(Node root)

    {

  

        // базовый вариант

        if (root == null)

        {

            return;

        }

  

        print(root.left);

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

        print(root.right);

    }

}

  
// Класс драйвера для проверки вышеуказанной функции

public class GFG

{

    public static void Main(string[] args)

    {

  

        BinaryTree tree = new BinaryTree();

  

        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.right.left = new Node(6);

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

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

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

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

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

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

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

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

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

  

        Console.WriteLine("Tree before truncation");

        tree.print(tree.root);

  

        tree.prune(tree.root, 45);

  

        Console.WriteLine("\nTree after truncation");

        tree.print(tree.root);

    }

}

  

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


Выход:

Tree before truncation
8 4 13 9 15 14 2 12 5 1 6 3 10 11 7

Tree after truncation
4 9 15 14 2 1

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

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

Удалите все узлы, которые не лежат ни на одном пути с суммой> = k

0.00 (0%) 0 votes