Обход двоичного дерева (сортировка)
Есть : двоичное дерево применительно к сортировке массива
Задача : обойти узлы по схеме <левый сосед -> родитель -> правый сосед> для получения отсортированного массива, соотв.
Хочется: алгоритм в псевдокоде или блок-схема (или сам код) для реализации такого обхода.
Q2:
Есть : текст программы на C\C++
Задача : собрать статистику по всем переменным, вывести их типы
Хочется: быстро определять тип переменной по ее имени.
Спасибо.
Q1:
Есть : двоичное дерево применительно к сортировке массива
Задача : обойти узлы по схеме <левый сосед -> родитель -> правый сосед> для получения отсортированного массива, соотв.
Хочется: алгоритм в псевдокоде или блок-схема (или сам код) для реализации такого обхода.
Q2:
Есть : текст программы на C\C++
Задача : собрать статистику по всем переменным, вывести их типы
Хочется: быстро определять тип переменной по ее имени.
Спасибо.
1. Посмотри здесь:
http://alglib.manual.ru/sorting/heapsort.php
1. Хм, а тут условие, что дерево обладает свойством "любой предок больше потомка"; я так понял это когда для каждого узла выполняется условие того что все узлы в его поддереве меньше него (или равны) - а у меня дерево таким свойством не обладает.
1. Хм, а тут условие, что дерево обладает свойством "любой предок больше потомка"; я так понял это когда для каждого узла выполняется условие того что все узлы в его поддереве меньше него (или равны) - а у меня дерево таким свойством не обладает.
Когда ты сортируешь массив, он состоит из отсортированной части(дерево) и неотсортированной.
Берёшь первый элемент из неотсортированной части, и вставляешь в "дерево", пока не кончатся ноехваченные элементы.
Когда ты сортируешь массив, он состоит из отсортированной части(дерево) и неотсортированной.
Берёшь первый элемент из неотсортированной части, и вставляешь в "дерево", пока не кончатся ноехваченные элементы.
Судя по всему это "лабораторка". Так вот: чтобы отсортировать массив методом бинарной сортировки (так кажется), тебе нужно создавать именно дерево двоичного поиска (а в нем "любой предок больше потомка").
А алгоритм в псевдокоде при таком раскладе выглядел бы типа такого:
void recurs(TTreeNode *node)
{
if (node) {
recurs(node->left);
output(node->field);
recurs(node->right);
}
}
P.S. Почитай Кнута, Вирта и т.п.