搜索在模板树

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; } 

问题是我如何实现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<X>，如果有人告诉你找到一个DataNode<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"));