Рубрики

Преобразовать произвольное двоичное дерево в дерево, которое содержит свойство Children Sum

Вопрос: Если дано произвольное двоичное дерево, преобразуйте его в двоичное дерево, которое содержит свойство Children Sum . Вы можете только увеличивать значения данных в любом узле (Вы не можете изменить структуру дерева и не можете уменьшить значение любого узла).

Например, приведенное ниже дерево не содержит свойство sum детей, преобразуйте его в дерево, которое содержит свойство.

             50
           /     \     
         /         \
       7             2
     / \             /\
   /     \          /   \
  3        5      1      30

Алгоритм:
Пройдите по указанному дереву в последующем порядке, чтобы преобразовать его, т. Е. Сначала измените левый и правый дочерние элементы, чтобы сохранить свойство sum детей, а затем измените родительский узел.

Пусть разница между данными узла и дочерней суммой будет разной.

     diff = node’s children sum - node’s data  

Если diff равен 0, тогда ничего не нужно делать.

Если diff> 0 (данные узла меньше суммы дочерних узлов) увеличивают данные узла на diff.

Если diff <0 (данные узла больше, чем сумма дочерних узлов), то увеличивают данные одного дочернего элемента. Мы можем увеличить левый или правый дочерний элемент, если они оба не равны NULL. Давайте всегда сначала увеличивать левого ребенка. Увеличение дочернего объекта изменяет свойство sum для дочернего поддерева, поэтому нам нужно также изменить левое поддерево. Таким образом, мы рекурсивно увеличиваем левого ребенка. Если левый потомок пуст, то мы рекурсивно вызываем increment () для правого потомка.

Запустим алгоритм для данного примера.

Сначала преобразуйте левое поддерево (с приращением от 7 до 8).

             50
           /     \     
         /         \
       8             2
     / \             /\
   /     \          /   \
  3        5      1      30

Затем преобразуйте правильное поддерево (с приращением от 2 до 31)

          50
        /    \     
      /        \
    8            31
   / \           / \
 /     \       /     \
3       5    1       30

Теперь преобразуйте корень, мы должны увеличить левое поддерево для преобразования корня.

          50
        /    \     
      /        \
    19           31
   / \           /  \
 /     \       /      \
14      5     1       30

Обратите внимание на последний шаг — мы увеличили с 8 до 19, а для исправления поддерева мы увеличили с 3 до 14.

Реализация:

C ++

/ * C ++ Программа для конвертации арибориала
бинарное дерево к дереву, которое содержит
детская сумма имущества * /
#include<iostream>
#include<bits/stdc++.h> 

using namespace std;

  

class node 

    public:

    int data; 

    node* left; 

    node* right; 

      

    / * Конструктор, который выделяет новый узел

    с данными данными и NULL влево и вправо

    указатели. * /

    node(int data)

    {

        this->data = data; 

        this->left = NULL; 

        this->right = NULL;

    }

}; 

  
/ * Эта функция используется
увеличить левое поддерево * /

void increment(node* node, int diff); 

  
/ * Эта функция меняет дерево
держать детей суммой собственности * /

void convertTree(node* node) 

    int left_data = 0, right_data = 0, diff; 

      

    / * Если дерево пустое или это лист

        затем верните ноль * /

    if (node == NULL || (node->left == NULL &&

                        node->right == NULL)) 

        return

    else

    

        / * конвертировать левое и правое поддеревья * /

        convertTree(node->left); 

        convertTree(node->right); 

      

        / * Если левого ребенка нет, то используется 0

        как данные левого ребенка * /

        if (node->left != NULL) 

        left_data = node->left->data; 

      

        / * Если нужного ребенка нет, то используется 0

        как данные правильного ребенка * /

        if (node->right != NULL) 

        right_data = node->right->data; 

      

        / * получить разность данных узла и суммы детей * /

        diff = left_data + right_data - node->data; 

      

        / * Если сумма дочерних узлов равна

        больше, чем данные узла * /

        if (diff > 0) 

        node->data = node->data + diff; 

      

        / * ЭТО ПРАВДА -> Если данные узла

        больше, чем сумма детей,

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

        if (diff < 0) 

        increment(node, -diff); // -diff используется, чтобы сделать diff положительным

    

  
