定義樹+ ocaml中的子樹的指針

Question

如何在OCaml中定義樹+指向其子樹的指針，以便在該子樹中添加樹葉需要一定的時間？

Answer 1

如果您想要使用純粹的函數表示法，那麼由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 

Answer 2

另一（更簡單和更普通）溶液對二進制tree：

type 'a t = { 
    value : 'a; 
    mutable left : 'a t option; 
    mutable right : 'a t option; 
} 

使用此類型，可以獨立設置左右子樹當他們變得需要時。