BST; сумма элементов BST, превышающая сумму их прямых потомков - PullRequest
Новая
       4

BST; сумма элементов BST, превышающая сумму их прямых потомков

0 голосов
/ 15 апреля 2020

Таким образом, задача состоит в том, чтобы написать функцию, которая возвращает сумму элементов BST, которая больше, чем сумма их прямых потомков. Не считайте листовые узлы. Я сделал это таким образом, базовый случай, когда дерево пустое, возвращает 0, а если у него нет сыновей, также возвращает 0. Затем я проверил, имеет ли узел один или два дочерних элемента, и условие для сумм. 

int sum(struct node* root) 
{
if (root== NULL) return 0;
if (root->right == NULL && root->left==NULL) return 0;
if (root->right!= NULL && root->left != NULL)
{
    if (((root->right)->key + (root->left)->key) < root->key) return root->key;
}
if (root->right != NULL && root->left==NULL)
{
    if ((root->right)->key< root->key) return root->key;
}
if (root->left != NULL && root->right==NULL)
{
    if ((root->left)->key < root->key) return root->key;
}
else return sum(root->right) + sum(root->left);
}

Main: 

struct node* root = NULL;

add(&root,-4);
add(&root,6);
add(&root,8);
add(&root,-11);
add(&root,5);
add(&root,7);
add(&root,-20);
printf("%d",sum(root));

Должно возвращаться -1 (6 + 8-11-4), но моя функция не работает, я не знаю почему.

1 Ответ

1 голос
/ 15 апреля 2020

В вашем коде предложение else никогда не будет выполнено; Ваши предыдущие условия имели дело со всеми возможностями.

Однако выражение должно быть выполнено. Вам нужно либо добавить + sum(root->left) + sum(root->right) как часть трех невырожденных операторов return, либо сохранить root->key в локальной переменной (по умолчанию ноль) и перейти к return return_value + sum(root->left) + sum(root->right);.

Следовательно (используя аббревиатуру rv для «возвращаемого значения»: 

int sum(struct node* root)
{
    int rv = 0;
    if (root == NULL || (root->right == NULL && root->left == NULL))
        return rv;
    if (root->right != NULL && root->left != NULL)
    {
        if ((root->right->key + root->left->key) < root->key)
            rv = root->key;
    }
    if (root->right != NULL && root->left == NULL)
    {
        if (root->right->key < root->key)
           rv = root->key;
    }
    if (root->left != NULL && root->right == NULL)
    {
        if (root->left->key < root->key)
            rv = root->key;
    }
    return rv + sum(root->right) + sum(root->left);
}

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

Вы можете использовать цепочку else if для последних трех «внешних» if тестов (с предложением else вместо последнего теста), чтобы избежать повторных тестов. измеримая разница спорна, оптимизатор может даже сделать изменения для себя

.
...