Найти сумму данных, хранящихся во всех не листах дерева двоичного поиска? (автономная рекурсивная функция, которая возвращает целое число.)

Question

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

friend int Sum_Node_leaf_Data(BST *Root)

И ниже память объекта следующего класса действует как узел связанного списка, представляющего дерево двоичного поиска целых чисел.Если кто-то может предложить другую логику для этого.Я не могу исправить свою логическую ошибку, если кто-то из вас может указать и предложить что-то, было бы очень полезно.

class BST{
private: int info;
         BST *left;
         BST *right;
public: BST () {} //NULL Constructor.
};

логика, которую я сформировал для этой проблемы, заключается в том, что я объявляю и инициализируюпеременная целочисленного типа 'сумма' к нулю.ii) проверил, указывает ли корневой адрес на ноль.Если это не так, iii) проверил, указывают ли оба указателя 'left' и 'right' на Null, если false, то сумма добавляется с помощью 'info', хранящейся в том месте, куда указывает корневой указатель. После ее добавления, iv) два рекурсивных вызовак той же функции передаются значения «root-> left» и «root_> right» соответственно.

int Sum_Non_Leaf_Data(BST *Root){
    int sum =0;
    if(Root != NULL){
       if(Root->left != NULL && Root->right !=NULL){
          sum += Root_info;
          Sum_Node_Leaf_Data(Root->left);
          Sum_Node_Leaf_Data(Root->right);
        }
    return sum;
     }
}

Но проблема в том, что, поскольку это функция recurive, значение sum каждый раз переинициализируется, поэтомуКак я могу вернуть целочисленное значение суммы.

Answer 1

Я считаю, что этот код намного чище, чем принятый ответ:

int internal_node_sum(BST *node)
{
    if (!node || (!node->left && !node->right)) {
        return 0;
    }

    int sum = node->info;
    sum += internal_node_sum(node->left);
    sum += internal_node_sum(node->right);
    return sum;
}

Обратите внимание, что из-за короткого замыкания нулевой указатель не будет разыменовываться в условии if в случаепустой список.

Answer 2

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

, поскольку это функция recurive, значение sum каждый раз переинициализируется

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

Но вам даже не нужен sum в этой функции

int internal_node_sum(BST * node)
{
    if (node && node->left && node->right) {
        return node->info
             + internal_node_sum(node->left)
             + internal_node_sum(node->right);
    }

    return 0;
}

Answer 3

вы не должны игнорировать возвращаемые значения вашей рекурсивной функции.Код ниже должен решить вашу проблему:

int Sum_Non_Leaf_Data(BST *Root){
    int sum =0;
    if(Root != NULL){
       if(Root->left != NULL && Root->right !=NULL){
          sum += Root->info;
          sum+=Sum_Node_Leaf_Data(Root->left);
          sum+=Sum_Node_Leaf_Data(Root->right);
        }
   }
   return sum;
}