Рубрики

Преобразовать данное дерево в его дерево сумм

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

Например, следующее дерево

                  10
               /      \
             -2        6
           /   \      /  \ 
         8     -4    7    5

следует изменить на

                 20(4-2+12+6)
               /      \
         4(8-4)      12(7+5)
           /   \      /  \ 
         0      0    0    0

Решение:
Сделайте обход данного дерева. При обходе сохраните старое значение текущего узла, рекурсивно вызовите левое и правое поддеревья и измените значение текущего узла как сумму значений, возвращаемых рекурсивными вызовами. Наконец, возвращаем сумму нового значения и значения (которая является суммой значений в поддереве, укорененном в этом узле).

C ++

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

using namespace std;

  
/ * Древовидная структура * /

class node 

    public:

int data; 

node *left; 
node *right; 
}; 

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

int toSumTree(node *Node) 

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

    if(Node == NULL) 

    return 0; 

  

    // Сохраняем старое значение

    int old_val = Node->data; 

  

    // рекурсивный вызов left и

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

    // новое значение этого узла

    Node->data = toSumTree(Node->left) + toSumTree(Node->right); 

  

    // Возвращаем сумму значений узлов

    // в левом и правом поддеревьях и

    // старое_значение этого узла

    return Node->data + old_val; 

  
// Утилита для печати
// обход порядка двоичного дерева

void printInorder(node* Node) 

    if (Node == NULL) 

        return

    printInorder(Node->left); 

    cout<<" "<<Node->data; 

    printInorder(Node->right); 

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

node* newNode(int data) 

    node *temp = new node; 

    temp->data = data; 

    temp->left = NULL; 

    temp->right = NULL; 

      

    return temp; 

  
/ * Код водителя * /

int main() 

    node *root = NULL; 

    int x; 

      

    / * Построение дерева приведено на рисунке выше * /

    root = newNode(10); 

    root->left = newNode(-2); 

    root->right = newNode(6); 

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

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

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

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

      

    toSumTree(root); 

      

    // Вывести порядок обхода преобразованного

    // дерево для проверки результата toSumTree ()

    cout<<"Inorder Traversal of the resultant tree is: \n"

    printInorder(root); 

    return 0; 

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

С

#include<stdio.h>

  
/ * Древовидная структура * /

struct node

{

  int data;

  struct node *left;

  struct node *right;

};

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

int toSumTree(struct node *node)

{

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

    if(node == NULL)

      return 0;

  

    // Сохраняем старое значение

    int old_val = node->data;

  

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

    // новое значение этого узла

    node->data = toSumTree(node->left) + toSumTree(node->right);

  

    // Возвращаем сумму значений узлов в левом и правом поддеревьях и

    // старое_значение этого узла

    return node->data + old_val;

}

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

void printInorder(struct node* node)

{

     if (node == NULL)

          return;

     printInorder(node->left);

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

     printInorder(node->right);

}

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

struct node* newNode(int data)

{

  struct node *temp = new struct node;

  temp->data = data;

  temp->left = NULL;

  temp->right = NULL;

  

  return temp;

}

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

int main()

{

  struct node *root = NULL;

  int x;

  

  / * Построение дерева приведено на рисунке выше * /

  root = newNode(10);

  root->left = newNode(-2);

  root->right = newNode(6);

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

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

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

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

  

  toSumTree(root);

  

  // Вывести порядок обхода преобразованного дерева для проверки результата toSumTree ()

  printf("Inorder Traversal of the resultant tree is: \n");

  printInorder(root);

  

  getchar();

  return 0;

}

Джава

// Java-программа для преобразования дерева в дерево сумм

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

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

    // значения узлов в левом и правом поддеревьях в исходном дереве

    int toSumTree(Node node) 

    {

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

        if (node == null)

            return 0;

   

        // Сохраняем старое значение

        int old_val = node.data;

   

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

        // как новое значение этого узла

        node.data = toSumTree(node.left) + toSumTree(node.right);

   

        // Возвращаем сумму значений узлов в левом и правом поддеревьях

        // и old_value этого узла

        return node.data + old_val;

    }

   

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

    void printInorder(Node node) 

    {

        if (node == null)

            return;

        printInorder(node.left);

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

        printInorder(node.right);

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

   

        / * Построение дерева приведено на рисунке выше * /

        tree.root = new Node(10);

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

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

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

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

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

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

   

        tree.toSumTree(tree.root);

   

        // Вывести порядок обхода преобразованного дерева в результат теста

        // of toSumTree ()

        System.out.println("Inorder Traversal of the resultant tree is:");

        tree.printInorder(tree.root);

    }

}

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

python3

# Python3 программа для преобразования дерева
# в дерево сумм

  
# Определение узла

class node: 

      

    def __init__(self, data): 

        self.left = None

        self.right = None

        self.data = data 

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

def toSumTree(Node) :

      

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

    if(Node == None) :

        return 0

  

    # Сохранить старое значение

    old_val = Node.data 

  

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

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

    # новое значение этого узла

    Node.data = toSumTree(Node.left) + \

                toSumTree(Node.right) 

  

    # Вернуть сумму значений узлов

    # в левом и правом поддеревьях и

    # old_value этого узла

    return Node.data + old_val 

  
# Утилита для печати
# порядок обхода двоичного дерева

def printInorder(Node) :

    if (Node == None) :

        return

    printInorder(Node.left) 

    print(Node.data, end = " "

    printInorder(Node.right) 

      
# Служебная функция для создания нового узла двоичного дерева

def newNode(data) :

    temp = node(0

    temp.data = data 

    temp.left = None

    temp.right = None

      

    return temp 

  
Код водителя

if __name__ == "__main__"

    root = None

    x = 0

      

    # Построение дерева приведено на рисунке выше

    root = newNode(10

    root.left = newNode(-2

    root.right = newNode(6

    root.left.left = newNode(8

    root.left.right = newNode(-4

    root.right.left = newNode(7

    root.right.right = newNode(5

      

    toSumTree(root) 

      

    # Печать по порядку обхода преобразованного

    # дерево для проверки результата toSumTree ()

    print("Inorder Traversal of the resultant tree is: "

    printInorder(root) 

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

C #

// C # программа для преобразования дерева
// в дерево сумм

using System;

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

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

public virtual int toSumTree(Node node)

{

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

    if (node == null)

    {

        return 0;

    }

  

    // Сохраняем старое значение

    int old_val = node.data;

  

    // рекурсивный вызов left и

    // правильные поддеревья и сохраняем сумму

    // как новое значение этого узла

    node.data = toSumTree(node.left) + 

                toSumTree(node.right);

  

    // Возвращаем сумму значений узлов

    // в левом и правом поддеревьях old_value

    // этого узла

    return node.data + old_val;

}

  
// Утилита для печати
// обход порядка двоичного дерева

public virtual void printInorder(Node node)

{

    if (node == null)

    {

        return;

    }

    printInorder(node.left);

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

    printInorder(node.right);

}

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

public static void Main(string[] args)

{

    GFG tree = new GFG();

  

    / * Построение дерева дано в

       приведенная выше цифра *

    tree.root = new Node(10);

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

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

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

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

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

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

  

    tree.toSumTree(tree.root);

  

    // Распечатать порядок обхода

    // преобразовал дерево в результат теста toSumTree ()

    Console.WriteLine("Inorder Traversal of "

                     "the resultant tree is:");

    tree.printInorder(tree.root);

}
}

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


Выход:

Inorder Traversal of the resultant tree is:
0 4 0 20 0 12 0

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

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

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

Преобразовать данное дерево в его дерево сумм

0.00 (0%) 0 votes