Возможно ли сделать обход в глубину в sql postgresql?

Question

Возможно ли сделать обход в глубину в sql postgresql? Под этим понятием я имею ввиду сортировку данных, имитирующую обход дерева в глубину. Предположим у нас есть таблица(иерархическая структура данных):

CREATE TABLE table1(
    id SERIAL NOT NULL,
    parent INREGER
)

Я знаю как обойти ее в ширину:

WITH RECURSIVE tree(id, parent, lvl) AS (
    SELECT id, parent, 0
    FROM from table1 WHERE parent IS NULL
    UNION ALL
    SELECT id, parent
    FROM table1 INNER JOIN tree on tree.id = table1.parent.
)
SELECT * FROM tree;

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

Answer 1

Обход в ширину (сортируем по уровням):

WITH RECURSIVE tree(id, parent, lvl) AS (
    SELECT id, parent, 0
    FROM table1 WHERE parent IS NULL
    UNION ALL
    SELECT table1.*, lvl + 1
    FROM table1 INNER JOIN tree on tree.id = table1.parent
)
SELECT * FROM tree order by lvl;

Обход в глубину (сортируем по путям от корня):

WITH RECURSIVE tree(id, parent, path) AS (
    SELECT id, parent, array[id]::integer[]
    FROM table1 WHERE parent IS NULL
    UNION ALL
    SELECT table1.*, path || array[table1.id]::integer[]
    FROM table1 INNER JOIN tree on tree.id = table1.parent
)
SELECT * FROM tree order by path;

Для данных:

insert into table1 values (1, null);
insert into table1 values (11, 1);
insert into table1 values (12, 1);
insert into table1 values (13, 1);
insert into table1 values (111, 11);
insert into table1 values (112, 11);
insert into table1 values (113, 11);
insert into table1 values (114, 11);
insert into table1 values (121, 12);
insert into table1 values (1211, 121);
insert into table1 values (12111, 1211);
insert into table1 values (12112, 1211);
insert into table1 values (12113, 1211);

Результат обхода в ширину:

  id   | parent | lvl
-------+--------+-----
     1 |        |   0
    11 |      1 |   1
    12 |      1 |   1
    13 |      1 |   1
   111 |     11 |   2
   112 |     11 |   2
   113 |     11 |   2
   114 |     11 |   2
   121 |     12 |   2
  1211 |    121 |   3
 12111 |   1211 |   4
 12112 |   1211 |   4
 12113 |   1211 |   4

Результат обхода в глубину:

  id   | parent |         path
-------+--------+-----------------------
     1 |        | {1}
    11 |      1 | {1,11}
   111 |     11 | {1,11,111}
   112 |     11 | {1,11,112}
   113 |     11 | {1,11,113}
   114 |     11 | {1,11,114}
    12 |      1 | {1,12}
   121 |     12 | {1,12,121}
  1211 |    121 | {1,12,121,1211}
 12111 |   1211 | {1,12,121,1211,12111}
 12112 |   1211 | {1,12,121,1211,12112}
 12113 |   1211 | {1,12,121,1211,12113}
    13 |      1 | {1,13}

БЛОГ НА HUSL

Возможно ли сделать обход в глубину в sql postgresql?

Ответы (1 шт):