數據結構設計

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


}