在n树实现中需要帮助
我正在尝试使用c#实现n-ary类型的数据结构。该树将具有一个根节点和一组子节点,并且子节点数组中的每个子节点也将具有一组子节点。我试图做的是每当我们添加应该添加到叶节点中存在的所有子节点的子节点数组。我的代码是在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);
}
但是这个代码的结果。我试过但无法弄清楚发生了什么问题?请帮我找出我做错了什么。 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);
}
}
}
谢谢:)
没有创建树正如您在图中所示,而你正在做一些象下面这样:
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;
}
你或许应该让你的内部node[]
成list<node>
而不是数组。
然后使用此代码
public void addChildren(Node root, Node[] children)
{
if (root.children == null)
{
root.children = new List<Node>();
}
root.children.AddRange(children);
}
感谢您的回复。如果我使用您的代码,我得到的树有一个有四个孩子的根。但我需要一棵有两个孩子的根,每个孩子又有两个孩子。在上面的场景中,我想要root - > m1:y,m1:n和m1:y - > m2:y,m2:n,m1:n - > m2:y,m2:n等等 – udi 2013-02-23 08:31:24
道歉, t当我发布我的答案时添加了主程序 – Dreamwalker 2013-02-23 09:37:46
对不起,我的错误 – udi 2013-02-27 05:26:30
非常感谢。问题已经解决了。 – udi 2013-02-23 09:12:15