数据结构设计

Question

我有很多嵌套类的大型基础架构，我正在寻找正确的设计模式。

我将解释： 我有一个名为“标题”阶级和阶级称为项目 A标题包含不同的项目，每个项目包含不同的数据

您可以在原理图中的标题看到的还包含ITEMLIST包含更多的项目。每个项目都可以包含项目 。

我加入了基础设施的示意图，它看起来像一个非二叉树

我正在寻找此对象的最佳数据结构，

要求：

1. 使用节点ID和树节点我将能够快速找到节点
2. 良好的代码维护性
3. 可以从平面切换到树状并从树状切换到平面

Answer 1

您的问题似乎要求快速访问给定ID值的节点，而不考虑层次结构。在这种情况下，您可能会最好（如Daniel Gabriel在评论中所建议的那样）创建一个优化用于“搜索”ID的平面列表的平面列表，因为您的查找操作不关心层次结构。仅仅因为你的对象是树形结构并不意味着你不能在另一个结构中索引它们。字典应该非常擅长 - 关键可能是一个整数（或者任何你的节点ID），并且该值可能指向节点对象实例。你只需要记住保持这个结构与你的树结构同步。删除节点时从字典中删除键，并在添加节点时将它们添加到字典中（如果结构是动态的）。

这满足您的要求＃1和可能＃2（如果您需要在同一类中封装索引的同步）。对于＃3我们可能需要更多信息，但如果您保持这些结构同步，则您将始终可以访问这两种格式而无需转换。应该很容易。

下面是一个说明如何封装的结构，可以在任何时候都同时提供扁平索引和树形结构的一些示例代码：

class Program 
{ 
    static void Main(string[] args) 
    { 
    Node<int, string> node1 = new Node<int, string>(1, "One"); 
    Node<int, string> node2 = new Node<int, string>(2, "Two"); 
    Node<int, string> node3 = new Node<int, string>(3, "Three"); 
    Node<int, string> node4 = new Node<int, string>(4, "Four"); 
    node2.Parent = node1; 
    node3.Parent = node1; 
    node4.Parent = node2; 
    Console.WriteLine(node1.GetDump()); 

    Node<int, string> node5 = new Node<int, string>(5, "Five"); 
    // Test spliting the tree attaching it and it's subtree to another parent 
    node2.Parent = node5; 
    Console.WriteLine(node1.GetDump()); 
    Console.WriteLine(node5.GetDump()); 

    // Test re-attaching the detached parent as a child 
    node1.Parent = node2; 
    Console.WriteLine(node5.GetDump()); 

    // Test moving a node to another parent within the tree 
    node1.Parent = node5; 
    Console.WriteLine(node5.GetDump()); 
    } 
} 

/// <summary> 
/// Create a tree structure whose nodes are of type T and are indexed by ID type I 
/// </summary> 
/// <typeparam name="I">Type of the index</typeparam> 
/// <typeparam name="T">Type of the node</typeparam> 
class Node<I, T> 
{ 
    private Dictionary<I, Node<I, T>> rootIndex; // Shared flat index 
    public I Id { get; private set; } 
    public T Value { get; set; } 
    private Node<I, T> parent; 
    List<Node<I, T>> childNodes; 

    public Node(I id, T value) 
    { 
    this.Id = id; 
    this.Value = value; 
    this.childNodes = new List<Node<I, T>>(); 
    } 

    public string GetDump() 
    { 
    System.Text.StringBuilder sb = new StringBuilder(); 
    if (parent == null) 
    { 
     foreach (KeyValuePair<I, Node<I,T>> node in rootIndex) 
     { 
      sb.Append(string.Format("{0}:{1} ", node.Key, node.Value.Value)); 
     } 
     sb.AppendLine(); 
    } 
    sb.AppendLine(string.Format("ID={0}, Value={1}, ParentId={2}", Id, Value, 
     (parent == null)?"(null)":parent.Id.ToString())); 
    foreach (Node<I, T> child in childNodes) 
    { 
     string childDump = child.GetDump(); 
     foreach (string line in childDump.Split(new string[] {Environment.NewLine}, 
      StringSplitOptions.RemoveEmptyEntries)) 
     { 
      sb.AppendLine(" " + line); 
     } 
    } 
    return sb.ToString(); 
    } 

    private void RemoveFromIndex(Dictionary<I, Node<I, T>> index) 
    { 
    index.Remove(Id); 
    foreach(Node<I, T> node in childNodes) 
     node.RemoveFromIndex(index); 
    } 

    private void ReplaceIndex(Dictionary<I, Node<I, T>> index) 
    { 
    rootIndex = index; 
    rootIndex[Id] = this; 
    foreach (Node<I, T> node in childNodes) 
     node.ReplaceIndex(index); 
    } 

    public Node<I, T> Parent 
    { 
    get 
    { 
     return parent; 
    } 
    set 
    { 
     // If this node was in another tree, remove it from the other tree 
     if (parent != null) 
     { 
      // If the tree is truly a separate tree, remove it and all nodes under 
      // it from the old tree's index completely. 
      if (value == null || (parent.rootIndex != value.rootIndex)) 
      { 
       // Split the child's index from the parent's 
       Dictionary<I, Node<I, T>> parentRootIndex = parent.rootIndex; 
       RemoveFromIndex(parentRootIndex); 
       rootIndex = new Dictionary<I, Node<I, T>>(); 
       ReplaceIndex(rootIndex); 
      } 

      // Remove it from it's old parent node's child collection 
      parent.childNodes.Remove(this); 
     } 
     // These operations only apply to a node that is not being removed 
     // from the tree 
     if (value != null) 
     { 
      // If parent does not already have an index, create one with itself listed 
      if (value.rootIndex == null) 
      { 
       value.rootIndex = new Dictionary<I, Node<I, T>>(); 
       value.rootIndex[value.Id] = value; 
      } 
      // If the index for the child node is separate form that of the parent 
      // node, merge them as appropriate 
      if (this.rootIndex != value.rootIndex) 
      { 
       // If this node has a complete index, merge the two tree indexes 
       // into the parent's index 
       if (this.rootIndex != null) 
       { 
       foreach (KeyValuePair<I, Node<I, T>> node in rootIndex) 
       { 
        if (value.rootIndex.ContainsKey(node.Key)) 
         throw new InvalidOperationException(string.Format(
         "Node Id {0} in child tree already exists in the parent", 
         node.Key)); 
        value.rootIndex[node.Key] = node.Value; 
       } 
       } 
       else 
       { 
       // If this node does not have an index, it is not a tree; 
       // just add it to the parent's index. 
       if (value.rootIndex.ContainsKey(this.Id)) 
        throw new InvalidOperationException(string.Format(
        "Node Id {0} already exists in the parent's tree.", Id)); 
       value.rootIndex[this.Id] = this; 
       } 
      } 
      // Make all nodes in a tree refer to a common root index. 
      this.rootIndex = value.rootIndex; 
      // Attach this node to the tree via the parent's child collection. 
      value.childNodes.Add(this); 
     } 
     // Attach this node to the tree via this node's parent property 
     // (null if removing from the tree) 
     this.parent = value; 
    } 
    } 


}