在n树实现方面需要帮助

本文关键字：帮助 方面需 实现 | 更新日期: 2023-09-27 18:00:35

我正在尝试使用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);
                }
            }
        }

再次感谢：）

在n树实现方面需要帮助

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

然后使用此代码

      public void addChildren(Node root, Node[] children)
        {
            if (root.children == null)
            {
                root.children = new List<Node>();
            }
            root.children.AddRange(children);
        }

您并没有像图中所示那样创建树，而是在做以下操作：

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

当您将b1, b2添加为a2的子级时，您引用的是已添加到a1的相同b1 and b2。

在下一次迭代中，当你添加c1 and c2时，根据你的算法，你首先通过a1将c1 and c2引用到两个b1 and b2，但你的函数并没有到此为止，这次它通过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;
}
相关文章：