我希望使用 c# 打印(以列出>树叶的每个路径(最好是递归的)
如果是树:
A
B C
D E F G H
I
我希望得到的结果是叶子列表(A 是叶子,ABDI 是叶子列表):
ABDI
ABE
ABF
ACG
ACH
我正在尝试像 foreach 这样的不同循环,但我不知道何时打印以获得整个路径。
我希望使用 c# 打印(以列出>树叶的每个路径(最好是递归的)
如果是树:
A
B C
D E F G H
I
我希望得到的结果是叶子列表(A 是叶子,ABDI 是叶子列表):
ABDI
ABE
ABF
ACG
ACH
我正在尝试像 foreach 这样的不同循环,但我不知道何时打印以获得整个路径。
您需要使用深度优先遍历。
解决方案是:
public class Node {
public List<Node> Children {get;set;}
public string Label {get;set;}
}
public static void Print(Node node, string result)
{
if (node.Children == null || node.Children.Count == 0)
{
Console.WriteLine(result);
return;
}
foreach(var child in node.Children)
{
Print(child, result + child.Label);
}
}
像这样称呼它:
Print(root, root.Label);
应该是这样的:(第一次调用 ListNodes(node, "");
private void ListNodes(TreeNode node, string root)
{
if (node.Nodes.Count > 0)
{
foreach (TreeNode n in node.Nodes)
{
ListNodes(n, root + node.Text);
}
}
else
{
Console.Write(" " + root + node.Text);
}
}
假设您有这样的结构:
class Node {
List<Node> Children {get;set;}
string Label {get;set;}
}
您可以使用递归方法打印路径,例如:
void PrintPaths (Node node, List<Node> currentPath)
{
currentPath = new List<Node>(currentPath);
currentPath.Add (node);
if (node.Children.Any()) {
foreach (var child in node.Children)
PrintPaths (child, currentPath);
} else {
//we are at a leaf, print
foreach (var n in currentPath)
Console.Write (n.Label);
Console.WriteLine ();
}
}
在根节点上调用:PrintPaths (rootnode, null);
如果您想要返回这些列表而不是打印,则将一个额外的参数 aList<List<Node>>
传递给方法,而不是在最后打印,而是将 currentpath 添加到结果中。
var result = new List<List<Node>> ();
GetPaths (rootNode, null, result); //implementation not provided, but trivial
使用堆栈的深度优先搜索,另一种干净的方式
push (root);
while (top ())
{
pop (top);
push (node->right);
push (node->left);
}
这可以递归地完成