在n樹實現中需要幫助

Question

我正在嘗試使用c＃實現n-ary類型的數據結構。該樹將具有一個根節點和一組子節點，並且子節點數組中的每個子節點也將具有一組子節點。我試圖做的是每當我們添加應該添加到葉節點中存在的所有子節點的子節點數組。我的代碼是

 public void addChildren(Node root, Node[] children) 
     { 

      if (root.children == null) 
      { 
       root.children = children; 

      } 
      else 
      { 
       for (int i = 0; i < root.children.Length; i++) 
       { 

        addChildren(root.children[i], children); 
       } 
      } 

     } 

主程序無限遞歸調用

 Dictionary<String, String[]> measurelist = new Dictionary<string, string[]>(); 
     String[] values = { "y", "n" }; 
     measurelist.Add("m1", values); 
     measurelist.Add("m2", values); 
     measurelist.Add("m3", values);   
     foreach (KeyValuePair<String, String[]> entry in measurelist) 
     { 
      Node[] children = new Node[entry.Value.Length]; 
      for(int i = 0; i < entry.Value.Length ;i ++) 
      { 
       Node child = new Node(entry.Key+":"+entry.Value[i]); 
       children[i] = child; 
      } 

      clustertree.addChildren(clustertree.root, children);    
     } 

但是這個代碼的結果。我試過但無法弄清楚發生了什麼問題？請幫我找出我做錯了什麼。 I have described the problem in the image

解決方案： 隨着你的幫助，我已經找到了解決這個問題。如果我解釋根本原因，我認爲這對其他可能面臨同樣問題的人會有所幫助。 問題的主要原因是當我傳遞節點的數組時，它將作爲參考而不是值傳遞。爲了確保相同的子數組引用不會傳遞給下一個遞歸調用，我已經更改了一些代碼。

這是我糾正代碼：再次

public void addChildren(Node root, Node[] children) 
     { 

      if (root.children == null) 
      { 

       root.children = children; 

      } 
      else 
      { 
       for (int i = 0; i < root.children.Length; i++) 
       {      
        Node[] children1 = new Node[children.Length]; 
      //I am creating a new array and nodes and passing the newly created array to          the next recursive call 
        for (int j = 0; j < children.Length; j++) 
        { 
         Node node = new Node(children[j].key);       
         node.children = children[j].children; 
         children1[j] = node; 
        } 
        addChildren(root.children[i], children1); 
       } 
      } 

     } 

謝謝:)

Answer 1

沒有創建樹正如您在圖中所示，而你正在做一些象下面這樣：

 R 
    /\ 
    / \ 
    a1 a2 (children of this are actually b1 and b2) 
/\ 
/ \ 
b1 b2 

當您添加b1, b2作爲a2的子女，你所引用的b1 and b2已被alreayd添加到a1。

在接下來的迭代中，當您添加c1 and c2，根據你的算法您引用c1 and c2既b1 and b2首先通過a1但你的功能在這裏不會停止，它通過a2再次進入b1 and b2這一次，但由於c1 and c2已經被添加作爲b1 and b2的孩子，該算法變得混亂並進入永久循環。

爲了解決這個問題：

查找樹但是到最後級別的最後一個級別只使用只有一個孩子，用遞歸路徑。

public boolean addChildren(Node root, Node[] children) 
{ 

    if (root.children == null) 
    { 
     root.children = children; 
     return true; 
    } 
    else 
    { 
     for (int i = 0; i < root.children.Length; i++) 
     { 
      /* if it returns true then it was last level 
        else break */ 
      if(!addChildren(root.children[i], children)) 
      { 
       /* this is non-last level break */ 
       break; 
      } 
     } 
    } 
    return false; 
} 

Answer 2

你或許應該讓你的內部node[]成list<node>而不是數組。

然後使用此代碼

 public void addChildren(Node root, Node[] children) 
     { 

      if (root.children == null) 
      { 
       root.children = new List<Node>(); 

      } 

      root.children.AddRange(children); 

     }