Рубрики

Преобразовать BST в большую сумму дерева

Получив BST, преобразуйте его в дерево с большей суммой, где каждый узел содержит сумму всех узлов, больших этого узла.

Мы настоятельно рекомендуем свернуть браузер и сначала попробовать это самостоятельно.

Метод 1 (Наивный):
Этот метод не требует, чтобы дерево было BST. Ниже приведены шаги.
1. Обход узла за узлом (порядок, предварительный заказ и т. Д.)
2. Для каждого узла найдите все узлы больше, чем у текущего узла, суммируйте значения. Храните все эти суммы.
3. Замените каждое значение узла соответствующей суммой, перемещаясь в том же порядке, что и на шаге 1.
Это занимает O (n ^ 2) сложность времени.

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

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

using namespace std;

  
// узел BST

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Утилита для создания нового узла Binary Tree

struct Node *newNode(int item)

{

    struct Node *temp =  new Node;

    temp->data = item;

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

    return temp;

}

  
// Рекурсивная функция для преобразования BST в дерево сумм.
// Эта функция пересекает дерево в обратном порядке, так
// что мы посетили все большие ключевые узлы текущего
// посещаемый узел

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

{

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

   if (root == NULL)  return;

  

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

   transformTreeUtil(root->right, sum);

  

   // Обновить сумму

   *sum = *sum + root->data;

  

   // Сохранить старую сумму в текущем узле

   root->data = *sum - root->data;

  

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

   transformTreeUtil(root->left, sum);

}

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

void transformTree(struct Node *root)

{

    int sum = 0; // Инициализировать сумму

    transformTreeUtil(root, &sum);

}

  
// Вспомогательная функция для печати обхода
// двоичное дерево

void printInorder(struct Node *root)

{

    if (root == NULL) return;

  

    printInorder(root->left);

    cout << root->data << " ";

    printInorder(root->right);

}

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

int main()

{

    struct Node *root = newNode(11);

    root->left = newNode(2);

    root->right = newNode(29);

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

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

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

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

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

  

    cout << "Inorder Traversal of given tree\n";

    printInorder(root);

  

    transformTree(root);

  

    cout << "\n\nInorder Traversal of transformed tree\n";

    printInorder(root);

  

    return 0;

}

Выход:

Inorder Traversal of given tree
1 2 7 11 15 29 35 40

Inorder Traversal of transformed tree
139 137 130 119 104 75 40 0

Временная сложность этого метода составляет O (n), так как он делает простой обход дерева.

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

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

Преобразовать BST в большую сумму дерева

0.00 (0%) 0 votes