在模板树上搜索

Question

所以我有 2 个接口：

一个可以有子节点的节点

public interface INode
{
    IEnumeration<INode> Children { get; }
    void AddChild(INode node);
}

和一个可以有与之关联的数据的派生“数据节点” 请

public interface IDataNode<DataType> : INode
{
    DataType Data;
    IDataNode<DataType> FindNode(DataType dt);
}

记住，树中的每个节点都可以有一个不同的数据类型与其关联作为其数据（因为INode.AddChild 函数仅采用基本 INode）

以下是 IDataNode 接口的实现：

internal class DataNode<DataType> : IDataNode<DataType>
{
    List<INode> m_Children;

    DataNode(DataType dt)
    {
        Data = dt;
    }

    public IEnumerable<INode> Children
    {
        get { return m_Children; }
    }

    public void AddChild(INode node)
    {
        if (null == m_Children)
            m_Children = new List<INode>();

        m_Children.Add(node);
    }   

    public DataType Data { get; private set; }

问题是，在不知道在树中会遇到哪种 DataType 的情况下，如何实现 FindNode 函数？

    public IDataNode<DataType> FindNode(DataType dt)
    {
        throw new NotImplementedException();    
    }
}

正如您可以想象的那样，

    public IDataNode<DataType> FindNode(DataType dt)
    {
        IDataNode<DataType> result = null;

        foreach (var child in Children)
        {
            if (child is IDataNode<DataType>)
            {
                var datachild = child as IDataNode<DataType>;

                if (datachild.Data.Equals(dt))
                {
                    result = child as IDataNode<DataType>;
                    break;
                }
            }
            else 
            {
                 // What??
            }

            // Need to recursively call FindNode on the child
            // but can't because it could have a different
            // DataType associated with it. Can't call FindNode 
            // on child because it is of type INode and not IDataNode
            result = child.FindNode(dt); // can't do this!

            if (null != result)
                break;
       }

       return result; 
    }

当我知道我使用的特定树将具有什么类型的数据类型时，我唯一的选择是这样做吗？也许我以错误的方式处理这个问题，所以任何提示都会受到赞赏。谢谢！

Answer 1

首先，您需要将FindNode方法放入INode中。否则，在找到 DataType 类型的节点之前，您无法找到某种类型 DataType 的节点。即使您知道的对象是 DataNode 的引用，如果有人告诉您查找 DataNodeDataNode，这对您也无济于事;Y>。

现在您可以采取两条路：如果您希望将 DataNode 模板化，那么您需要在编译时了解树中所有可能的数据类型。如果您知道这一点，则可以使用通用的 DataNode。如果您有可能想要找到一个节点，该节点包含某种类型的数据，而这些数据只能在运行时为您所知（例如，从您无法控制的某些方法的返回值），那么您不能使用泛型。

我将在下面说明通用解决方案。

public interface INode
{
    IEnumerable<INode> Children { get; }
    IDataNode<DataType> FindNode<DataType>(DataType value);
    void AddChild(INode node);
}

public interface IDataNode<DataType> : INode
{
    DataType Data { get; }
}

INode.FindNode 可以这样实现：

public IDataNode<DataType> FindNode<DataType> (DataType value) {
    // If we are searching for ourselves, return this
    var self = this as IDataNode<DataType>;
    if (self != null && self.Data.Equals(value)) {
        return self;
    }

    // Otherwise:
    // 1. For each of our children, call FindNode on it. This will
    //    find the target node if it is our child, since each child
    //    will check if it is the node we look for, like we did above.
    // 2. If our child is not the one we are looking for, FindNode will
    //    continue looking into its own children (depth-first search).
    // 3. Return the first descendant that comes back and is not null.
    //    If no node is found, FirstOrDefault means we will return null.
    return this.children.Select(c => c.FindNode(value))
                        .FirstOrDefault(found => found != null);
}

我不得不说，上面使用 LINQ 的递归实现可能过于聪明，并且可能不太容易理解。它总是可以用 foreach 编写，以使其更清晰。

Answer 2

使用通用函数：

public IDataNode<DataType> FindNode<DataType>(DataType dt)
{
    IDataNode<DataType> result = null;

    foreach (var child in Children)
    {
        if (child is IDataNode<DataType>)
        {
            var datachild = child as IDataNode<DataType>;

            if (datachild.Data.Equals(dt))
            {
                result = child as IDataNode<DataType>;
                break;
            }
        }
        else 
        {
             // it's not a DataType You're looking for, so ignore it!
        }
   }

   return result; 
}

然后像这样调用它：

var resultsStr = tree.FindNode<string>("Hello");
var resultsInt = tree.FindNode<int>(5);
var resultsCust = tree.FindNode<MyCustomClass>(new MyCustomClass("something"));