3

我正在尝试使用 c# 实现 n 元类型的数据结构。树将有一个根节点和子数组，并且子数组中的每个子节点也将具有一组子节点。我想要做的是每当我们添加子数组时，应该将其添加到叶节点中存在的所有子节点中。我的代码是

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

但是这段代码会导致无限递归调用。我试过但无法弄清楚出了什么问题？请帮助我找出我做错了什么。 我已经描述了图像中的问题

解决方案： 在您的帮助下，我找到了解决此问题的方法。如果我解释根本原因，我认为这将对可能面临同样问题的其他人有所帮助。当我传递子节点数组时，问题的主要原因是作为引用而不是值传递。我已经稍微更改了我的代码，以确保相同的子数组引用不会传递给下一个递归调用。

这是我更正的代码：

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

        }

再次感谢 ：）

4

2 回答 2

2

您可能应该将您的内部node[]变成 alist<node>而不是数组。

然后使用此代码

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

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

            }

            root.children.AddRange(children);

        }
于 2013-02-23T08:13:01.523 回答
1

您没有像图中所示那样创建树，而是在执行如下操作：

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

当您添加b1, b2作为您的子项时，a2您将引用b1 and b2已添加到a1.

在下一次迭代中，当您添加时c1 and c2，根据您的算法，您首先引用c1 and c2两个b1 and b2via，a1但您的函数不会在这里停止，它会再次进入b1 and b2这次 via a2，但由于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;
}
于 2013-02-23T08:43:40.593 回答