/ * Эта функция используется
увеличить поддерево на diff * /

void increment(node* node, int diff) 

    / * ЕСЛИ левого ребенка нет

    NULL, затем увеличиваем его * /

    if(node->left != NULL) 

    

        node->left->data = node->left->data + diff; 

      

        // Рекурсивный вызов для исправления

        // потомки узла-> слева

        increment(node->left, diff); 

    

    else if (node->right != NULL) // остальное приращение правого потомка

    

        node->right->data = node->right->data + diff; 

      

        // Рекурсивный вызов для исправления

        // потомки узла-> вправо

        increment(node->right, diff); 

    

  
/ * Учитывая бинарное дерево,
printInorder () распечатывает его
обход по порядку * /

void printInorder(node* node) 

    if (node == NULL) 

        return

      

    / * первый рецидив на левом ребенке * /

    printInorder(node->left); 

      

    / * затем распечатать данные узла * /

    cout<<node->data<<" ";

      

    / * теперь возвращаемся на правильного ребенка * /

    printInorder(node->right); 

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

int main() 

    node *root = new node(50); 

    root->left = new node(7); 

    root->right = new node(2); 

    root->left->left = new node(3); 

    root->left->right = new node(5); 

    root->right->left = new node(1); 

    root->right->right = new node(30); 

      

    cout << "\nInorder traversal before conversion: " << endl; 

    printInorder(root);

      

    convertTree(root); 

      

    cout << "\nInorder traversal after conversion: " << endl; 

    printInorder(root); 

    return 0; 

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

С

/ * Программа для преобразования бинарного дерева

   дерево, которое содержит свойство sum детей *

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

  

struct node

{

  int data;

  struct node* left;

  struct node* right;

};

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

void increment(struct node* node, int diff);

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

 с данными данными и NULL влево и вправо

 указатели. * /

struct node* newNode(int data);

  
/ * Эта функция изменяет дерево для хранения суммы детей

   свойство */

void convertTree(struct node* node)

{

  int left_data = 0,  right_data = 0, diff;

  

  / * Если дерево пусто или это листовой узел, то

     вернуть истину * /

  if (node == NULL ||

     (node->left == NULL && node->right == NULL))

    return;

  else

  {

    / * конвертировать левое и правое поддеревья * /

    convertTree(node->left);

    convertTree(node->right);

  

    / * Если левого ребенка нет, то используется 0

       как данные левого ребенка * /

    if (node->left != NULL)

      left_data = node->left->data;

  

    / * Если нужного ребенка нет, то используется 0

      как данные правильного ребенка * /

    if (node->right != NULL)

      right_data = node->right->data;

  

    / * получить разность данных узла и суммы детей * /

    diff = left_data + right_data - node->data;

  

    / * Если сумма дочерних узлов больше, чем данные узла * /

    if (diff > 0)

       node->data = node->data + diff;

  

    / * ЭТО ПРАВДА -> Если данные узла больше суммы детей,

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

    if (diff < 0)

      increment(node, -diff);  // -diff используется, чтобы сделать diff положительным

  }

}

  
/ * Эта функция используется для увеличения поддерева на diff * /

void increment(struct node* node, int diff)

{

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

  if(node->left != NULL)

  {

    node->left->data = node->left->data + diff;

  

    // Рекурсивный вызов для исправления потомков node-> left

    increment(node->left, diff);  

  }

  else if (node->right != NULL) // остальное приращение правого потомка

  {

    node->right->data = node->right->data + diff;

  

    // Рекурсивный вызов для исправления потомков node-> right

    increment(node->right, diff);

  }

}

  
/ * Учитывая двоичное дерево, printInorder () распечатывает его

   обход по порядку * /

void printInorder(struct node* node)

