搜索在模板樹

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"));