4036. Прямой обход дерева
Задан массив целых чисел.
Создайте из них Бинарное Дерево Поиска. Если вставляемое значение равно текущей
вершине, то его следует вставлять в правое
поддерево.
Реализуйте метод PreOrder прямого обхода дерева. При
прямом обходе сначала посещается корень, потом левое поддерево, потом правое
поддерево.
Напишите код согласно следующего
интерфейса:
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 в Бинарное Дерево Поиска
void PreOrder(void); // Вывести вершины дерева в порядке прямого обхода
};
Вы можете создавать
(использовать) по необходимости дополнительные методы.
Вход. Первая
строка содержит число n (1 ≤ n ≤ 100). Вторая строка содержит n целых чисел.
Выход. Создайте Бинарное Дерево Поиска
из входных данных. Выведите вершины дерева в порядке прямого обхода.
Пример входа
6
14 9 1 14 20 13
Пример выхода
14 9 1 13 14 20
РЕШЕНИЕ
дерево
Анализ алгоритма
Прямой
обход дерева (PreOrder): посещается корень, левое поддерево, правое поддерево;
Реализация алгоритма
Объявим рабочие структуры данных.
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);
}
void
PreOrder(void)
{
PreOrder(head);
printf("\n");
}
void
PreOrder(TreeNode *tree)
{
if (tree ==
NULL) return;
printf("%d
",tree->val);
PreOrder(tree->left);
PreOrder(tree->right);
}
};
Основная часть программы. Читаем входные данные, строим
дерево.
Tree a;
scanf("%d",&n);
for(i = 0; i < n; i++)
{
scanf("%d",&val);
a.Insert(val);
}
Выводим вершины дерева в порядке прямого
обхода.
a.PreOrder();