Рубрики

Добавить все большие значения для каждого узла в данном BST

Для заданного значения B B inary S earch T (BST) измените его так, чтобы все большие значения в данном BST добавлялись к каждому узлу. Например, рассмотрим следующий BST.

              50
           /      \
         30        70
        /   \      /  \
      20    40    60   80 

The above tree should be modified to following 

              260
           /      \
         330        150
        /   \       /  \
      350   300    210   80

Простой метод решения этой проблемы — найти сумму всех больших значений для каждого узла. Этот метод занял бы O (n ^ 2) времени.
Мы можем сделать это с помощью одного обхода . Идея состоит в том, чтобы использовать следующее свойство BST. Если мы сделаем обратный обход Inorder BST, мы получим все узлы в порядке убывания. Мы делаем обратный обход Inorder и отслеживаем сумму всех посещенных узлов, мы добавляем эту сумму к каждому узлу.

C ++

// C ++ программа для добавления всех больших значений в каждом узле BST
#include <bits/stdc++.h>

using namespace std; 

  

class Node 

    public:

    int data; 

    Node *left, *right; 

}; 

  
// Вспомогательная функция для создания нового узла BST

Node *newNode(int item) 

    Node *temp = new Node();

    temp->data = item; 

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

    return temp; 

  
// Рекурсивная функция для добавления всех больших значений в каждом узле

void modifyBSTUtil(Node *root, int *sum) 

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

    if (root == NULL) return

  

    // Повтор для правого поддерева

    modifyBSTUtil(root->right, sum); 

  

    // Теперь * сумма имеет сумму узлов в правом поддереве, добавляем

    // root-> data для суммирования и обновления root-> data

    *sum = *sum + root->data; 

    root->data = *sum; 

  

    // Повтор для левого поддерева

    modifyBSTUtil(root->left, sum); 

  
// Оболочка над modifyBSTUtil ()

void modifyBST(Node *root) 

    int sum = 0; 

    modifyBSTUtil(root, &sum); 

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

void inorder(Node *root) 

    if (root != NULL) 

    

        inorder(root->left); 

        cout<<root->data<<" "

        inorder(root->right); 

    

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

Node* insert(Node* node, int data) 

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

    if (node == NULL) return newNode(data); 

  

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

    if (data <= node->data) 

        node->left = insert(node->left, data); 

    else

        node->right = insert(node->right, data); 

  

    / * вернуть (неизмененный) указатель узла * /

    return node; 

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

int main() 

    / * Давайте создадим следующий BST

            50

        / /

        30 70

        / / / /

    20 40 60 80 *

    Node *root = NULL; 

    root = insert(root, 50); 

    insert(root, 30); 

    insert(root, 20); 

    insert(root, 40); 

    insert(root, 70); 

    insert(root, 60); 

    insert(root, 80); 

  

    modifyBST(root); 

  

    // печать inoder tarversal модифицированного BST

    inorder(root); 

  

    return 0; 

}

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

С

// C программа для добавления всех больших значений в каждом узле BST
#include<stdio.h>
#include<stdlib.h>

  

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Вспомогательная функция для создания нового узла BST

struct Node *newNode(int item)

{

    struct Node *temp =  (struct Node *)malloc(sizeof(struct Node));

    temp->data = item;

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

    return temp;

}

  
// Рекурсивная функция для добавления всех больших значений в каждом узле

void modifyBSTUtil(struct Node *root, int *sum)

{

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

    if (root == NULL)  return;

  

    // Повтор для правого поддерева

    modifyBSTUtil(root->right, sum);

  

    // Теперь * сумма имеет сумму узлов в правом поддереве, добавляем

    // root-> data для суммирования и обновления root-> data

    *sum = *sum + root->data;

    root->data = *sum;

  

    // Повтор для левого поддерева

    modifyBSTUtil(root->left, sum);

}

  
// Оболочка над modifyBSTUtil ()

void modifyBST(struct Node *root)

{

    int sum = 0;

    modifyBSTUtil(root, &sum);

}

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

