Как получить все узлы листа из любого родительского узла в дереве

Question

Я разрабатываю приложение в Android с помощью Sqlite, у меня есть древовидная структура, которую я представляю в БД, как так:

 +------+------+-------+------+ 
     |comp_id nodeId parent| text | 
     |------|------|-------|------| 
     | 146 | 1 | -1 | Top | 
     |  |  |  |  | 
     | 146 | 2 | 1 | Ch1 | 
     |  |  |  |  | 
     | 146 | 3 | 2 | Leaf | 
     |  |  |  |  | 
     | ... |  |  |  | 
     | 152 | 1 | -1 | Top | 
     +------+------+-------+------+ 

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

Node 
{ 
    public Node[] getAllLeafs() 
    { 
     // traverse all the way down the tree 
     // and get only leafs 
    } 
} 

Если есть способ сделать это более легко, изменяя свою структуру таблицы и/или с использованием SQL, пожалуйста, отметить, что, как я могу сделать это.

Answer 1

Выбрать все строки, чьи node_id не являются родителями некоторых других строк, то есть являются листьями.

select * 
from tree_table 
where node_id not in (
    select distinct parent from tree_table 
); 

Answer 2

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

public Node[] getAllLeafs() { 

    ArrayList<Node> allLeafs = new ArrayList<Node>(); 

    if (getAllChildren().size() == 0) { 
     allLeafs.add(this); 
     return (Node[]) allLeafs.toArray(); 
    } else { 
     for (Node child : this.getAllChildren()) { 
      allLeafs.addAll(child.getAllLeafs()); 
     } 
    } 
} 

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

Answer 3

Я думаю, что эта логика будет работать:

select node_id 
from tree_table where node_id not in 
(select a.node_id 
from tree_table as a, tree_table as b 
where a.node_id = b.parent); 

Внутренний запрос обнаруживает те узлы, которые также родители в той же таблице. Внешний запрос обнаруживает узлы, которые не являются родителями какого-либо узла и, следовательно, должны быть листовыми узлами. Надеюсь это поможет!

Answer 4

Ну, в чем причина для извлечения всех узлов вместо всех прямых узлов? Второй вариант, очевидно, прост.

Я не думаю, что существует разумное решение, возможно, базы данных графов. Дело в том, что вы можете:

1. Чтобы все идентификаторы родителей (прямые и не прямые) сохранялись вместе с каждым узлом. Для этого вы можете создать новую таблицу с внешними ключами. Но это решение похоже на тяжеловес. Говоря о том, какая такая таблица должна расти экспоненциально.

2. Чтобы получить все дерево вместе. Это тот подход, который мы используем в нашем приложении после четырех лет исследования базы данных. БД предназначена для сбора данных, лежащих рядом друг с другом из-за буферизации и чтения блогов на жестком диске. Вы можете улучшить это решение, используя правильные индексы и так далее. Я говорю о том, что иногда лучше выбирать сегмент непрерывного привода из БД, чем создавать сложные запросы, а не искать все узлы в Java-коде.

   Обратите внимание, что одна выборка всего дерева (по индексу корневого индекса) может выполнять БД в одном считывании БД. С другой стороны, обычно выбор с использованием вложенного запроса или с использованием соединений использует больше чтений, требует сопоставления идентификаторов, может быть временная таблица и так далее. (обработка индексов, блокировка и т. д.)

   Вы должны обязательно использовать различные базы данных NoSQL, а также СУБД.

Answer 5

С SQLite 3.8.3 или более поздней версии, вы можете использовать запрос, как следующий вычислить поддерево, начинающееся в определенном узле, а затем получить листья в этом поддереве:

WITH RECURSIVE subtree(comp_id, nodeId, parent, text) 
AS (SELECT * 
    FROM MyTable 
    WHERE comp_id = 146 AND nodeId = 1 -- start node 
    UNION ALL 
    SELECT MyTable.* 
    FROM MyTable 
    JOIN subtree ON MyTable.comp_id = subtree.comp_id 
       AND MyTable.parent = subtree.nodeid) 
SELECT * 
FROM subtree 
WHERE nodeid NOT IN (SELECT parent 
        FROM subtree) 

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