如何找到最左边的叶子然后将拉链聚焦在那里

问题描述 投票:0回答:0

从一棵二叉树,我想构建一个以最左边的叶子为焦点的拉链。

type ('a, 'b) bin_tree =
  | Leaf of 'b
  | Node of 'a * ('a, 'b) bin_tree * ('a, 'b) bin_tree
              
type ('a, 'b) bin_context = 
  | Top
  | LContext of ('a * ('a, 'b) bin_context * ('a, 'b) bin_tree)
  | RContext of ('a * ('a, 'b) bin_context * ('a, 'b) bin_tree)

type ('a, 'b) t = BZ of ('a, 'b) bin_context * ('a, 'b) bin_tree 

这是我试过的:

(* val leftest_leaf_zipper : ('a,'b) t -> ('a,'b) z *)
let rec leftest_leaf_zipper t = 
  match t with
  | Node(v, l, r) -> 
    begin
      match l with 
      | Node(v, l, r) -> BZ(RContext(v, ?, r), leftest_leaf_zipper l)
      | Leaf _ -> BZ(LContext(v, ?, l), leftest_leaf_zipper r)
    end
  | Leaf(b) -> Leaf(b) 

但是我看不到如何跟踪父节点的左右上下文,这是如何实现的?

functional-programming ocaml
© www.soinside.com 2019 - 2024. All rights reserved.