void inorder(struct Node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

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

        inorder(root->right);

    }

}

  
/ * Служебная функция для вставки нового узла с данными в BST * /

struct Node* insert(struct Node* node, int data)

{

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

    if (node == NULL) return newNode(data);

  

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

    if (data <= node->data)

        node->left  = insert(node->left, data);

    else

        node->right = insert(node->right, data);

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

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

int main()

{

    / * Давайте создадим следующий BST

              50

           / /

          30 70

         / / / /

       20 40 60 80 *

    struct Node *root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

  

    modifyBST(root);

  

    // печать inoder tarversal модифицированного BST

    inorder(root);

  

    return 0;

}

Джава

// Java-код для добавления всех больших значений
// каждый узел в данном BST

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

class Node {

  

    int data;

    Node left, right;

  

    Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

class BinarySearchTree {

  

    // Корень BST

    Node root;

  

    // Конструктор

    BinarySearchTree()

    {

        root = null;

    }

  

    // По обходу дерева

    void inorder()

    {

        inorderUtil(this.root);

    }

  

    // Функция полезности для обхода по порядку

    // дерево

    void inorderUtil(Node node)

    {

        if (node == null)

            return;

  

        inorderUtil(node.left);

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

        inorderUtil(node.right);

    }

  

    // добавление нового узла

    public void insert(int data)

    {

        this.root = this.insertRec(this.root, data);

    }

      

    / * Утилита для вставки нового узла с

    данные приведены в BST * /

    Node insertRec(Node node, int data)

    {   

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

        if (node == null) {

            this.root = new Node(data);

            return this.root;

        }

  

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

        if (data <= node.data) {

            node.left = this.insertRec(node.left, data);

        } else {

            node.right = this.insertRec(node.right, data);

        }

        return node;

    }

  

    // Этот класс инициализирует значение суммы до 0

    public class Sum {

        int sum = 0;

    }

  

    // Рекурсивная функция для добавления всех больших значений в

    // каждый узел

    void modifyBSTUtil(Node node, Sum S)

    {

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

        if (node == null)

            return;

              

        // Повтор для правого поддерева

        this.modifyBSTUtil(node.right, S); 

          

        // Теперь * сумма имеет сумму узлов в правом поддереве, добавляем

        // root-> data для суммирования и обновления root-> data

        S.sum = S.sum + node.data;

        node.data = S.sum;

          

        // Повтор для левого поддерева

        this.modifyBSTUtil(node.left, S); 

    }

  

    // Оболочка над modifyBSTUtil ()

    void modifyBST(Node node)

    {

        Sum S = new Sum();

        this.modifyBSTUtil(node, S);

    }

  

    // Функция драйвера

    public static void main(String[] args)

    {

        BinarySearchTree tree = new BinarySearchTree();

          

          / * Давайте создадим следующий BST

              50

           / /

          30 70

         / / / /

       20 40 60 80 *

         

        tree.insert(50);

        tree.insert(30);

        tree.insert(20);

        tree.insert(40);

        tree.insert(70);

        tree.insert(60);

        tree.insert(80);

  

        tree.modifyBST(tree.root);

          

        // печать inoder tarversal модифицированного BST

        tree.inorder();

    }

}

  
// Этот код предоставлен Камалем Равалом

python3

# Python3 программа для добавления всех больших значений
# в каждом узле BST

  
# Полезная функция для создания
# новый узел BST

class newNode: 

  

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

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

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

def modifyBSTUtil(root, Sum):

      

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

    if root == None:

        return

  

    # Recur для правого поддерева

