Рубрики

Проверка суммы покрытых и непокрытых узлов двоичного дерева

Для данного двоичного дерева вам необходимо проверить, равна ли сумма всех покрытых элементов сумме всех непокрытых элементов или нет.
В двоичном дереве узел называется Uncovered, если он появляется на левой или правой границе. Остальные узлы называются закрытыми.

Например, рассмотрим ниже двоичное дерево


In above binary tree,
Covered node:     6, 5, 7
Uncovered node:   9, 4, 3, 17, 22, 20

The output for this tree should be false as 
sum of covered and uncovered node is not same

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

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

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

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

C ++

// C ++ программа для поиска суммы Covered и Uncovered узла
// двоичное дерево
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева имеет ключ, указатель налево

   дочерний элемент и указатель на правый дочерний элемент * /

struct Node

{

    int key;

    struct Node* left, *right;

};

  
/ * Создать новый узел дерева и вернуть указатель * /

struct Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

    temp->left = temp->right = NULL;

    return (temp);

}

  
/ * Утилита для расчета суммы всех узлов дерева * /

int sum(Node* t)

{

    if (t == NULL)

        return 0;

    return t->key + sum(t->left) + sum(t->right);

}

  
/ * Рекурсивная функция для вычисления суммы левой границы

   элементы * /

int uncoveredSumLeft(Node* t)

{

    / * Если листовой узел, то просто вернуть его значение ключа * /

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

        return t->key;

  

    / * Если доступно левое, то идите налево, в противном случае идите направо * /

    if (t->left != NULL)

        return t->key + uncoveredSumLeft(t->left);

    else

        return t->key + uncoveredSumLeft(t->right);

}

  
/ * Рекурсивная функция для вычисления суммы правой границы

   элементы * /

int uncoveredSumRight(Node* t)

{

    / * Если листовой узел, то просто вернуть его значение ключа * /

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

        return t->key;

  

    / * Если право доступно, тогда идите направо, в противном случае идите налево * /

    if (t->right != NULL)

        return t->key + uncoveredSumRight(t->right);

    else

        return t->key + uncoveredSumRight(t->left);

}

  
// Возвращает сумму непокрытых элементов

int uncoverSum(Node* t)

{

    / * Инициализация с 0, если у нас нет

       левая или правая граница * /

    int lb = 0, rb = 0;

  

    if (t->left != NULL)

        lb = uncoveredSumLeft(t->left);

    if (t->right != NULL)

        rb = uncoveredSumRight(t->right);

  

    / * возвращаем сумму корневого узла, левая граница

       и правая граница * /

    return t->key + lb + rb;

}

  
// Возвращает true, если сумма покрытых и непокрытых элементов
// такой же.

bool isSumSame(Node *root)

{

    // Сумма непокрытых элементов

    int sumUC = uncoverSum(root);

  

    // Сумма всех элементов

    int sumT = sum(root);

  

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

    return (sumUC == (sumT - sumUC));

}

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

   бинарное дерево * /

void inorder(Node* root)

{

    if (root)

    {

        inorder(root->left);

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

        inorder(root->right);

    }

}

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

int main()

{

    // Создание бинарного дерева данной диаграммы

    Node* root = newNode(8);

    root->left = newNode(3);

  

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

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

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

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

  

    root->right = newNode(10);

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

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

  

    if (isSumSame(root))

        printf("Sum of covered and uncovered is same\n");

    else

        printf("Sum of covered and uncovered is not same\n");

}

Джава

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

  
/ * Узел двоичного дерева имеет ключ, указатель на левого потомка и

   указатель на правого ребенка * /

class Node 

{

    int key;

    Node left, right;

  

    public Node(int key) 

    {

        this.key = key;

        left = right = null;

    }

}

  

class BinaryTree 

{

    Node root;

  

    / * Утилита для расчета суммы всех узлов дерева * /

    int sum(Node t) 

