從數據庫行構建一棵樹

我需要從數據庫行構建一棵樹。更具體地說，我有一張桌子，裏面包含了會計科目表。從數據庫行構建一棵樹

而不是遞歸查詢表我希望加載所有表的信息，在一個步驟中包含ids和parentIds帳戶行，然後從那裏建立樹。

這樣做的問題之一是帳戶行不是以任何順序，即。在遇到父母之前，我可能會遇到一個孩子。

我認爲這個問題是非常通用的，所以我推測可能已經有一個haskell庫了。

任何人都可以幫忙嗎？

來源

2013-03-15 Guenni

這是哪個數據庫？ Postgres的？ MySQL的？甲骨文？我錯誤地假設它使用SQL？ – dave4420 2013-03-15 15:00:49

數據庫是mysql。除非事情已經改變了很多與MySQL我不認爲它可以提供我一個hierarichal結果，即。樹和遞歸查詢數據庫將會起作用，但這將會相當昂貴。 – Guenni 2013-03-15 15:05:31

在StackOverflow中獲得答案的質量幾乎完全取決於您提供的問題的質量。如果你想得到一個包含一些代碼的答案，你應該在你的問題中提供一些代碼，如果你想得到關於某個特定庫的答案，那麼就參考它。

目前您的問題非常模糊，我可以回答的是您需要使用類似Data.Map的結構先累積中間結果，然後通過查詢此中間數據結構重新排列它們。正如它的文檔所表示的，其大部分訪問函數的複雜性是O(log n)，這非常有效。

您不應該期望來自任何數據庫庫的那種功能，因爲問題太具體。

來源

2013-03-15 14:49:46

正如Nikita所說，你真正的問題是什麼？

你不提供任何數據類型，樹鍵分類，...

不管怎麼說，這個代碼可以幫助想想你的問題......

data Tree a = Node a [Tree a] deriving Show 

db = [(0, 1) 
    ,(1, 2) 
    ,(1, 3) 
    ,(2, 4) 
    ,(2, 6) 
    ,(3, 5) 
    ] 

rootTree = Node 0 [] 

insert parent child (Node key childs) = 
    Node key $ if key == parent then Node child []:childs 
           else map (insert parent child) childs 

insertFromDB rows = foldl insertRow rootTree rows 
    where insertRow tree (parent, child) = insert parent child tree

如果你不能得到有序數據時，可以責令其搜索的父母，下一個函數計算出每個節點的深層次（與相同db數據）

calculateDeepLevel db = compute 0 roots 
    where roots = filter (not.flip elem snds) fsts 
     fsts = nub $ map fst db 
     snds = map snd db 
     compute level parents = map (\n -> (n, level)) parents ++ 
           concatMap (addChilds (level + 1)) parents 
     addChilds level node = compute level $ map snd $ filter ((node==).fst) db

與calculateDeepLevel可以CAL從有序和無根（沒有0節點）版本的db中收集有序的db版本和基於0的版本。

來源

2013-03-15 15:03:55 josejuan

嗨josejuan，謝謝你的例子。由於數據結構尚未完成，因此我無法提供代碼或數據結構作爲示例。你在例子中提供的數據結構雖然足以解釋一般原理。上面的例子很好地構建樹，但只有當輸入數據按順序時，我可能無法從數據庫中檢索到。我只是試過你的代碼，它工作正常，但是當我恢復列表時，它無法構建樹。所以我試圖找出當元素隨機排列時如何構建樹。 – Guenni 2013-03-15 16:25:29

我增加了'calculateDeepLevel'來獲得節點級別，使用'sortBy'命令。 – josejuan 2013-03-15 17:55:08

一是部分進口，

import qualified Data.Map as M 
import qualified Data.Tree as T 
import Data.List (foldl') 
import Control.Arrow ((&&&)) 
import Data.Maybe (fromMaybe)

接下來，讓我們假設我們有一個有一個ID，以及一個可選的父ID（根節點沒有父）記錄，並進行一定的價值：

data Rec a = Rec { recId  :: Int 
       , recParentId :: Maybe Int 
       , recValue :: a 
       }

沒有什麼可以阻止多個節點擁有一個Nothing父ID，所以我們可能會找到多個樹，所以我們用於將列表轉換爲樹的功能如下所示：

toTree :: [Rec a] -> [T.Tree a] 
toTree rs = ts where

首先，讓我們來構建從可選的父ID的地圖，那有父ID記錄的列表：

-- gs :: M.Map (Maybe Int) [Rec a] 
    gs = foldl' f M.empty rs where 
     f m r = M.insertWith (const (r:)) (recParentId r) [r] m

接下來，讓我們展開一個樹從一個虛擬的根節點開始，的孩子這將是我們感興趣的樹根注意，虛擬根節點沒有價值，所以我們使用undefined：

-- t :: T.Tree a 
    t = T.unfoldTree mkNode (undefined, Nothing)

的mkNode函數傳遞我們想要的節點的值和id建立。它返回值，並利用我們構建了Map較早孩子值/ ID對的列表：

-- mkNode :: (a, Maybe Int) -> (a, [(a, Maybe Int)]) 
    mkNode (a, i) = (a, map (recValue &&& Just . recId) 
          . fromMaybe [] 
          . M.lookup i $ gs)

最後，我們可以丟棄虛擬根節點，並返回其直接孩子爲樹的根我們感興趣的是：

ts = T.subForest t

而且這是一個測試：

main = mapM_ (putStrLn . T.drawTree) 
     $ toTree [ Rec 0 Nothing "rootA" 
        , Rec 1 (Just 0) "rootA.childA" 
        , Rec 2 (Just 0) "rootA.childB" 
        , Rec 3 (Just 1) "rootA.childA.childA" 
        , Rec 4 (Just 1) "rootA.childA.childB" 
        , Rec 5 (Just 2) "rootA.childB.childA" 
        , Rec 6 (Just 2) "rootA.childB.childB" 
        , Rec 7 Nothing "rootB" 
        , Rec 8 (Just 7) "rootB.childA" 
        , Rec 9 (Just 7) "rootB.childB" 
        , Rec 10 (Just 8) "rootB.childA.childA" 
        , Rec 11 (Just 8) "rootB.childA.childB" 
        , Rec 12 (Just 9) "rootB.childB.childA" 
        , Rec 13 (Just 9) "rootB.childB.childB" 
        ]

產生：

rootB 
| 
+- rootB.childB 
| | 
| +- rootB.childB.childB 
| | 
| `- rootB.childB.childA 
| 
`- rootB.childA 
    | 
    +- rootB.childA.childB 
    | 
    `- rootB.childA.childA 

rootA 
| 
+- rootA.childB 
| | 
| +- rootA.childB.childB 
| | 
| `- rootA.childB.childA 
| 
`- rootA.childA 
    | 
    +- rootA.childA.childB 
    | 
    `- rootA.childA.childA

來源

2013-03-15 19:05:45 pat

從數據庫行構建一棵樹

回答

相關問題