Обход дерева, предшественник и преемник - PullRequest
Новая
       5

Обход дерева, предшественник и преемник

0 голосов
/ 14 ноября 2018

Я столкнулся с парой сомнений в древовидной структуре данных.

1) Возможен ли обход дерева (Предзаказ, Переупорядочение, Поступорядочение) во всех типах деревьев или только в двоичных деревьях.

2) Если первая точка верна, то можем ли мы просто переупорядочить обход дерева и сохранить элементы в массиве.

И затем, используя этот массив, мы можем найти предшественника и преемника как элементы, идущие до и после данного элемента.

1 Ответ

0 голосов
/ 14 ноября 2018

1.

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

каждое дерево содержит дочерние узлы (двоичное дерево 2, троичное дерево 3 и т. Д.).

Нам нужно определить наш собственный способ обхода деревьев. давайте возьмем пример тройного дерева.

Предварительный заказ: посещение (root.data) -> root.left -> root.middle -> root.right

Порядок: root.left -> root.middle -> root.right -> визит (root.data)

inorder: root.left -> root.middle -> визит (root.data) -> root.right

Предзаказ : посещение всех k дочерних узлов (слева направо) после первого посещения корневого узла.

Postorder : посещение всех k дочерних узлов (слева направо) до посещения корневого узла.

Inorder : посещение k / 2 дочерних узлов (слева направо) и посещение корневого узла, затем посещение оставшихся k / 2 дочерних узлов.

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

для двоичного дерева, предшественник = левый потомок, преемник = правый потомок

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

...