    modifyBSTUtil(root.right, Sum

  

    # Теперь Sum [0] имеет сумму узлов справа

    # поддерево, добавьте root.data к сумме и

    # update root.data

    Sum[0] = Sum[0] + root.data 

    root.data = Sum[0]

  

    # Recur для левого поддерева

    modifyBSTUtil(root.left, Sum)

  
# Оболочка над modifyBSTUtil ()

def modifyBST(root):

    Sum = [0]

    modifyBSTUtil(root, Sum)

  
# Полезная функция, чтобы сделать заказ
# обход BST

def inorder(root):

    if root != None:

        inorder(root.left)

        print(root.data,end=" "

        inorder(root.right)

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

def insert(node, data):

      

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

    if node == None:

        return newNode(data)

  

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

    if data <= node.data: 

        node.left = insert(node.left, data) 

    else:

        node.right = insert(node.right, data)

  

    # вернуть (неизмененный) указатель узла

    return node

  
Код водителя

if __name__ == '__main__':

      

    # Давайте создадим следующий BST

    № 50

    # / /

    # 30 70

    # / / / /

    # 20 40 60 80

    root = None

    root = insert(root, 50

    insert(root, 30

    insert(root, 20

    insert(root, 40

    insert(root, 70

    insert(root, 60

    insert(root, 80

  

    modifyBST(root) 

  

    # распечатать inoder tarversal из

    # модифицированный BST

    inorder(root)

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

C #

using System;

  
// C # код для добавления всех больших значений
// каждый узел в данном BST

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

public class Node

{

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class BinarySearchTree

{

  

    // Корень BST

    public Node root;

  

    // Конструктор

    public BinarySearchTree()

    {

        root = null;

    }

  

    // По обходу дерева

    public virtual void inorder()

    {

        inorderUtil(this.root);

    }

  

    // Функция полезности для обхода по порядку

    // дерево

    public virtual void inorderUtil(Node node)

    {

        if (node == null)

        {

            return;

        }

  

        inorderUtil(node.left);

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

        inorderUtil(node.right);

    }

  

    // добавление нового узла

    public virtual void insert(int data)

    {

        this.root = this.insertRec(this.root, data);

    }

  

    / * Утилита для вставки нового узла с

    данные приведены в BST * /

    public virtual Node insertRec(Node node, int data)

    {

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

        if (node == null)

        {

            this.root = new Node(data);

            return this.root;

        }

  

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

        if (data <= node.data)

        {

            node.left = this.insertRec(node.left, data);

        }

        else

        {

            node.right = this.insertRec(node.right, data);

        }

        return node;

    }

  

    // Этот класс инициализирует значение суммы до 0

    public class Sum

    {

        private readonly BinarySearchTree outerInstance;

  

        public Sum(BinarySearchTree outerInstance)

        {

            this.outerInstance = outerInstance;

        }

  

        public int sum = 0;

    }

  

    // Рекурсивная функция для добавления всех больших значений в

    // каждый узел

    public virtual void modifyBSTUtil(Node node, Sum S)

    {

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

        if (node == null)

        {

            return;

        }

  

        // Повтор для правого поддерева

        this.modifyBSTUtil(node.right, S);

  

        // Теперь * сумма имеет сумму узлов в правом поддереве, добавляем

        // root-> data для суммирования и обновления root-> data

        S.sum = S.sum + node.data;

        node.data = S.sum;

  

        // Повтор для левого поддерева

        this.modifyBSTUtil(node.left, S);

    }

  

    // Оболочка над modifyBSTUtil ()

    public virtual void modifyBST(Node node)

    {

        Sum S = new Sum(this);

        this.modifyBSTUtil(node, S);

    }

  

    // Функция драйвера

    public static void Main(string[] args)

    {

        BinarySearchTree tree = new BinarySearchTree();

  

          / * Давайте создадим следующий BST

              50

           / /

          30 70

         / / / /

       20 40 60 80 *

  

        tree.insert(50);

        tree.insert(30);

        tree.insert(20);

        tree.insert(40);

        tree.insert(70);

        tree.insert(60);

        tree.insert(80);

  

        tree.modifyBST(tree.root);

  

        // печать inoder tarversal модифицированного BST

        tree.inorder();

    }

}

  

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


Выход

350 330 300 260 210 150 80

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

В качестве примечания, мы также можем использовать обратный обход Inorder, чтобы найти k-й по величине элемент в BST.

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

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

Добавить все большие значения для каждого узла в данном BST

0.00 (0%) 0 votes