algorithm - 递归从左到右枚举一棵无限树

Question

我有一棵树表示

type LazyTree<'T> =
    | LazyBranch of 'T * ('T LazyTree list Lazy) 

我要分配一个号码n到每个节点，从左到右计数。

更正式一些

已编辑:

对于一个节点a , h(a)=0如果a没有 child

对于一个节点a与 parent p , h(a)=h(p+1)

对于一个节点a ，没有 parent ，L(a)是一个空集。

对于一个节点a ，它有一个父级，L(a)是一组所有节点，其中每个节点 i ，从根到它的路径不包含 a

对于一个节点a , S(a)是 L(a) 的所有元素，其中每个元素 i持有 h(i)<=h(a)

我需要替换每个节点的值 a大小为 S(a)

我无法为我的问题想出一个不涉及副作用的解决方案。

我的函数应该返回一棵树。

它的节点依赖于左兄弟节点。所以，函数应该得到一个 'T LazyTree Option作为参数。

但是它最左边的 child 依赖于我们最右边的 sibling ，而我们最右边的 sibling 又依赖于我们。看来，我们得到了一个无限循环。

我不是在问如何在有限树上解决它。

---

我问的不是抽象概念。这是我如何从另一棵无限树返回一棵无限树:

type LazyTree<'T> =
    | LazyBranch of 'T * ('T LazyTree list Lazy)
with
    member this.Item = match this with LazyBranch(item,_) -> item
    member this.Children = match this with LazyBranch(_,children) -> children
member this.Map func =
        let children =
            lazy
            (
                this.Children.Force()
                |> List.map (fun child -> child.Map func)
            )
        LazyBranch(func this.Item, children)

Answer 1

您说得对，这里所需的递归结构有些复杂。这是一种方法。我将使用一个辅助函数 number，它给一个树列表编号，给定紧接在前面的编号树以及该列表和该列表中第一棵树的第一个子树之间的所有编号树。然后，如果列表非空:

1. 可以递归计算所需列表的尾部，将列表头部编号的待计算结果作为前一棵树传入，并将该列表的子级附加到“中间”列表，因为它们出现在第二个元素的子元素之前。
2. 与列表头部对应的编号树只取其前导数之后的下一个数字作为其值。该节点的子节点也可以递归计算。考虑所有与头部对应的树及其子树之间的编号树；这与现有的中间序列略有不同，后者仅包含在此列表尾部之后开始的元素，因此我们需要将步骤 1 中计算的列表的尾部附加到现有“中间”列表的前面.然后紧接在头节点的第一个 child 之前的节点只是这个新的中间序列的最后一个元素，如果有这样一个节点，或者如果没有这样的编号树本身(如果没有节点之间会发生这种情况)节点及其子节点)。 child 和他们的第一个 child 之间的节点就是这个新的中间序列的 child 。

抱歉，如果此描述没有启发性，但画图可能会有所帮助。无论如何，这是相应的代码:

// These help with type inference
let value (LazyBranch(v,_)) = v
let children (LazyBranch(_,ts)) = ts.Value

let numberedTree =
    let rec number prev between = function
    | [] -> []
    | t::ts ->
        let rec rest = number first (seq { yield! between; yield! children first }) ts
        and first =
            let between' = seq { yield! rest; yield! between }
            LazyBranch(value prev + 1, lazy (children t |> number (defaultArg (Seq.tryLast between') first) (between' |> Seq.collect children)))
        first::rest
    fun t ->
        let rec result = LazyBranch(0, lazy number result [] (children t))
        result