3

我需要从数据库行构建一棵树。更具体地说，我有一个包含会计科目表的表格。

我不想递归地查询表，而是想在一个步骤中加载所有表的信息，即包含 id 和 parentIds 的帐户行，然后从那里构建树。

问题之一是帐户行没有任何顺序，即。在我遇到父母之前，我可能会遇到一个孩子。

我认为这个问题非常普遍，所以我认为甚至可能已经有一个 haskell 库来解决它。

任何人都可以帮忙吗？

4

3 回答 3

2

正如尼基塔所说，你真正的问题是什么？

您不提供任何数据类型、树键分类、...

无论如何，这段代码可以帮助你思考你的问题......

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可以从.dbdb

于 2013-03-15T15:03:55.253 回答
2

首先是一些进口，

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-15T19:05:45.090 回答
1

您在 StackOverflow 上获得的答案质量几乎完全取决于您提供的问题的质量。如果您想获得包含一些代码的答案，您应该在问题中提供一些代码，如果您想获得有关某些特定库的答案，请参考它。

目前你的问题很模糊，我只能回答你需要使用类似Data.Map的结构来首先积累中间结果，然后通过查询这个中间数据结构来重新排列它们。正如它的文档所指出的，它的大多数访问器函数的复杂性是O(log n)，这是非常有效的。

您不应该期望任何数据库库提供这种功能，因为问题太具体了。

于 2013-03-15T14:49:46.700 回答