找到一棵树的最大深度

本文介绍了找到一棵树的最大深度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有一个树数据结构，其中也有N个第一级子节点.

I have a tree data structure with N first-level child nodes that have childs too.

例如:

• 根
• Node1
• Node11
• Node111
• Node1111
• Node21
• Node211

我想知道哪个分支的深度最大.与前面的示例一样，它将是

I would like to know which of the braches has the biggest depth. As in the previous example it will be

节点1-节点11-节点111-节点1111 Node1 - Node11 - Node111 - Node1111

具有四个层次的深度.

有什么建议吗?

谢谢！

推荐答案

您必须检查所有节点.几个月前，我以这种方式实现了该算法:

You must check all nodes. Several months ago I implemented this algorithm in this way:

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 -