Изменить значение листьев дерева на сумму пути от корня до листа

Мне нужно создать функцию, которая брала дерево t не пустым, изменяла содержимое каждого листа в своем поле, подставляя сумму значений, содержащихся в узлах пути от корня к листу (включая корень и лист).

Итак, я создал это:

void sum(BinTree t) {
    while(!t.isLeaf()) {
        sumL += sum(t.left);
        sumR += sum(t.right);
    }
    t.element = ?;
}

boolean isLeaf(BinTree t) {
    return t.left == null && t.right == null;
}

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

Спасибо

РЕДАКТИРОВАТЬ: я изменил свой метод:

void leafSum(BinTree t) {
    sumLeaf(root, 0);
}

void leafSum(BinTree t, int tot) {
    if(t->left == NULL && t->right == NULL)
        t->elem = tot;
    else {
        sumLeaf(t->left, tot + t->elem);
        sumLeaf(t->right, tot + t->elem);
    }
}

java binary-tree
person Community    schedule 01.06.2015    source источник
comment
Прошу прощения за резкость, но это значит, что вам нужно больше пробовать и больше учиться. Как бы вы выполнили эту задачу?   -  person Tassos Bassoukos    schedule 02.06.2015
comment
Прочтите эту вики-статью об обходе дерева: rosettacode.org/wiki/Tree_traversal#Java примеры на Java, которые вы можете копировать и вставлять, и вам нужно только изменить их для математики. И да, все примеры рекурсивны. Хотя можно пройти по дереву без рекурсии, это широко считается уродливым решением.   -  person Paul Sasik    schedule 02.06.2015

Ответы (1)


arrow_upward
2
arrow_downward

Вместо того, чтобы предлагать решение, я дам несколько советов, которые помогут вам в этом. Задавайте вопросы, если что-то непонятно.

  • Основной алгоритм, который вы ищете, таков: для каждого узла, если это лист, сохраните сумму, если это не лист, то повторите для обоих дочерних узлов.

  • Хотя рекурсия не обязательна, в данном случае она упростит решение. Это не сложно: основное правило состоит в том, чтобы всегда иметь условие завершения (в вашем случае, что вы смотрите на лист) перед рекурсией.

  • Вы должны передать промежуточную сумму функции, чтобы вам не нужно было возвращаться к дереву, как только вы доберетесь до листа. Это несложно: просто добавьте текущее значение для узла к промежуточной сумме, прежде чем сохранить его (для листьев) или передать его дочернему узлу (для не-листов).

  • Начните с промежуточной суммы, равной нулю, когда вы вызываете функцию для корневого узла.

Вот и все - вы должны быть в состоянии придумать решение из этих подсказок.

person sprinter    schedule 02.06.2015