Geek asks and answers

How to get all leaf nodes from any node parent in a tree

I am developing an application in android using Sqlite, I have a tree structure that I represent in db as follows:

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

It is difficult for me to program the algorithm in a stand-alone method, as shown below, to return me all the sheets under any node.

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

If there is a way to do this more easily by changing my table structure and / or using SQL, please indicate that I can do this.

+3
source share
5 answers

Select all rows whose node_idparents are not some other rows, i.e. they are leaves.

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

, , node 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());
        }
    }
}

, . .

0

, :

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);

, . , node , , . , !

0

, ? , , .

, , , . , :

  • ( ) node. . . , .

  • . , . , - . , . , , , , , Java-.

    , ( ) . , , , .. ( , ..)

    NoSQL, RDBMS.

0

SQLite 3.8.3 , node, :

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 .

0

More articles:


All Articles