6

タプルのリストint*stringがあります。ここで、intはレベル、stringは名前です。

let src = [
        (0, "root");
            (1, "a");
                (2, "a1");
                (2, "a2");
            (1, "b");
                (2, "b1");
                    (3, "b11");
                (2, "b2");
        ]

そして私はそれを次のように変換する必要があります

let expectingTree = 
    Branch("root", 
    [
        Branch("a",
            [
                Leaf("a1");
                Leaf("a2")
            ]);
        Branch("b",
            [
                Branch("b1", [Leaf("b11")]);
                Leaf("b2")
            ]);
    ]);

以下は私がそれをした方法ですが、それを達成するためのより良い方法で誰かがアドバイスすることができます。私はF＃を初めて使用しますが、同じことを行うC＃コードは少し短くなるので、間違っていると思います。

type Node = 
    | Branch of (string * Node list)
    | Leaf of string

let src = [
            (0, "root");
                (1, "a");
                    (2, "a1");
                    (2, "a2");
                (1, "b");
                    (2, "b1");
                        (3, "b11");
                    (2, "b2");
            ]

let rec setParents (level:int) (parents:list<int>) (lst:list<int*int*string>) : list<int*int*string> =
    //skip n items and return the rest
    let rec skip n xs = 
        match (n, xs) with
        | n, _ when n <= 0 -> xs
        | _, [] -> []
        | n, _::xs -> skip (n-1) xs

    //get parent id for given level
    let parentId (level) = 
        let n = List.length parents - (level + 1)
        skip n parents |> List.head 

    //create new parent list and append new id to begin
    let newParents level id =
        let n = List.length parents - (level + 1)
        id :: skip n parents

    match lst with
    | (id, l, n) :: tail -> 
                        if l = level then (id, parentId(l), n) :: setParents l (newParents l id) tail
                        elif l <= level + 1 then setParents l parents lst
                        else [] //items should be in order, e.g. there shouldnt be item with level 5 after item with level 3
    | _ -> []


let rec getTree (root:int) (lst: list<int*int*string>) =

    let getChildren parent = 
        List.filter (fun (_, p, _) -> p = parent) lst

    let rec getTreeNode (id:int) (name:string) =
        let children = getChildren id
        match List.length children with
        | 0 -> Leaf(name)
        | _ -> Branch(name, 
                        children
                        |> List.map (fun (_id, _, _name) -> getTreeNode _id _name))

    match getChildren root with
    | (id, _, n) :: _ -> getTreeNode id n
    | _ -> Leaf("")

let rec printTree (ident:string) (tree:Node) = 
    match tree with
    | Leaf(name) -> 
        printfn "%s%s" ident name
    | Branch(name, children) -> 
        printfn "%s%s" ident name
        List.iter (fun (node) -> printTree ("   " + ident) node) children

let tree = 
    src
    |> List.mapi (fun i (l, n) -> (i+1, l, n)) //set unique id to each item
    |> setParents 0 [0] //set parentId to each item
    |> getTree 0


printTree "" tree

Console.ReadKey() |> ignore
4

1 に答える 1

6

まず第一に、Leafブランチにサブツリーのリストが含まれている場合、葉はサブツリーのない単なるブランチであるため、実際には区別する必要はありません。したがって、次のツリー タイプを使用します。

type Tree = 
  | Branch of string * list<Tree>

リストをツリーに変換するコア関数は、明示的な再帰リスト処理を使用して実装する方がおそらく簡単です。1 回のパスで実行できます。要素を調べて、ネストされたインデックスが見つかったときはいつでも新しいブランチを開始するだけです (または、より小さなインデックスを取得する場合は、適切な数の再帰呼び出しから戻ります)。これは私の試みです：

/// Build a tree from elements of 'list' that have larger index than 'offset'. As soon
/// as it finds element below or equal to 'offset', it returns trees found so far
/// together with unprocessed elements.
let rec buildTree offset trees list = 
  match list with
  | [] -> trees, [] // No more elements, return trees collected so far
  | (x, _)::xs when x <= offset -> 
      trees, list // The node is below the offset, so we return unprocessed elements
  | (x, n)::xs ->
      /// Collect all subtrees from 'xs' that have index larger than 'x'
      /// (repeatedly call 'buildTree' to find all of them)
      let rec collectSubTrees xs trees = 
        match buildTree x [] xs with
        | [], rest -> trees, rest
        | newtrees, rest -> collectSubTrees rest (trees @ newtrees)
      let sub, rest = collectSubTrees xs []
      [Branch(n, sub)], rest

この関数は、これまでに収集された初期オフセットとツリーを取得します。treesパラメータは常に になり、[]initial には何らかの値が必要ですoffset。結果は、指定されたレベルより下のツリーのリストと残りの要素のリストです。

let res = buildTrees -1 [] src

ルートが -1 より上にあると仮定すると、タプルの 2 番目の部分 (空のリストである必要があります) を無視して、最初のツリー (1 つだけである必要があります) を取得できます。

/// A helper that nicely prints a tree
let rec print depth (Branch(n, sub)) =
  printfn "%s%s" depth n
  for s in sub do print (depth + "  ") s

res |> fst |> Seq.head |> print ""
于 2012-08-16T17:07:42.463 に答える