如何從任何父節點的所有葉子節點在樹上

我開發使用SQLite android的應用程序，我有一個樹狀結構，我在數據庫中表示，像這樣：如何從任何父節點的所有葉子節點在樹上

 +------+------+-------+------+ 
     |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請提的是，因爲我能這樣做更容易做到這一點。

來源

2014-02-12 sprocket12

您有兩個具有相同'nodeId'的節點。 'comp_id'的含義是什麼？顯示所需輸出的示例！ –

@CL。 'comp_id'表示編譯ID，它就像一本書，節點是章節名稱（可能有子章節），葉子就像頁面或段落。這是我可以給出的最接近的例子。 – sprocket12

選擇所有行的node_id不是其他行的父項，即它們是葉子。

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

來源

2014-02-12 10:26:26

感謝鮑里斯請參閱我的編輯，多個comp_id是可能的。 – sprocket12

這不是什麼問題！我猜他只有那些以給定節點爲根的子樹中的葉節點。 – Bhoot

是Bhoot是對的。 – sprocket12

你可以做一個遞歸方法，這將返回來自其子所有的葉子組成的數組，如果某個節點有孩子，或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()); 
     } 
    } 
}

這樣，您可以將邏輯保留在一個方法中，不必冗餘遍歷不重要的節點。結構方法的實施取決於你。

來源

2014-02-12 10:28:01 Warlord

請你可以用僞代碼顯示兩個方法'getAllLeafs'和'getAllChildren'。 – sprocket12

well getAllLeafs是寫在代碼中的，子字段是Node的一個屬性，因此你可以直接得到它，沒有涉及算法 – Warlord

看起來你的'getLeafs（）'沒有帶參數，但是你用它調用它參數？！ 'getAllLeafs（child）' – sprocket12

我覺得這個邏輯會工作：

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

內部查詢發現那些父母也是在同一個表節點。外部查詢找出不是任何節點的父節點的節點，因此必須是葉節點。希望這可以幫助！

來源

2014-02-12 10:43:19 Bhoot

你對鮑里斯的回答是正確的，但你也犯過同樣的錯誤！請將輸入'node_id'視爲root，並在您的解決方案中包含'comp_id'。 – sprocket12

哦！我以爲你說鮑里斯是對的。在這種情況下，我需要更多的思考。 :) – Bhoot

那麼，取下所有節點的原因是什麼，而不是所有的直接節點？第二種選擇顯然很簡單。

我不認爲有一個合理的解決方案，可能是圖形數據庫。關鍵是你可以：

要讓所有父ids（直接和非直接）與每個節點一起保持。你可以設計新表具有外鍵。但這個解決方案看起來像重量級。說到這個表應該成指數增長。
將整棵樹放在一起。這是我們經過四年數據庫研究後在我們的應用程序中使用的方法。數據庫旨在通過提前緩存和讀取硬盤驅動器博客來獲取彼此相鄰的數據。您可以使用正確的索引等來改進此解決方案。我所說的是，有時候從數據庫中獲取連續驅動器片段比製作複雜查詢更好，而不是搜索Java代碼中的所有節點。

請注意，整個樹的一個提取（通過根索引id）可以在一次數據庫讀取中完成數據庫。另一方面，通常選擇使用嵌套查詢或使用連接使用更多的讀取，需要ids匹配，也許臨時表等。（索引處理，鎖定等）

您絕對應該使用各種NoSQL DB，但也應該使用RDBMS。

來源

2014-02-12 11:44:52

不幸的是，我的樹可能包含近一百萬行，我無法將它全部加載到移動設備的內存中，而且我不知道任何其他數據庫都不是Sqlite提供給我的。 – sprocket12

所以我會使用另一個包含所有節點的父節點的表，並且您可以非常容易地查詢這樣的表。 –

請舉例說明使用我的數據，隨意拆分成多個表格，但記住表格中將包含許多100,000行，空間是寶貴的。 – sprocket12

使用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版本，你將不得不手動檢索每個級別的節點。

來源

2014-02-12 11:46:36

我不可能在android上獲得v3.8.3。最新的支持是3.7.11。對不起，我沒有足夠的標籤來添加'android'，並不認爲我需要提及它。 – sprocket12

如何從任何父節點的所有葉子節點在樹上

回答

相關問題