0

我有一个爱好项目，它是关于创建一棵树来存储标识号。我使用了数字，存储在节点上，即节点可以是 0 1 2 3 4 5 6 7 8 9。

创建树后，我想从树中撰写列表。但是，我找不到一种算法来管理我的目标。

我想要的是 ：

      "recompose tree"  will return list of numbers. For below tree it should be 

            [ 2, 21, 243, 245, 246, 78, 789 ]  


                               Root 
                           /          \         
                        2*               7
                      /      \             \                  
                   1*         4              8*    
                            / \  \            \         
                           3*  5* 6*           9*

       my data type :  data ID x = ID ( ( x, Mark ), [ ID x ] ) 
                       data Mark = Marked | Unmarked

       EDIT:

       for convenience : * shows it is marked
                         I have stored digit as char, actually not 1, 
                            it is stored as'1'

你有什么建议我该怎么做？（建议最好是算法）

4

2 回答 2

3

关于什么

recompose :: Num a => ID a -> [a]
recompose = go 0
  where
    go acc (ID ((n, Marked), ids)) =
      let acc' = 10 * acc + n
      in  acc' : concatMap (go acc') ids
    go acc (ID ((n, Unmarked), ids)) =
      let acc' = 10 * acc + n
      in  concatMap (go acc') ids

?

也就是说，我们遍历树，同时累积从根到节点的路径的值。在每个节点上，我们通过将路径的值乘以 10 并将节点的值添加到它来更新累加器。遍历生成标记节点的所有累加器值的列表：因此，在标记节点处，我们将累加器值添加到列表中，对于未标记节点，我们只是传播我们为节点的子节点收集的列表。

我们如何计算节点子节点的列表？go我们通过将遍历函数 ( ) 映射到子列表上来递归调用所有子函数。这给了我们一个列表列表，我们将这些列表连接起来以获得一个列表。（concatMap f xs只是concat (map f xs))或concat . map f。）

在属性语法术语中：累加器用作继承属性，而返回的列表是合成属性。

作为改进，我们可以引入一个辅助函数isMarked，

isMarked :: Mark -> Bool
isMarked Marked   = True
isMarked Unmarked = False

这样我们就可以简洁地写

recompose :: Num a => ID a -> [a]
recompose = go 0
  where
    go acc (ID ((n, m), ids)) =
      let acc'   = 10 * acc + n
          prefix = if isMarked m then (acc' :) else id
      in  prefix (concatMap (go acc') ids)
于 2012-04-20T10:35:17.723 回答
2

顺便说一句：这甚至可以在 sql 中完成：

DROP SCHEMA tmp CASCADE;

CREATE SCHEMA tmp ;
SET search_path='tmp';

CREATE TABLE the_tree
        ( id CHAR(1) NOT NULL PRIMARY KEY
        , parent_id CHAR(1) REFERENCES the_tree(id)
        );
INSERT INTO the_tree(id,parent_id) VALUES
 ( '@', NULL)
,( '2', '@')
,( '7', '@')
,( '1', '2')
,( '4', '2')
,( '3', '4')
,( '5', '4')
,( '6', '4')
,( '8', '7')
,( '9', '8')
        ;

WITH RECURSIVE sub AS (
        SELECT id, parent_id, ''::text AS path
        FROM the_tree t0
        WHERE id = '@'
        UNION
        SELECT t1.id, t1.parent_id, sub.path || t1.id::text
        FROM the_tree t1
        JOIN sub ON sub.id = t1.parent_id
        )
SELECT sub.id,sub.path
FROM sub
ORDER BY path
        ;

结果：（postgresql）

NOTICE:  drop cascades to table tmp.the_tree
DROP SCHEMA
CREATE SCHEMA
SET
NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "the_tree_pkey" for table "the_tree"
CREATE TABLE
INSERT 0 10
 id | path 
----+------
 @  | 
 2  | 2
 1  | 21
 4  | 24
 3  | 243
 5  | 245
 6  | 246
 7  | 7
 8  | 78
 9  | 789
(10 rows)
于 2012-04-20T10:52:00.020 回答