1185. Сумма чисел на дереве

Задан массив целых чисел. Создайте из них Бинарное Дерево Поиска. Если вставляемое значение равно текущей вершине, то его следует вставлять в правое поддерево.

Реализуйте метод Sum, который возвращает сумму чисел во всех вершинах дерева.

Напишите код согласно следующего интерфейса:

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Tree

{

public:

TreeNode *head;

Tree() : head(NULL) {};

void Insert(int val); // Вставка числа val в Бинарное Дерево Поиска

int Sum(void); // Вернуть сумму чисел во всех вершинах дерева

};

Вы можете создавать (использовать) по необходимости дополнительные методы.

Вход. Первая строка содержит число n (1 ≤ n ≤ 100). Вторая строка содержит n целых чисел.

Выход. Создайте Бинарное Дерево Поиска из входных данных. Выведите сумму чисел во всех вершинах дерева.

Пример входа

6

14 9 1 14 20 13

Пример выхода

71

РЕШЕНИЕ

дерево

Анализ алгоритма

Сумму чисел Sum в дереве tree находим рекурсивно:

· если tree = NULL, то Sum = 0;

· иначе Sum = Sum(tree->left) + Sum(tree->right) + tree->val;

Реализация алгоритма

Объявим рабочие структуры данных.

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Tree

{

public:

TreeNode *head;

Tree() : head(NULL) {};

void Insert(int val)

{

Insert(head,val);

}

void Insert(TreeNode *&tree, int val)

{

if (tree == NULL)

{

tree = new TreeNode(val);

return;

}

if (val < tree->val)

Insert(tree->left,val);

else

Insert(tree->right,val);

}

int Sum(void)

{

return Sum(head);

}

int Sum(TreeNode *tree)

{

if (tree == NULL) return 0;

return Sum(tree->left) + Sum(tree->right) + tree->val;

}

};

Основная часть программы. Читаем входные данные, строим дерево.

Tree a;

scanf("%d",&n);

for(i = 0; i < n; i++)

{

scanf("%d",&val);

a.Insert(val);

}

Выводим сумму чисел в вершинах дерева.

printf("%d\n",a.Sum());