    {

        if (t == null

            return 0;

        return t.key + sum(t.left) + sum(t.right);

    }

  

    / * Рекурсивная функция для вычисления суммы левой границы

       элементы * /

    int uncoveredSumLeft(Node t) 

    {

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

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

            return t.key;

  

        / * Если доступно левое, то идите налево, в противном случае идите направо * /

        if (t.left != null

            return t.key + uncoveredSumLeft(t.left);

         else 

            return t.key + uncoveredSumLeft(t.right);

    }

  

    / * Рекурсивная функция для вычисления суммы правой границы

       элементы * /

    int uncoveredSumRight(Node t) 

    {

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

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

            return t.key;

  

        / * Если право доступно, тогда идите направо, в противном случае идите налево * /

        if (t.right != null)

            return t.key + uncoveredSumRight(t.right);

        else

            return t.key + uncoveredSumRight(t.left);

    }

  

    // Возвращает сумму непокрытых элементов

    int uncoverSum(Node t) 

    {

        / * Инициализация с 0, если у нас нет

           левая или правая граница * /

        int lb = 0, rb = 0;

  

        if (t.left != null)

            lb = uncoveredSumLeft(t.left);

        if (t.right != null)

            rb = uncoveredSumRight(t.right);

  

        / * возвращаем сумму корневого узла, левая граница

           и правая граница * /

        return t.key + lb + rb;

    }

  

    // Возвращает true, если сумма покрытых и непокрытых элементов

    // такой же.

    boolean isSumSame(Node root) 

    {

        // Сумма непокрытых элементов

        int sumUC = uncoverSum(root);

  

        // Сумма всех элементов

        int sumT = sum(root);

  

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

        return (sumUC == (sumT - sumUC));

    }

  

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

       бинарное дерево * /

    void inorder(Node root) 

    {

        if (root != null

        {

            inorder(root.left);

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

            inorder(root.right);

        }

    }

  

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

    public static void main(String[] args) 

    {

  

        BinaryTree tree = new BinaryTree();

  

        // Создание бинарного дерева данной диаграммы

        tree.root = new Node(8);

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

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

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

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

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

  

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

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

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

  

        if (tree.isSumSame(tree.root)) 

            System.out.println("Sum of covered and uncovered is same");

         else 

            System.out.println("Sum of covered and uncovered is not same");

    }

}

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

python3

# Python3 программа для поиска суммы Covered и
# Обнаружен узел двоичного дерева

  
# Создать новый узел дерева и вернуть указатель

class newNode:

    def __init__(self, key):

        self.key = key 

        self.left = self.right = None

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

def Sum(t):

    if (t == None):

        return 0

    return t.key + Sum(t.left) + Sum(t.right)

  
# Рекурсивная функция для вычисления суммы
Количество левых граничных элементов

def uncoveredSumLeft(t):

      

    # Если листовой узел, то просто вернуть

    # его значение ключа

    if (t.left == None and t.right == None): 

        return t.key 

  

    # Если осталось доступно, то иди

    # влево, иначе идти направо

    if (t.left != None): 

        return t.key + uncoveredSumLeft(t.left) 

    else:

        return t.key + uncoveredSumLeft(t.right)

  
# Рекурсивная функция для вычисления суммы
# правые граничные элементы

def uncoveredSumRight(t):

      

    # Если листовой узел, то просто вернуть

    # его значение ключа

    if (t.left == None and t.right == None): 

        return t.key 

  

    # Если право доступно, тогда идите направо

    # в противном случае идите налево

    if (t.right != None):

        return t.key + uncoveredSumRight(t.right) 

    else:

        return t.key + uncoveredSumRight(t.left)

  
# Возвращает сумму непокрытых элементов

def uncoverSum(t):

      

    # Инициализация с 0 в случае, если мы

    # не имеет левой или правой границы

    lb = 0

    rb = 0

  

    if (t.left != None):

        lb = uncoveredSumLeft(t.left) 

    if (t.right != None): 

        rb = uncoveredSumRight(t.right) 

  

    # возвращаем сумму корневого узла,

    # левая граница и правая граница

    return t.key + lb + rb 

  
# Возвращает true, если сумма покрыта и
# непокрытые элементы одинаковы.

def isSumSame(root):

      

    # Сумма раскрытых элементов

    sumUC = uncoverSum(root) 

  

    # Сумма всех элементов

    sumT = Sum(root) 

  

    # Проверьте, покрыта ли сумма и

    # раскрыто то же самое

    return (sumUC == (sumT - sumUC))

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

def inorder(root):

    if (root):

        inorder(root.left) 

        print(root.key, end = " "

        inorder(root.right)

  
Код водителя

if __name__ == '__main__':

      

    # Создание выше данной диаграммы

    # двоичное дерево

    root = newNode(8

    root.left = newNode(3

  

    root.left.left = newNode(1

    root.left.right = newNode(6

    root.left.right.left = newNode(4

    root.left.right.right = newNode(7

  

    root.right = newNode(10

    root.right.right = newNode(14

    root.right.right.left = newNode(13

  

    if (isSumSame(root)): 

        print("Sum of covered and uncovered is same"

    else:

        print("Sum of covered and uncovered is not same")

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

C #

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

using System;

  
/ * Узел двоичного дерева имеет ключ, указатель
левый ребенок и указатель на правый ребенок * /

public class Node

{

    public int key;

    public Node left, right;

  

    public Node(int key)

    {

        this.key = key;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

  
/ * Утилита для расчета
сумма всего узла дерева * /

public virtual int sum(Node t)

{

    if (t == null)

    {

        return 0;

    }

    return t.key + sum(t.left) + 

                   sum(t.right);

}

  
/ * Рекурсивная функция для расчета
сумма левых граничных элементов * /

public virtual int uncoveredSumLeft(Node t)

{

    / * Если левый узел, то просто вернуть

       его значение ключа * /

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

    {

        return t.key;

    }

  

    / * Если осталось доступно, то иди

       влево в противном случае идти направо * /

    if (t.left != null)

    {

        return t.key + uncoveredSumLeft(t.left);

    }

    else

    {

        return t.key + uncoveredSumLeft(t.right);

    }

}

  
/ * Рекурсивная функция для расчета

   сумма правых граничных элементов * /

public virtual int uncoveredSumRight(Node t)

{

    / * Если левый узел, то просто вернуть

       его значение ключа * /

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

    {

        return t.key;

    }

  

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

       вправо в противном случае идти налево *

    if (t.right != null)

    {

        return t.key + uncoveredSumRight(t.right);

    }

    else

    {

        return t.key + uncoveredSumRight(t.left);

    }

}

  
// Возвращает сумму непокрытых элементов

public virtual int uncoverSum(Node t)

{

    / * Инициализация с 0 в случае, если мы

    не имеет левой или правой границы * /

    int lb = 0, rb = 0;

  

    if (t.left != null)

    {

        lb = uncoveredSumLeft(t.left);

    }

    if (t.right != null)

    {

        rb = uncoveredSumRight(t.right);

    }

  

    / * возвращаем сумму корневого узла,

    левая граница и правая граница * /

    return t.key + lb + rb;

}

  
// Возвращает true, если сумма покрыта
// и непокрытые элементы одинаковы.

public virtual bool isSumSame(Node root)

{

    // Сумма непокрытых элементов

    int sumUC = uncoverSum(root);

  

    // Сумма всех элементов

    int sumT = sum(root);

  

    // Проверяем, покрыта ли сумма и

    // непокрыто то же самое

    return (sumUC == (sumT - sumUC));

}

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

public virtual void inorder(Node root)

{

    if (root != null)

    {

        inorder(root.left);

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

        inorder(root.right);

    }

}

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

public static void Main(string[] args)

{

  

    GFG tree = new GFG();

  

    // Создание бинарного дерева данной диаграммы

    tree.root = new Node(8);

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

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

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

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

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

  

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

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

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

  

    if (tree.isSumSame(tree.root))

    {

        Console.WriteLine("Sum of covered and " +

                            "uncovered is same");

    }

    else

    {

        Console.WriteLine("Sum of covered and "

                        "uncovered is not same");

    }

}
}

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

Выход :

Sum of covered and uncovered is not same

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

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

Проверка суммы покрытых и непокрытых узлов двоичного дерева

0.00 (0%) 0 votes