Рубрики

Сумма всех элементов N-арного Дерева

По заданному N-арному дереву найдите сумму всех элементов в нем.

Пример :

Input : Above tree
Output : Sum is 536

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

Ниже приведена реализация вышеуказанной идеи:

C ++

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

using namespace std;

  
// Представляет узел n-арного дерева

struct Node {

    int key;

    vector<Node*> child;

};

  
// Сервисная функция для создания нового узла дерева

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

    return temp;

}

  
// Функция для вычисления суммы
// всех элементов в родовом дереве

int sumNodes(Node* root)

{

    // инициализируем переменную суммы

    int sum = 0;

  

    if (root == NULL)

        return 0;

  

    // Создание очереди и проталкивание корня

    queue<Node*> q;

    q.push(root);

  

    while (!q.empty()) {

        int n = q.size();

  

        // Если у этого узла есть дети

        while (n > 0) {

  

            // Удалить элемент из очереди и

            // добавить его в переменную "sum"

            Node* p = q.front();

            q.pop();

            sum += p->key;

  

            // ставим в очередь всех потомков изъятого из строя предмета

            for (int i = 0; i < p->child.size(); i++)

                q.push(p->child[i]);

            n--;

        }

    }

    return sum;

}

  
// Драйвер программы

int main()

{

    // Создание родового дерева

    Node* root = newNode(20);

    (root->child).push_back(newNode(2));

    (root->child).push_back(newNode(34));

    (root->child).push_back(newNode(50));

    (root->child).push_back(newNode(60));

    (root->child).push_back(newNode(70));

    (root->child[0]->child).push_back(newNode(15));

    (root->child[0]->child).push_back(newNode(20));

    (root->child[1]->child).push_back(newNode(30));

    (root->child[2]->child).push_back(newNode(40));

    (root->child[2]->child).push_back(newNode(100));

    (root->child[2]->child).push_back(newNode(20));

    (root->child[0]->child[1]->child).push_back(newNode(25));

    (root->child[0]->child[1]->child).push_back(newNode(50));

  

    cout << sumNodes(root) << endl;

  

    return 0;

}

Джава

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

import java.util.*;

  

class GFG

{

  
// Представляет узел n-арного дерева

static class Node 

{

    int key;

    Vector<Node> child;

};

  
// Сервисная функция для создания нового узла дерева

static Node newNode(int key)

{

    Node temp = new Node();

    temp.key = key;

    temp.child = new Vector<>();

    return temp;

}

  
// Функция для вычисления суммы
// всех элементов в родовом дереве

static int sumNodes(Node root)

{

    // инициализируем переменную суммы

    int sum = 0;

  

    if (root == null)

        return 0;

  

    // Создание очереди и проталкивание корня

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

    q.add(root);

  

    while (!q.isEmpty()) 

    {

        int n = q.size();

  

        // Если у этого узла есть дети

        while (n > 0)

        {

  

            // Удалить элемент из очереди и

            // добавить его в переменную "sum"

            Node p = q.peek();

            q.remove();

            sum += p.key;

  

            // ставим в очередь всех потомков изъятого из строя предмета

            for (int i = 0; i < p.child.size(); i++)

                q.add(p.child.get(i));

            n--;

        }

    }

    return sum;

}

  
// Драйвер программы

public static void main(String[] args)

{

    // Создание родового дерева

    Node root = newNode(20);

    (root.child).add(newNode(2));

    (root.child).add(newNode(34));

    (root.child).add(newNode(50));

    (root.child).add(newNode(60));

    (root.child).add(newNode(70));

    (root.child.get(0).child).add(newNode(15));

    (root.child.get(0).child).add(newNode(20));

    (root.child.get(1).child).add(newNode(30));

    (root.child.get(2).child).add(newNode(40));

    (root.child.get(2).child).add(newNode(100));

    (root.child.get(2).child).add(newNode(20));

    (root.child.get(0).child.get(1).child).add(newNode(25));

    (root.child.get(0).child.get(1).child).add(newNode(50));

  

    System.out.print(sumNodes(root) +"\n");

}
}

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

C #

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

using System;

using System.Collections.Generic;

  

class GFG

{

  
// Представляет узел n-арного дерева

class Node 

{

    public int key;

    public List<Node> child;

};

  
// Сервисная функция для создания нового узла дерева

static Node newNode(int key)

{

    Node temp = new Node();

    temp.key = key;

    temp.child = new List<Node>();

    return temp;

}

  
// Функция для вычисления суммы
// всех элементов в родовом дереве

static int sumNodes(Node root)

{

    // инициализируем переменную суммы

    int sum = 0;

  

    if (root == null)

        return 0;

  

    // Создание очереди и проталкивание корня

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

    q.Enqueue(root);

  

    while (q.Count != 0) 

    {

        int n = q.Count;

  

        // Если у этого узла есть дети

        while (n > 0)

        {

  

            // Удалить элемент из очереди и

            // добавить его в переменную "sum"

            Node p = q.Peek();

            q.Dequeue();

            sum += p.key;

  

            // ставим в очередь всех потомков изъятого из строя предмета

            for (int i = 0; i < p.child.Count; i++)

                q.Enqueue(p.child[i]);

            n--;

        }

    }

    return sum;

}

  
// Драйвер программы

public static void Main(String[] args)

{

    // Создание родового дерева

    Node root = newNode(20);

    (root.child).Add(newNode(2));

    (root.child).Add(newNode(34));

    (root.child).Add(newNode(50));

    (root.child).Add(newNode(60));

    (root.child).Add(newNode(70));

    (root.child[0].child).Add(newNode(15));

    (root.child[0].child).Add(newNode(20));

    (root.child[1].child).Add(newNode(30));

    (root.child[2].child).Add(newNode(40));

    (root.child[2].child).Add(newNode(100));

    (root.child[2].child).Add(newNode(20));

    (root.child[0].child[1].child).Add(newNode(25));

    (root.child[0].child[1].child).Add(newNode(50));

  

    Console.Write(sumNodes(root) +"\n");

}
}

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

Выход:

536

Сложность времени: O (N), где N — количество узлов в дереве.
Вспомогательное пространство: O (N), где N — количество узлов в дереве.

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

Сумма всех элементов N-арного Дерева

0.00 (0%) 0 votes