樹組合和分區

Question

我有一個包含字符串記錄的（非二進制）樹。

我想使包含數據的記錄陣列（或指針的記錄）如下...

我在此示出的示例：

 ABCDEFGHIJKL 
    / |  \ 
    ABC  DE  FGHIJKL 
/ \   / | \ 
AB  C  FGH IJK L 
        /\ 
        I JK 

結果應該是：
（7包含與此數據記錄陣列）

1. ABCDEFGHIJKL
2. ABC，DE，FGHIJKL
3. ABC，DE，FGH，I，JK，L
4. ABC，DE，FGH，IJK，L
5. AB，C，DE，FGHIJKL
6. AB，C，DE ，FGH，I，JK，L
7. AB，C，DE，FGH，IJK，L

一些注意事項：

• 我不關心的順序（1- 7）結果只要我讓他們全部。
• 我正在使用C＃
• 在這個示例中有7個路徑的4個級別，但在現實生活中它可以是任意數量的級別。
• 這裏的模式是從左到右的所有組合創建"ABCDEFGHIJKL"。

有沒有人有建議？

Answer 1

這個想法很簡單。只有根節點的列表，然後將其替換爲它的子節點。然後遞歸替換該列表中的每個節點，並在每次替換操作時將該列表添加到結果集合中。

這樣我們將在某些分支中得到重複的結果，所以我們將通過遞歸傳遞結果集合，並檢查當前節點列表是否已經存在。如果是，那麼它的派生列表也是如此，那麼就返回。

假設我們有一個類Tree，其節點類別爲Node（每個節點都有Children）。樹根是Root。然後你就可以實現你的功能，像這樣（的Tree類中）：

public List<List<Node>> GetLevels() { 
    List<Node> nodes = new List<Node>(); 
    nodes.Add(Root); 
    List<List<Node>> result = new List<List<Node>>(); 
    GetLevelsCore(nodes, result); 
    return result; 
} 
void GetLevelsCore(List<Node> nodes, List<List<Node>> result) { 
    if(result.Any(list => list.SequenceEqual(nodes))) return; 
    result.Add(nodes); 

    foreach(Node node in nodes) { 
     if(node.Children.Count != 0) { 
      List<Node> replacedNodes = new List<Node>(nodes); 
      int index = replacedNodes.IndexOf(node); 
      replacedNodes.RemoveAt(index); 
      replacedNodes.InsertRange(index, node.Children); 

      GetLevelsCore(replacedNodes, result); 
     } 
    } 
} 

我得到的結果：

List<List<Node>> result = tree.GetLevels(); 
List<string> strings = new List<string>(result.Select(nodes => string.Join(", ", nodes.Select(node => node.Value)))); 

strings：

1. 「ABCDEFGHIJKL」
2. 「ABC ，DE，FGHIJKL「
3. 」AB，C，DE，FGHIJKL「
4. 「AB，C，DE，FGH，IJK，L」
5. 「AB，C，DE，FGH，I，JK，L」
6. 「ABC，DE，FGH，IJK，L」
7. 「ABC，DE，FGH，I，JK，L」

UPD：替換包含使用Any進行檢查（），現在不需要相等比較器。

Answer 2

如果我理解你 - 你的樹看起來（可能）像這樣，其中.表示一個有子節點但沒有「內容」的節點，AB表示一個節點的文本內容爲「AB」。

         . 
           / |  \ 
           .  DE  . 
          /\  / | \ 
          AB C  FGH . L 
              /\ 
              I JK 

ie：一個具有3個子節點的根節點（1是包含文本「DE」的葉節點）。

我假設你已經有了你的數據結構，它將成爲一棵樹，每個節點可以有3個子節點，一個父節點和一個可選的文本字段。例如：

class Node 
{ 
    // NB: I would not implement the class exactly like this - for illustrative purposes only. 
    Node Left; 
    Node Mid; 
    Node Right; 
    string Text; 
} 

想要實現的是遍歷樹並連接所有文本在特定級別或低於特定級別？

因此，像，

• 級別4：I + JK = 「IJK」
• 3級：AB + C + FGH +（I + JK）+ L = 「ABCDFGHIJKL」
• 等級2：（AB + C）+ DE +（FGH +（I + JK）+ L）=「ABCDEFGHIJKL」

要以這種方式處理樹，您可能必須使用遞歸。您需要編寫一個recursive function來查找所需的節點，跟蹤深度等，並執行所需的文本/數據操作。

對此有幫助的一種方法是在插入時將每個節點的深度存儲在樹中，如果有控制權的話。

例如，剛剛發現你一定級別的所有節點的文本很簡單的遞歸函數可能看起來有點像這樣的東西：

//NB: Comes with no warrentee and untested :). 
public string TextAtLevel(Node root, int maxLevel, int currentLevel) 
{ 
    currentlevel += 1; 

    if(currentLevel == maxLevel) 
    { 
     // stop the recursion, return text of this node 
     return root.Text; 
    } 
    else 
    { 
     //Recurse into the child nodes. Left to right, depth first. 
     return TextAtLevel(root.Left, maxLevel, currentLevel) + 
       TextAtLevel(root.Mid, maxLevel, currentLevel) + 
       TextAtLevel(root.Right, maxLevel, currentLevel) 
    } 

} 

Node treeRoot = LoadData(); // imagine tree being populated as per diagram. 
string textAtLevel4 = TextAtLevel(treeRoot, 4, 0); // returns "IJK" 

希望這可以幫助您開始使用。