我有一个带有 N 个一级子节点的树数据结构,这些子节点也有子节点。
例如:
- 根
- 节点1
- 节点11
- 节点111
- 节点1111
- 节点12
- 节点2
- 节点21
- 节点211
我想知道哪个分支的深度最大。与前面的示例一样,它将是
节点 1 - 节点 11 - 节点 111 - 节点 1111
有四个层次的深度。
有什么建议吗?
谢谢!
您必须检查所有节点。几个月前,我以这种方式实现了这个算法:
class Node
{
public String Name { get; private set; }
public IList<Node> Childs { get; private set; }
public Node(String name)
{
Name = name;
Childs = new List<Node>();
}
public List<Node> Depth
{
get
{
List<Node> path = new List<Node>();
foreach (Node node in Childs)
{
List<Node> tmp = node.Depth;
if (tmp.Count > path.Count)
path = tmp;
}
path.Insert(0, this);
return path;
}
}
public override string ToString()
{
return Name;
}
}
示例测试:
Node node1111 = new Node("Node1111");
Node node111 = new Node("Node111");
Node node11 = new Node("Node11");
Node node12 = new Node("Node12");
Node node1 = new Node("Node1");
Node root = new Node("Root");
Node node2 = new Node("Node2");
Node node21 = new Node("Node21");
Node node211 = new Node("Node211");
root.Childs.Add(node1);
root.Childs.Add(node2);
node1.Childs.Add(node11);
node1.Childs.Add(node12);
node11.Childs.Add(node111);
node111.Childs.Add(node1111);
node2.Childs.Add(node21);
node21.Childs.Add(node211);
List<Node> path = root.Depth;
foreach (Node n in path)
Console.Write(String.Format("{0} - ", n.ToString()));
Console.WriteLine();
Node node2111 = new Node("Node2111");
node2111.Childs.Add(new Node("Node21111"));
node211.Childs.Add(node2111);
path = root.Depth;
foreach (Node n in path)
Console.Write(String.Format("{0} - ", n.ToString()));
Console.WriteLine();
控制台输出:
Root - Node1 - Node11 - Node111 - Node1111 -
Root - Node2 - Node21 - Node211 - Node2111 - Node21111 -
最直接的是一种蛮力算法,它枚举每条路径,保存指向所有节点的指针,并测量深度。对于比前一条路径长的每条路径,忘记所有其他路径,只记住最长的路径。
The deepest branch from a node is:
the longest of the respective deepest branches from each child node
prepended with the current node.
遍历树深度优先或广度优先,为每个节点分配其深度。记住深度最高的节点。
将 recusrivle 从该节点导航回根。这为您提供了 lngest 分支。可能有多个具有相同长度的分支。
如果你在你的树上有任何形式的迭代器,那么你可以使用一种非常普通的方法来达到最大深度。
这是一个愚蠢的单行代码,显示了使用 UNIX 查找最大可达文件系统深度的概念find
,awk
并且tr
:
find / -depth | tr -dc '/\n' \
| awk '{if (length($0) > max) { max=length($0)}}; END {print max}'
...find
是迭代器,tr
是一种数据操作,将一组字符“转换”为另一组字符(在这种情况下,它用于 -d(删除)指定的单个字符集 (/) 的补码 (-c)。所以它将任何 UNIX 完整路径转换为 / 分隔符。从那里我只找到最长的输入行......这就是我的结果。
当然,这种方法对你的家庭作业没有多大帮助。但是这个概念应该很清楚。:)