Sem II (Program I) - N9

Question 1

Зачем используется стек при поиске в глубину?

Answer 1

Чтобы сохранять порядок узлов вдоль пути.

Question 2

Wann gilt ein Binärbaum als sortiert?

Answer 2

Бинарное дерево считается отсортированным, если:
- Все узлы в левом поддереве узла меньше самого узла.
- Все узлы в правом поддереве узла больше самого узла.

Question 3

Как вставить узел в отсортированное бинарное дерево?

Answer 3

Алгоритм решает на каждом узле, куда вставлять новый узел - слева или справа:

- Если значение меньше, проверить, есть ли место слева. Если да, вставить слева. В противном случае продолжить поиск в левом поддереве.
- Если значение больше, действовать аналогично с правой стороны.
- Если значение равно, узел не вставляется, и выводится сообщение об ошибке.

Question 4

Was passiert, wenn der Baum leer ist?

Answer 4

Новый узел вставляется в качестве корня.

Question 5

Was ist der Unterschied zwischen Preorder-, Inorder- und Postorder-Durchlauf in binären Bäumen?

Answer 5

Preorder: Корень → левое поддерево → правое поддерево
Inorder: левое поддерево → корень → правое поддерево
Postorder: левое поддерево → правое поддерево → корень

Question 6

Wie wird ein Preorder-Durchlauf in Java implementiert?

Answer 6

public void preorder() {    
    rekPreorder(root); 
}

private void rekPreorder(BinNode k) {
    if (k != null) {
        tuWas(k.inhalt);  
        rekPreorder(k.links);  
        rekPreorder(k.rechts);  
    } 
}

Question 7

Welche Schritte sind beim Postorder-Durchlauf erforderlich?

Answer 7

- Обойти левое поддерево
- Обойти правое поддерево
- Посетить корень

Question 8

Чем поиск в ширину (Levelorder) отличается от других обходов?

Answer 8

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

Question 9

Wie könnte die Breitensuche in Java implementiert werden?

Answer 9

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

Question 10

Welche praktische Anwendung hat die Breitensuche in Bäumen?

Answer 10

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

Question 11

Warum ist es wichtig, sich in der Breitensuche die Knoten einer Ebene zu merken?

Answer 11

Чтобы узлы могли быть пройдены в упорядоченном порядке (слева направо), их необходимо сохранить в очереди перед рассмотрением следующего уровня.

Question 12

Wie wird ein Blattknoten aus einem sortierten Binärbaum entfernt?

Answer 12

- Найти узел, который нужно удалить.
- Удалить узел и установить указатель родительского узла в null.

Question 13

Wozu wird die Datenstruktur Baum verwendet?

Answer 13

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

Question 14

Какой уровень доступа (видимости) к классу двоичных узлов вы порекомендуете?

Answer 14

Видимость класса должна быть ограничена (например, private или protected), чтобы избежать прямого доступа к данным узла и защитить структуру данных.

Question 15

Как можно обойти дерево?

Answer 15

Tiefensuche: Preorder, Inorder, Postorder
Breitensuche

Question 16

Was ist der Unterschied zwischen Tiefen- und Breitensuche?

Answer 16

Поиск в глубину: Проходит по узлам вдоль одного пути до конца, прежде чем исследовать другие пути.
Поиск в ширину: Проходит по узлам уровень за уровнем.

Question 17

Wie kann man Tiefen- und Breitensuche auf Bäumen in Java implementieren?

Answer 17

Поиск в глубину: Рекурсивная реализация, которая обращается к левому и правому поддеревьям.
Поиск в ширину: Использование очереди (Queue) для последовательного посещения узлов одного уровня

Question 18

Легче ли вставить или удалить узел в отсортированном двоичном дереве?

Answer 18

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

Question 19

Blatt (Terminalknoten)

Answer 19

Knoten ohne Kinder

Question 20

innerer Knoten

Answer 20

** ein Knoten mit mind. einem Kind**

Question 21

Höhe (Tiefe) des Baumes

Answer 21

**max. (Kanten-)Entfernung von Wurzel bis zum Blatt **

Question 22

Tiefe (Level) eines Knoten

Answer 22

seine Entfernung zur Wurzel (Tiefe der Wurzel = 0)

Question 23

Binärbaum

Answer 23

Baum, bei dem jeder Knoten max. zwei Kindknoten hat