过滤数据树,构建新树

Filtering a data tree, building a new tree

给定一棵数据树class:

class DataTreeNode<T> : IEnumerable<DataTreeNode<T>> 
{
    public KeyValuePair<T, int> Data
    {
        get;
        set;
    }
    public DataTreeNode<T> Parent {get; set;}
    public ICollection<DataTreeNode<T>> Children {get; set;}
.....
}

数据 属性 包含数据的键和数据类型的值。 并给定一个树实例,我需要构建一个子树过滤如下:

一个。仅包含叶节点的某些值 (Data.Key)

b。叶子的路径符合:

  1. 仅包含特定类型的节点 (Data.value)

  2. 不包含某些类型的节点(Data.value)

我尝试提取所有可能的路径作为节点列表,过滤列表并重建树,但到目前为止还没有成功。

我的直觉是应该使用一些递归之王来完成,但我不知道如何在递归中进行过滤和新树的构造。

从递归函数中遍历树开始,可能会在每个节点打印路径以查看发生了什么。

然后,不用打印,而是应用过滤器并向结果树中添加一个新节点,其中包含当前节点的内容。

这是解决方案(不是递归的): 构建从根到每个叶子的路径列表。 然后构建一棵新树过滤每条路径:

DataTreeNode<string> createFilteredTree(List<List<DataTreeNode<string>>> paths, List<int> types, List<bool> flags, string filter, string title)
    {
        DataTreeNode<string> root = new DataTreeNode<string> (new keyValuePair<string, int> ("SEARCH RESULTS", 0));
        foreach (List<DataTreeNode<string>> path in paths)
        {
            if (!passesFilter (path, types, flags, filter))
                continue;//don't need this path
            path.Reverse ();
            DataTreeNode<string> curNode = root;
            DataTreeNode<string> found;
            foreach (DataTreeNode<string> node in path)
            {
                found = curNode.FindTreeNode (node1 => node1.Data.Equals (node.Data));
                if (found == null)
                {
                    found = node.Clone ();
                    curNode.AddChild (found);
                }
                curNode = found;
            }
        }
        return root;
    }