Рубрики

Диагональная сумма двоичного дерева

Рассмотрим линии наклона -1, проходящие между узлами (пунктирные линии на диаграмме ниже). Диагональная сумма в двоичном дереве представляет собой сумму данных всех узлов, лежащих между этими строками. Для заданного двоичного дерева выведите все диагональные суммы.

Для следующего дерева ввода вывод должен быть 9, 19, 42.
9 — сумма 1, 3 и 5.
19 — сумма 2, 6, 4 и 7.
42 — это сумма 9, 10, 11 и 12.

Алгоритм:
Идея состоит в том, чтобы отслеживать вертикальное расстояние от верхней диагонали, проходящей через корень. Увеличиваем расстояние по вертикали и спускаемся до следующей диагонали.
1. Добавьте корень с вертикальным расстоянием как 0 в очередь.
2. Обработка суммы всех правильных детей и прав правильных детей и так далее.
3. Добавьте левый дочерний текущий узел в очередь для последующей обработки. Вертикальное расстояние левого ребенка — это вертикальное расстояние текущего узла плюс 1.
4. Продолжайте делать 2-й, 3-й и 4-й шаг, пока очередь не опустеет.

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

C ++

// C ++ Программа для поиска диагонали
// сумма в двоичном дереве
#include <iostream>
#include <stdlib.h>
#include <map>

using namespace std;

  

struct Node

{

    int data;

    struct Node* left;

    struct Node* 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;

}

  
// корень - корень двоичного дерева
// vd - вертикальное расстояние по диагонали
// diagonalSum - карта для хранения диагонали
// Sum (Передано по ссылке)

void diagonalSumUtil(struct Node* root,

                int vd, map<int, int> &diagonalSum)

{

    if(!root)

        return;

          

    diagonalSum[vd] += root->data;

  

    // увеличить вертикальное расстояние, если левый ребенок

    diagonalSumUtil(root->left, vd + 1, diagonalSum);

  

    // вертикальное расстояние остается тем же для правого ребенка

    diagonalSumUtil(root->right, vd, diagonalSum);

}

  
// Функция для вычисления диагонали
// сумма заданного бинарного дерева

void diagonalSum(struct Node* root)

{

  

    // создаем карту для хранения диагональной суммы

    map<int, int> diagonalSum; 

      

    diagonalSumUtil(root, 0, diagonalSum);

  

    map<int, int>::iterator it;

        cout << "Diagonal sum in a binary tree is - ";

      

    for(it = diagonalSum.begin();

                it != diagonalSum.end(); ++it)

    {

        cout << it->second << " ";

    }

}

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

int main()

{

    struct Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

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

  

    diagonalSum(root);

  

    return 0;

}

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

Джава

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

import java.util.*;

import java.util.Map.Entry;

  
// Узел дерева

class TreeNode

{

    int data; // данные узла

    int vd; // вертикальное расстояние по диагонали

    TreeNode left, right; // левая и правая дочерняя ссылка

  

    // Конструктор узла дерева

    public TreeNode(int data)

    {

        this.data = data;

        vd = Integer.MAX_VALUE;

        left = right = null;

    }

}

  
// Класс дерева

class Tree

{

    TreeNode root;// Корень дерева

  

    // Конструктор дерева

    public Tree(TreeNode root)  {  this.root = root;  }

  

    // метод диагональной суммы

    public void diagonalSum()

    {

        // Очередь, в которой хранятся узлы дерева

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

  

        // Карта для хранения суммы данных узла, лежащих по диагонали

        Map<Integer, Integer> map = new TreeMap<>();

  

        // Назначаем вертикальное расстояние корня как 0.

        root.vd = 0;

  

        // Добавить корневой узел в очередь

        queue.add(root);

  

        // Цикл пока очередь не пуста

        while (!queue.isEmpty())

        {

            // Удалить узел переднего дерева из очереди.

            TreeNode curr = queue.remove();

  

            // Получить вертикальное расстояние от удаленного узла.

            int vd = curr.vd;

  

            // Сумма по правому-дочернему узлу, right-of-right-child этого узла

            // и так далее

            while (curr != null)

            {

                int prevSum = (map.get(vd) == null)? 0: map.get(vd);

                map.put(vd, prevSum + curr.data);

  

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

                // это в очередь для дальнейшей обработки.

                if (curr.left != null)

                {

                    curr.left.vd = vd+1;

                    queue.add(curr.left);

                }

  

                // Перейти к правому дочернему узлу текущего узла.

                curr = curr.right;

            }

        }

  

        // Сделать запись набора из карты.

        Set<Entry<Integer, Integer>> set = map.entrySet();

  

        // Сделать итератор

        Iterator<Entry<Integer, Integer>> iterator = set.iterator();

  

        // Обход элементов карты с помощью итератора.

         System.out.print("Diagonal sum in a binary tree is - ");

        while (iterator.hasNext())

        {

            Map.Entry<Integer, Integer> me = iterator.next();

  

            System.out.print(me.getValue()+" ");

        }

    }

}

  
// Класс водителя

public class DiagonalSum

{

    public static void main(String[] args)

    {

        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);

        root.right = new TreeNode(3);

        root.left.left = new TreeNode(9);

        root.left.right = new TreeNode(6);

        root.right.left = new TreeNode(4);

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

        root.right.left.left = new TreeNode(12);

        root.right.left.right = new TreeNode(7);

        root.left.right.left = new TreeNode(11);

        root.left.left.right = new TreeNode(10);

        Tree tree = new Tree(root);

        tree.diagonalSum();

    }

}

python3

# Программа для поиска диагональной суммы в двоичном дереве

  

class newNode: 

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

          
# Функция для вычисления высоты и
# root - корень двоичного дерева
# vd - расстояние по вертикали по диагонали
# diagonalSum - карта для хранения диагонали
# Сумма (передано по ссылке)

def diagonalSumUtil(root, vd, diagonalSum) :

  

    if(not root): 

        return

          

    if vd not in diagonalSum:

        diagonalSum[vd] = 0

    diagonalSum[vd] += root.data 

  

    # увеличить вертикальное расстояние

    # если оставить ребенка

    diagonalSumUtil(root.left, vd + 1

                          diagonalSum) 

  

    # вертикальное расстояние остается тем же

    # для правильного ребенка

    diagonalSumUtil(root.right, vd,

                       diagonalSum) 

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

def diagonalSum(root) :

  

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

    diagonalSum = dict() 

      

    diagonalSumUtil(root, 0, diagonalSum) 

  

    print("Diagonal sum in a binary tree is - "

                                       end = "")

      

    for it in diagonalSum:

        print(diagonalSum[it], end = " ")

          
Код водителя

if __name__ == '__main__':

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

    root.left.left = newNode(9

    root.left.right = newNode(6

    root.right.left = newNode(4

    root.right.right = newNode(5

    root.right.left.right = newNode(7

    root.right.left.left = newNode(12

    root.left.right.left = newNode(11

    root.left.left.right = newNode(10

  

    diagonalSum(root)

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

Выход:

 Диагональная сумма в бинарном дереве - 9 19 42 

Упражнение:
Эта проблема была для диагоналей сверху вниз и наклона -1. Попробуйте ту же проблему для склона +1.

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

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

Диагональная сумма двоичного дерева

0.00 (0%) 0 votes