재귀는 무한 트리 나는 왼쪽에서 오른쪽으로 카운팅, 각 노드에 번호 <code>n</code>을 할당 할</p> <pre><code>type LazyTree<'T> = | LazyBranch of 'T * ('T LazyTree list Lazy) </code></pre> <p>에 의해

Question

내가 표현 나무가 왼쪽에서 오른쪽 열거합니다.

더 공식적으로

편집 : 노드 a를 들어

, h(a)=0a는 노드 a를 들어 아이

부모 p와 노드 a를 들어

, h(a)=h(p+1)

가없는 경우 , 부모가없는 경우 L(a)은 빈 세트입니다.

부모가있는 노드 a, 들어

, L(a)이 루트에서 각 노드 i, 경로 노드 a를 들어 a

를 포함하지 않는 모든 노드의 집합입니다, S(a)는 모든 요소이다 각 요소 ih(i)<=h(a)

보유 L(a), I는 S(a)의

의 크기와 각 노드 a 값을 바꿔야

부작용이없는 문제점을 해결할 수 없습니다.

내 함수는 트리를 반환해야합니다.

노드는 왼쪽 형제 노드에 종속됩니다. 따라서 함수는 'T LazyTree Option을 매개 변수로 가져야합니다.

하지만 가장 왼쪽에있는 자식은 우리에게 가장 가까운 형제에 종속됩니다. 우리는 무한한주기를 가졌습니다.

나는 유한 트리에서 어떻게 해결해야 하는지를 묻지 않는다.

---

추상적 인 개념에 대해서는 묻지 않습니다. 여기 내가 다른 하나 무한 트리를 반환 할 수있는 방법입니다 :

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

은 무한 트리 (비 지연) 통과를 필요로하기 때문에이 같은 번호를 할당하는 것이 불가능하다. 는 당신이 필요로하는 것은이 의사 코드와 같이 폭 우선 탐색입니다 :

let traverse (node:LazyTree<'T>) = 
    let q = System.Collections.Generic.Queue() 
    q.Enqueue node 
    let mutable i = 0 
    while 0 < q.Count do // always TRUE 
     let node = q.Dequeue() 
     printfn "Node #%i: %A" i node.Map 
     i <- i + 1 
     for child in node.Children.Force() do 
      q.Enqueue child 

Answer 2

맞아요 여기에 필요한 재귀 구조가 다소 복잡한입니다. 하나의 접근법이 있습니다. 헬퍼 함수 number을 사용하여이 목록과이 목록의 첫 번째 트리의 첫 번째 자식 사이에있는 모든 번호 매겨진 트리뿐만 아니라 바로 앞에 번호가 매겨진 트리가 주어진 트리의 목록에 번호를 매 깁니다.그런 다음, 목록이 비어 있지 않은 경우 :

1. 원하는리스트의 꼬리 이전 트리로리스트의 머리를 번호의에 - - 계산 결과를 전달하고 추가, 재귀 적으로 계산 될 수있다 그 목록의 하위 항목은 두 번째 요소의 하위 항목 앞에 있기 때문에 "중간"목록으로 이동합니다.
2. 목록의 헤드에 해당하는 번호가 매겨진 트리는 이전 값 다음의 값을 값으로 취합니다. 이 노드의 자식도 재귀 적으로 계산할 수 있습니다. 모두의 번호가 매겨진 나무가 머리와 자식에 해당하는 사이에 있다고 가정합니다. 이 목록의 꼬리 뒤에서 시작하는 요소 만있는 기존 중간 시퀀스와 약간 다릅니다. 따라서 1 단계에서 계산 된 목록의 꼬리를 기존 "중간"목록 앞에 추가해야합니다 . 그런 다음 헤드 노드의 첫 번째 자식 바로 앞의 노드는 해당 노드가있는 경우이 새로운 중간 시퀀스의 마지막 요소 일 뿐이며 그렇지 않은 경우에는 번호가 지정된 트리 자체입니다 (이 작업은 노드 사이에 노드가없는 경우 발생할 수 있습니다. 노드 및 그 자식). 그리고 아이들과 사이의 노드는 첫 번째 자식 인입니다.이 새로운 중간 시퀀스의 자식입니다.

이 설명이 밝혀지지 않아서 불편을 끼쳐 드려 죄송합니다. 그림을 그리면 도움이됩니다. 어쨌든, 해당 코드는 다음과 같습니다.

// 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