Сумма чисел на пути к максимальному числу в деревьях
Требуется реализовать функцию которая определить сумму цифр в значениях тех узлов, которые лежат на пути от корня до максимального элемента. Я сам пытался, но все заканчивается крахом:
template <class T> class TNode {
public:
T Key; //Значение узла
TNode* Left; //Левый потомок
TNode* Right; //Правый потомок
size_t count; //Счетчик числа вхождений
int height; //Высота узла
TNode() : Left(nullptr), Right(nullptr) {}
TNode(T key) : Key(key), Left(nullptr), Right(nullptr), count(1), height(0) {}
TNode(T key, TNode* lptr, TNode* rptr) :Key(key), Left(lptr), Right(rptr), count(1), height(0) {}
};
template <class T> struct SearchResult {
T _maxValue;
T _sum;
public:
SearchResult() :_sum(NULL), _maxValue(NULL) {}
TNode<T> getMaxValue() const { return _maxValue; }
void setMaxValue(int value) { _maxValue = value; }
void setSum(int value) { _sum = value; }
TNode<T> getSum() const { return _sum; }
};
template <class T> class BinSTree {
protected:
TNode<T>* root; //Указатель на корневой узел
TNode<T>* current; //Указатель на текущий узел
size_t size; //Число узлов в дереве
public:
void findsum(ostream& stream, const TNode<T>* node, T previousSum, SearchResult& result)
{
T sum = previousSum + node.data;
if (node.data > result.getMaxValue()) {
result.setMaxValue(node.data);
result.setSum(sum);
}
if (node.Left != NULL) findsum(node.Left, sum, result);
if (node.Right != NULL) findsum(node.Right, sum, result);
stream << "Сумма всех чисел на пути" << sum << endl;
stream << "Максимальное число: " << result.getMaxValue();
}
};
//Main:
BinSTree<double>* t_tree; //Указатель на объект "Дерево"
t_tree = new BinSTree<double>();//Инициализация на объекта "Дерево"
SearchResult<double> res ; // Значение текущей суммы
t_tree->findsum(cout, t_tree->getRoot(),0, res);
cout << endl;
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Почему бы не выполнить задачу поэтапно?
Первым обходом находим максимум.
При втором обходе, как только находим его снова - возвращаемся до корня.