Бинарное дерево

Задание 1

Ответы на вопросы и сами вопросы:

1)  Что определяет степень дерева?

Степень дерева определяет максимальное количество потомков каждого узла в дереве. То есть, степень дерева указывает на ограничение по количеству дочерних узлов, которые может иметь каждый узел в дереве.

2) Какова степень сильноветвящегося дерева?

Сильноветвящееся дерево - это дерево, в котором каждый узел имеет максимально возможное количество потомков, равное степени дерева. Таким образом, степень сильноветвящегося дерева соответствует степени дерева. Если в бинарном дереве степень <=2, то в сильноветвящемся дереве >2.

3) Что определяет путь в дереве?

Путь в дереве определяет последовательность узлов, которые соединяют корневой узел с определённым узлом дерева. Путь включает как начальный узел, так и конечный узел, а также все узлы, которые соединяют их в порядке следования.

4) Как рассчитать длину пути в дереве?

Длина пути в дереве - это количество ребер, которые нужно пройти, чтобы достичь определенного узла от корня дерева. Для вычисления длины пути в дереве необходимо посчитать сумму длин всех его ребер, которые находятся на данном пути.

5) Какова степень бинарного дерева?

В бинарном дереве каждый узел может иметь не более двух потомков, поэтому его степень всегда равна двум.

6) Может ли дерево быть пустым?

Да, дерево может быть пустым, если оно не содержит ни одного узла.

7) Дайте определение бинарного дерева?

Бинарное дерево - это структура данных, состоящая из узлов, в которой каждый узел имеет не более двух дочерних узлов, называемых левым и правым потомками. Левый потомок обычно содержит значение, меньшее или равное значению узла, а правый потомок - значение, большее чем значение узла.

8) Дайте определение алгоритму обхода.

Обход дерева - это алгоритм, обеспечивающий доступ к каждому узлу дерева для выполнения операций с данными узла.. Алгоритм обхода определяет порядок, в котором будут посещаться узлы.

9) Приведите рекуррентную зависимость для вычисления высоты дерева.

Высота дерева = 1 + максимальная высота из высот левого и правого поддерева, где максимальная высота из высот левого и правого поддерева - это наибольшее из значений высоты левого и правого поддерева.

10) Изобразите бинарное дерево, корень которого имеет индекс 6, и которое представлено в памяти таблицей вида:

[pic 1]

Ключи были подписаны над ребрами для удобства:

[pic 2]

11) Укажите путь обхода дерева по алгоритмы: прямой, обратный, симметричный

[pic 3]

Прямой: корень, лево, право : ABDGCEHIF

Обратный: лево, право, корень : GDBHIEFCA

Симметричный: лево, корень, право: DGBAHEICF

12) Какая структура используется в алгоритме обхода дерева методом в «ширину»?

В алгоритме обхода дерева методом в "ширину" используется структура данных под названием "очередь" (queue). Очередь работает по принципу FIFO (First In, First Out), что означает, что элементы добавляются в конец очереди, а извлекаются из начала очереди.

При обходе дерева в "ширину" алгоритм посещает все узлы одного уровня перед переходом на следующий уровень. Начиная с корневого узла, алгоритм добавляет его в очередь. Затем он извлекает узел из начала очереди, посещает его и добавляет в очередь всех его потомков. Процесс повторяется, пока очередь не опустеет.

Использование очереди позволяет сохранять порядок посещения узлов на каждом уровне дерева. Это важно для правильной последовательности обхода и правильного восстановления структуры дерева.

13) Выведите путь при обходе дерева в «ширину». Продемонстрируйте использование структуры при обходе дерева.