Помогите понять условие (паскаль, двоичные деревья)

love_4ever

Динамические структуры данных. Обработка деревьев.
Составить программу для построения и обработки УПОРЯДОЧЕННОГО ДВОИЧНОГО ДЕРЕВА, содержащего узлы типа char. Основные функции работы с деревьями реализовать в виде универсальных процедур. После того, как дерево создано, его обработака должна производиться в режиме меню с действиями:
-- добавление нового узла(для двоичного дерева положение нового узла определяется в соответствии с требованием сохранения порядка)
--визуализация дерева(значение каждого зла выводится в отдельной строке, с отступом, пропорциональным глубине узла, в порядке старшинства узлов)
--удаление узла (двоичное дерево перестраивается в соответствии с требованием сохранения целостности и порядка;
--проверка монотонности убывания ширины уровня дерева.
определения
Глубиной вершини дерева называется длниа пути в эту вершину из корня.
Глубиной(высотой) дерева называется макс. глубина его вершин.
Листом, или терминальной вершиной дерева называется вершина, не имеющая поддеревьев.
Степенью вершины называется число исходящих из неё ветвей.
Степенью дерева называется макс. степень его вершин
Шириной уровня дерева называется число вершин на данной глубине.
Шириной дерева называется макс. ширина по всем уровням
Подобие деревьев отличается от равенства возможным несовпадением значений данных в узлах.

love_4ever

Я не понимаю или не знаю:
Определение упорядоченного двоичного дерева - 1(это, собственно, главное, из него всё и проистекает)
Там должны быть, наверное, какие-то ключи, как они определяются?
Или дерево (каноническое) должно быть упорядоченно по данным?
Тогда могут ли быть ветви с одинаковыми данными?

poi1981

>Или дерево (каноническое) должно быть упорядоченно по данным?
да
>Тогда могут ли быть ветви с одинаковыми данными?
могут

kokoc88

Это дерево, из каждой вершины которого могут исходить не более двух ветвей (дуг). Ключом могут быть любые данные на листьях (вершинах). Упорядоченное дерево - это такое дерево, в котором новое положение элемента определяется так, чтобы все элементы с большим или равным ключом находились на правом (или на левом) поддереве. Для числового ключа дерево может выглядеть так :




              4

           /      \

         2        15

       /         /   \

     -4         5     18

love_4ever

А что значит -

--удаление узла (двоичное дерево перестраивается в соответствии с требованием сохранения целостности и порядка;

Когда удаляется узел, то всё удаляется под ним или нет?
Если нет, то этот узел надо чем-то заполнить, вытянув снизу, например, большее или левое. для этого, по ходу дела, надо вытянуть дальше снизу, и так далее, пока не кончится.
Не понял я эту херню.

pollak

удаляется всё под ним.

kokoc88

В моём случае правое поддерево вешается вместо элемента, а левое поддерево становится левым поддеревом самого левого нижнего элемента правого поддерева.




              4

           /      \

         2        15

       /         /   \

     -4         5     18

                    /   \

                   16    19

Удаляем 15...




              4

           /     \

         2        \

       /            \

     -4              18

                    /   \

                   16    19

                 /

               5

VitMix

удаляется всё под ним

Не надо пугать человека, а то он и правдо всё под удаляемым элементом удалять станет

Оставить комментарий