Я столкнулся с парой сомнений в древовидной структуре данных.
1) Возможен ли обход дерева (Preorder, Inorder, Postorder) во всех типах деревьев или только в бинарных деревьях.
2) Если первая точка верна, то можем ли мы просто Inorder пройтись по дереву и сохранить элементы в массиве.
И затем, используя этот массив, мы можем найти предшественника и преемника как элементы, идущие до и после данного элемента.
1.
Обход дерева (Preorder, Inorder, Postorder) возможен во всех типах деревьев, а не только в бинарных деревьях.
каждое дерево содержит дочерние узлы (двоичное дерево 2, троичное дерево 3 и т. д.).
Нам нужно определить наш собственный способ обхода деревьев. давайте возьмем пример троичного дерева.
Предварительный заказ: посещение (root.data) -> root.left -> root.middle -> root.right
в обратном порядке: root.left -> root.middle -> root.right -> visit(root.data)
в порядке: root.left -> root.middle -> visit(root.data) -> root.right
Предварительный порядок: посещение всех k дочерних узлов (слева направо) после первого посещения корневого узла.
Postorder: посетить все k дочерних узлов (слева направо) до посещения корневого узла.
По порядку: посетите k/2 дочерних узлов (слева направо) и посетите корневой узел, затем посетите оставшиеся k/2 дочерние узлы.
для бинарного дерева предшественник = левый дочерний элемент, преемник = правый дочерний элемент
для троичного дерева предшественник = левый дочерний элемент или средний дочерний элемент, преемник = средний дочерний элемент или правый дочерний элемент. (мы должны указать это на основе нашего требования)
