如何在OCaml中定義樹+指向其子樹的指針,以便在該子樹中添加樹葉需要一定的時間?定義樹+ ocaml中的子樹的指針
4
A
回答
7
如果您想要使用純粹的函數表示法,那麼由nlucaroni建議的拉鍊確實是表示數據結構深處的遊標的好方案,可以移動或用於更新結構。
如果您希望使用就地突變的解決方案,則可以通過mutable
記錄字段或從其派生的參考文獻(ref
)使用可變數據。例如:
type 'a tree_cell = {mutable node : 'a tree}
and 'a tree = Leaf of 'a | Branch of 'a tree_cell * 'a * 'a tree_cell
如果你持有的'a tree_cell
,你可以變異它(在恆定的時間)。
let head {node = (Leaf x | Branch(_, x, _))} = x
let duplicate cell =
cell.node <- Branch (cell, head cell, {node = cell.node})
編輯:在你的問題的評論,你似乎表明你在正叉樹的解決方案興趣。
一般n進制情況下,可以表示爲
type 'a tree_cell = {mutable node: 'a tree}
and 'a tree = Branch of 'a * 'a tree_cell list
而拉鍊溶液看起來像(未測試的代碼)
type 'a tree = Branch of 'a * 'a forest
and 'a forest = 'a tree list
(* the data between the current cursor and the root of the tree *)
type 'a top_context = Top | Under of 'a * 'a tree * 'a top_context
(* a cursor on the 'data' element of a tree *)
type 'a data_cursor = top_context * 'a tree list
(* plug some data in the hole and get a tree back *)
val fill_data : 'a data_cursor -> 'a -> 'a tree
(* a cursor on one of the children of a tree *)
type 'a list_zipper = 'a list * 'a list
type 'a children_cursor = top_context * 'a * 'a tree list_zipper
(* plug some subtree in the hole and get a tree back *)
val fill_children : 'a children_cursor -> 'a tree -> 'a tree
(* carve a data hole at the root; also return what was in the hole *)
val top_data : 'a tree -> 'a data_cursor * 'a
(* fill a data hole and get a cursor for the first children in return
-- if it exists *)
val move_down : 'a data_cursor -> 'a -> ('a children_cursor * 'a tree) option
(* fill the children hole and carve out the one on the left *)
val move_left : 'a data_cursor -> 'a tree -> ('a data_cursor * 'a tree) option
val move_right : 'a data_cursor -> 'a tree -> ('a data_cursor * 'a tree) option
(* fill the children hole and get a cursor on the data *)
val move_up : 'a children_cursor -> 'a tree -> 'a data_cursor * 'a
+0
是的,我認爲這是我正在尋找的。謝謝! – mencaripagi 2012-02-16 09:01:13
4
另一(更簡單和更普通)溶液對二進制tree:
type 'a t = {
value : 'a;
mutable left : 'a t option;
mutable right : 'a t option;
}
使用此類型,可以獨立設置左右子樹當他們變得需要時。
相關問題
- 1. 指針的樹頭
- 2. B樹中的指針
- 3. 在Raven中存儲具有父指針和子指針的樹
- 4. OCaml的二叉樹
- 5. OCaml的 - 一棵樹
- 6. 摺疊樹OCaml中
- 7. 樹指針結構
- 8. OCaml中的空樹類型
- 9. OCaml - 遍歷樹
- 10. OCaml:樹函數
- 11. Ocaml樹函數
- 12. C中的結構,指針和樹木
- 13. 紅色黑樹中的虛空指針
- 14. Rust中的基本樹和指針
- 15. ocaml的 - 建立二叉樹
- 16. OCaml選項值樹
- 17. C++樹指針錯誤
- 18. 空指針彈出樹
- 19. 二叉樹智能指針
- 20. B樹具有指針
- 21. 計算ocaml中樹中的節點數
- 22. 在OCaml中抽象語法樹的S-表達式樹
- 23. 樹遍歷 - 從只有父指針的樹葉開始?
- 24. 確定樹是否是其他樹的子樹的算法
- 25. OCaml - 解析樹中級別的節點
- 26. 在Ocaml的'樹中添加元素
- 27. OCaml中多路樹的最大值
- 28. 用指針製作的稀疏AABB樹?
- 29. KD樹 - 難以理解的指針
- 30. 創建二叉樹的指針麻煩
在OCaml的純子集中,數據是不可變的。所以你不能將樹葉添加到樹上。你只能製作一棵與老樹相似但有額外葉子的新樹。如果您使用OCaml的不純的構造,解決方案將與任何命令式語言一樣。你能顯示迄今爲止你已經嘗試過的代碼嗎? – 2012-02-14 20:17:40
在OCaml的不純的子集中,數據是可變的。你可以改變記錄,字符串,記錄,所以你在OCaml中找到的是確實可能的,而不是純粹的語言。 – 2012-02-14 22:52:59
@Jeffrey:我所做的只是沿着路徑加入葉子,所以類似於, 'type tree = Empty | 'a *樹列表節點 讓rec添加路徑=函數 |空 - >節點(a,[]) | Node(s,c) - > if(空路徑)then Node(s,Node(a,[]):: c)else 節點(s,List.map(fun x - > if(greater_than path(path_to然後添加一個(減去路徑(path_to x))else x)c)' 然而,我使用的路徑在下一步構建樹時會變得更長,所以像指針一樣會很方便。可能我會在這裏嘗試一些建議,拉鍊或可變記錄。 – mencaripagi 2012-02-15 00:40:20