Модифицированный обход дерева предзаказа - поиск следующего узла

Question

У меня есть эти данные:

id | parent_id | lft | rgt | name
=====================================
1  | 0         | 1   | 8   | abc
2  | 3         | 5   | 6   | jkl
3  | 1         | 2   | 3   | def
4  | 0         | 9   | 10  | mnno
5  | 1         | 4   | 7   | ghi

Мне нужно пройти эту иерархию в следующем порядке (идентификаторы): 1> 3> 5> 2> 4

Как мне этого добиться?

Предположим, что я хочу найти следующий узел node_x.

if (node_x_rgt - node_x_lft == 1) {
    next_node_lft = node_x_rgt + 1;
} else {
    next_node_lft = node_x_lft + 1;
}

Эта формула работает только в некоторых случаях (идентификаторы узлов 1,3,5,2). Следующий узел узла 2 должен быть 4.

Answer 1

С информацией, которую вы дали, все, что я могу посоветовать, это попробовать:

select * from table order by id

Кстати, столбцы lft и rgt для id 4 находятся вне дерева, похоже на ошибку?

btw2, если это домашнее задание, пожалуйста, отметьте его как таковое.

Редактировать : вариант 2 вопроса:

Эти виды деревьев имеют инвариант (lft < rgt) для всех узлов. Если таблица содержит только 1 корневой узел, последовательности могут быть извлечены либо значениями lft или rgt, в этом случае lft по-прежнему справляется с задачей (но альтернатива через rgt в порядке убывания не будет):

select * from table order by lft