再帰を使用してツリーをフィルタリングする

Question

次のようなツリーがあります。私は基本的な考え方

 
A1 
    A2 
    A3 
    A4   
    A5 
    A6 

を返すために、これをフィルタリングする

 
A1 
    B1 
    B2 
    A2 
     A3 
     B3 
     A4   
    A5 
    C1 
    C2 
     C3 
     A6 

は、ノードのみを返すことです。私が午前闘争は、私はB1をドロップし、

私は木がノードのリストで構成され、C＃を使用しています

Answer 1

あなたがにしたいB2のレベルまでA2を引きたい場合A2にあります深さ探索（再帰）を行い、A以外のノードを排除するのですか？

私は途中でノードを削除し、子ノードを親ノード（現在のノードの位置）に挿入してから、非ノードにいるときはいつでもこのノードを削除します。

このような何か（、あなたは彼らがなどが繰り返されている間に変化するノードコレクションで注意する簡略化された擬似コードを持っている）：

void FilterNode(Node node) { 
    foreach (Node child in node.Children) { 
     FilterNode(child); 
    } 
    if (node.Type != NodeType.A) { 
     foreach (Node child in node.Children) { 
      node.Parent.InsertAfter(node, child); 
     } 
     node.Parent.RemoveNode(node); 
    } 
} 

Answer 2

これは私が見た前に私が思いついたのソリューションですルセロのソリューションは、私はあなたのツリー構造を仮定するつもりです

private List<NodesEntity> ReturnHierarchyFilteredByType(List<NodesEntity> nodesEntities, List<String> nodeTypes) 
{ 
    List<NodesEntity> _nodesEntities = new List<NodesEntity>(); 
    foreach (NodesEntity _nodesEntity in nodesEntities) 
    { 
    //We first recurse to the bottom 
    List<NodesEntity> _childNodesEntities = ReturnHierarchyFilteredByType(_nodesEntity.ChildNodes, nodeTypes); 

    if (nodeTypes.Contains(_nodesEntity.Type)) 
    { 
     //The node matches what we have in the list 
     _nodesEntities.Add(_nodesEntity); 
     _nodesEntity.ChildNodes = _childNodesEntities; 
    } 
    else 
    { 
     //We pull the child nodes into this level 
     _nodesEntities.AddRange(_childNodesEntities); 
    } 
    } 

    return _nodesEntities; 
} 

Answer 3

は次のようになります。

class Node<T> { 
    public readonly T Value; 
    public readonly LinkedList<Node<T>> Children; 
    public readonly bool IsEmtpy; 

    public Node() { 
     IsEmpty = true; 
    } 

    public Node(T value, LinkedList<Node<T>> children) { 
     Value = value; 
     Children = children; 
     IsEmpty = false; 
    } 
} 

単一の深さの最初の検索で1回のパスでツリーをフィルタリングできます。

通常、これらの種類のアルゴリズムを関数型言語でプロトタイプ化し、必要に応じてC＃に変換する方が簡単です。ここでF＃コードです：

type 'a tree = Nil | Node of 'a * 'a tree list 

// val filter : ('a -> bool) -> 'a tree list -> 'a tree list 
let rec filter f = function 
    | Node(value, children)::xs -> 
     if f value then Node(value, filter f children)::filter f xs 
     else (filter f children) @ filter f xs 
    | Nil::xs -> filter f xs 
    | [] -> [] 

let input = 
    Node("A1", 
     [ Node("B1", 
      [ Node("B2", []); 
       Node("A2", 
       [ Node("A3", []); 
        Node("B3", [ Node("A4", []) ]) ]) ]); 
      Node("A5", []); 
      Node("C1", 
      [ Node("C2", 
       [Node("C3", [ Node("A6", []) ]) ]) ]) ]) 

let expectedOutput = 
    Node("A1", 
     [ Node("A2", 
      [ Node("A3", []); 
       Node("A4", []) ]); 
      Node("A5", []); 
      Node("A6", []) ]) 

let actualOutput = [input] |> filter (fun value -> value.StartsWith("A")) |> List.head 

let testPasses = expectedOutput = actualOutput 

そしてF＃出力：

val testPasses : bool = true 

そしてここでは、同等のコードはC＃である：

static LinkedList<Node<T>> Filter(Func<T, bool> predicate, IEnumerable<Node<T>> input) { 
    var res = new LinkedList<Node<T>>(); 

    foreach(Node<T> node in input) { 
     if (!node.IsEmpty) { 
      if (predicate(node.Value)) { 
       res.AddLast(new Node(node.Value, Filter(predicate, node.Children)); 
      else { 
       res.AddRange(Filter(predicate, node.Children)); 
      } 
     } 
    } 

    return res; 
}