Сумма последних N узлов в двоичном дереве поиска - PullRequest
Новая
       86

Сумма последних N узлов в двоичном дереве поиска

0 голосов
/ 05 мая 2020

Я хочу написать функцию, которая получает число N и двоичное дерево поиска, тогда функция должна просуммировать значения последних N узлов дерева. от большего к меньшему значению узлов. Я не могу использовать вспомогательные функции или переменную stati c.

example

Например, если функция получает это двоичное дерево поиска и значение N равно 3, то вывод будет быть: 7 + 6 + 5. И если N его 4, это будет: 7 + 6 + 5 + 3.

Есть идеи для алгоритма?

1 Ответ

2 голосов
/ 05 мая 2020

Вы можете просто посетить дерево в обратном порядке, то есть начиная с root, и сделать три вещи:

  1. посетить правую ветвь
  2. посетить собственный узел и накопить сумму при необходимости
  3. посетите левую ветвь

И прекратите итерацию, когда накопится k элементов. 

#include    <iostream>

struct Node {
    int value;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int v) : value(v) {}
};

// Visit the tree in reverse order and get sum of top k items.
int sumK(Node* root, int& k) {
    if (root == nullptr) return 0;
    int sum = 0;
    if (k > 0 && root->right) {
        sum += sumK(root->right, k);
    }
    if (k > 0) {
        sum += root->value;
        k--;
    }
    if (k > 0 && root->left) {
        sum += sumK(root->left, k);
    }
    return sum;
}

int main () {
    // The following code hard coded a tree matches the picture in your question.
    // I did not free the tree, so there will be memory leaking, but that is not relevant to this test.
    Node* root = new Node(5);
    root->right = new Node(6);
    root->right->right = new Node(7);
    root->left = new Node(3);
    root->left->right = new Node(4);
    root->left->left = new Node(2);
    root->left->left->left = new Node(1);
    // TODO: delete the tree after testing.

    int k = 1;
    std::cout << "k=" << k << " sum=" << sumK(root, k) << std::endl;
    k = 3;
    std::cout << "k=" << k << " sum=" << sumK(root, k) << std::endl;
    k = 4;
    std::cout << "k=" << k << " sum=" << sumK(root, k) << std::endl;
}

Результат: 

k=1 sum=7
k=3 sum=18
k=4 sum=22
...