訪問每個節點

Question

我有一個愛好項目，該項目是關於建立一個樹來存儲標識號。我已經使用數字，保存在節點，即節點可以是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' 

你有意見，我該怎麼辦呢？ （建議是prefferred是算法）

Answer 1

什麼

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) 

Answer 2

BTW：這甚至可以在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)