{

  if (node == NULL)

    return;

  

  / * первый рецидив на левом ребенке * /

  printInorder(node->left);

  

  / * затем распечатать данные узла * /

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

  

  / * теперь возвращаемся на правильного ребенка * /

  printInorder(node->right);

}

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

 с данными данными и NULL влево и вправо

 указатели. * /

struct node* newNode(int data)

{

  struct node* node =

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

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  return(node);

}

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

int main()

{

  struct node *root = newNode(50);

  root->left        = newNode(7);

  root->right       = newNode(2);

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

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

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

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

  

  printf("\n Inorder traversal before conversion ");

  printInorder(root);

  

  convertTree(root);

  

  printf("\n Inorder traversal after conversion ");

  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;

    / * Эта функция изменяет дерево для хранения суммы детей

       свойство */

   

    void convertTree(Node node) 

    {

        int left_data = 0, right_data = 0, diff;

   

        / * Если дерево пусто или это листовой узел, то

         вернуть истину * /

        if (node == null

                || (node.left == null && node.right == null))

            return;

        else

        {

            / * конвертировать левое и правое поддеревья * /

            convertTree(node.left);

            convertTree(node.right);

         

            / * Если левого ребенка нет, то используется 0

             как данные левого ребенка * /

            if (node.left != null)

                left_data = node.left.data;

              

            / * Если нужного ребенка нет, то используется 0

             как данные правильного ребенка * /

            if (node.right != null)

                right_data = node.right.data;

   

            / * получить разность данных узла и суммы детей * /

            diff = left_data + right_data - node.data;

   

            / * Если сумма дочерних узлов больше, чем данные узла * /

            if (diff > 0)

                node.data = node.data + diff;

   

            / * ЭТО ПРАВДА -> Если данные узла больше, чем дочерние

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

            if (diff < 0)

              

                // -diff используется, чтобы сделать diff положительным

                increment(node, -diff);  

        }

    }

   

    / * Эта функция используется для увеличения поддерева на diff * /

    void increment(Node node, int diff) 

    {

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

        if (node.left != null

        {

            node.left.data = node.left.data + diff;

   

            // Рекурсивный вызов для исправления потомков node-> left

            increment(node.left, diff);

        

        else if (node.right != null) // остальное приращение правого потомка

        {

            node.right.data = node.right.data + diff;

   

            // Рекурсивный вызов для исправления потомков node-> right

            increment(node.right, diff);

        }

    }

   

    / * Учитывая двоичное дерево, printInorder () распечатывает его

     обход по порядку * /

    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(50);

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

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

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

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

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

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

   

        System.out.println("Inorder traversal before conversion is :");

        tree.printInorder(tree.root);

   

        tree.convertTree(tree.root);

        System.out.println("");

   

        System.out.println("Inorder traversal after conversion is :");

        tree.printInorder(tree.root);

   

    }

}

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

python3

# Программа для конвертирования арифитарного бинарного дерева
# к дереву, которое содержит свойство sum детей

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

class newNode: 

  

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

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

  
# Эта функция меняет дерево на
# держать детей суммой собственности

def convertTree(node):

  

    left_data = 0

    right_data = 0

    diff=0

  

    # Если дерево пусто или это

    # листовой узел, затем верните true

    if (node == None or (node.left == None and

                         node.right == None)):

        return

      

    else:

          

        "" "преобразовать левое и правое поддеревья" ""

        convertTree(node.left)

        convertTree(node.right)

  

    "" "Если левого ребенка нет, то 0

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

    if (node.left != None):

        left_data = node.left.data

  

    "" "Если правильного ребенка нет, то 0

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

    if (node.right != None):

        right_data = node.right.data

  

    "" "получить разницу данных узла

        а дети суммируют "" "

    diff = left_data + right_data - node.data

  

    "" "Если сумма дочерних узлов больше

        чем данные узла "" "

    if (diff > 0):

        node.data = node.data + diff

  

    "" "ЭТО ПРОСТО -. Если данные узла

    больше, чем сумма детей, то приращение

    поддерево с помощью diff "" "

    if (diff < 0):

        increment(node, -diff) # -дифф используется для

                               # сделать разницу положительной

  
"" "Эта функция используется для увеличения

    поддерево с помощью diff "" "

def increment(node, diff):

  

    "" "ЕСЛИ левого ребенка нет

        затем увеличить его "" "

    if(node.left != None):

        node.left.data = node.left.data + diff

  

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

        # потомки node.left

        increment(node.left, diff) 

  

    elif(node.right != None): # Остальное приращение правого ребенка

        node.right.data = node.right.data + diff

  

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

        # потомки node.right

        increment(node.right, diff)

  
"" "Учитывая двоичное дерево, printInorder ()
распечатывает его обход по порядку "" "

def printInorder(node):

  

    if (node == None):

        return

  

    "" "первый рецидив на левом ребенке" ""

    printInorder(node.left)

  

    "" "затем распечатайте данные узла" ""

    print(node.data,end=" ")

  

    "" "теперь возвращаемся на нужного ребенка" ""

    printInorder(node.right)

  
Код водителя

if __name__ == '__main__':

    root = newNode(50)

    root.left     = newNode(7)

    root.right     = newNode(2)

    root.left.left = newNode(3)

    root.left.right = newNode(5)

    root.right.left = newNode(1)

    root.right.right = newNode(30)

  

    print("Inorder traversal before conversion")

    printInorder(root)

  

    convertTree(root)

  

    print("\nInorder traversal after conversion ")

    printInorder(root)

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

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 void convertTree(Node node)

{

    int left_data = 0, right_data = 0, diff;

  

    / * Если дерево пустое или это лист

    затем верните ноль * /

    if (node == null || (node.left == null && 

                         node.right == null))

    {

        return;

    }

    else

    {

        / * конвертировать левое и правое поддеревья * /

        convertTree(node.left);

        convertTree(node.right);

  

        / * Если левого ребенка нет, то

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

        if (node.left != null)

        {

            left_data = node.left.data;

        }

  

        / * Если правильного ребенка нет, то

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

        if (node.right != null)

        {

            right_data = node.right.data;

        }

  

        / * получить разницу данных узла

           и дети сумма * /

        diff = left_data + right_data - node.data;

  

        / * Если сумма дочерних узлов больше

           чем данные узла * /

        if (diff > 0)

        {

            node.data = node.data + diff;

        }

  

        / * ЭТО ПРАВДА -> Если данные узла

        больше, чем сумма детей, то приращение

        поддерево по diff * /

        if (diff < 0)

        {

  

            // -diff используется, чтобы сделать diff положительным

            increment(node, -diff);

        }

    }

}

  
/ * Эта функция используется для увеличения
поддерево по diff * /

public virtual void increment(Node node, int diff)

{

    / * Если оставленный ребенок не равен NULL,

    увеличить его * /

    if (node.left != null)

    {

        node.left.data = node.left.data + diff;

  

        // Рекурсивный вызов для исправления

        // потомки узла-> слева

        increment(node.left, diff);

    }

    else if (node.right != null) // остальное приращение правого потомка

    {

        node.right.data = node.right.data + diff;

  

        // Рекурсивный вызов для исправления

        // потомки узла-> вправо

        increment(node.right, diff);

    }

}

  
/ * Учитывая двоичное дерево, printInorder ()
распечатывает его обход по порядку * /

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(50);

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

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

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

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

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

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

  

    Console.WriteLine("Inorder traversal "

                  "before conversion is :");

    tree.printInorder(tree.root);

  

    tree.convertTree(tree.root);

    Console.WriteLine("");

  

    Console.WriteLine("Inorder traversal "

                   "after conversion is :");

    tree.printInorder(tree.root);

}
}

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

Выход :

Inorder traversal before conversion is :
3 7 5 50 1 2 30
Inorder traversal after conversion is :
14 19 5 50 1 31 30

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

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

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

Преобразовать произвольное двоичное дерево в дерево, которое содержит свойство Children Sum

0.00 (0%) 0 votes