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

     }