寻找树的最大深度

Question

我有一个树形数据结构，其中有N个一级子节点，它们也有子节点。

例如：

根 - 节点1 - 节点11 - 节点111 - 节点1111 - 节点12 - 节点2 - 节点21 - 节点211

我想知道哪个分支具有最大深度。在上面的示例中，它将是

Node1 - Node11 - Node111 - Node1111

它有四个级别的深度。

有什么建议吗？

谢谢！

- Vincenzo

---

@Moron：你说的作业是什么意思？ - Vincenzo

你知道什么是家庭作业吧？ - Aryabhatta

Answer 1

您必须检查所有节点。几个月前，我以以下方式实现了此算法：

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 -

- Michał Ziober

---

这几乎是我做的方式，但我不得不用C实现它。 - WarmWaffles

好的解决方案。两个建议。首先，“Depth”这个名称不恰当，它并没有返回深度。应该将其命名为“PathToDeepestLeaf”。其次，属性应该保留给(1)逻辑上是属性的东西，比如颜色或深度，而不是像“path to lowest leaf”这样复杂的计算内容；(2)计算速度非常快，与访问字段的速度相同的东西。我建议将它作为一个方法而不是一个属性。 - Eric Lippert

一个挑战：这棵树可能非常深。假设它有一千个节点，那么递归太多会导致堆栈溢出。你能否在不使用递归的情况下完成它？ - Eric Lippert

谢谢你的建议。我会尝试不使用递归来编写算法。但是，递归版本对我来说最容易。 - Michał Ziober

感谢您的回答和评论！ 除了Eric Lippert的评论，我几乎完全同意，您提出的解决方案是我的第一个想法。我使用递归编码，它运行得非常完美。 但是...它有点“未优化”！对此有什么建议吗？ - Vincenzo

Answer 2

The deepest branch from a node is:
    the longest of the respective deepest branches from each child node
    prepended with the current node.

- Svante

Answer 3

最直接的算法是蛮力算法，枚举每一条路径，保存所有节点的指针，并测量深度。对于比前一条路径更长的每一条路径，忘记所有其他路径，仅记住最长路径。

- wallyk

Answer 4

深度优先或广度优先遍历树，为每个节点分配其深度。记住具有最大深度的节点。

从该节点递归地向根导航回来。这给您最长的分支。可能会有多个长度相同的分支。

- Carsten

Answer 5

如果您的树上有任何形式的迭代器，那么您可以使用完全平凡的方法来确定最大深度。

下面是一个愚蠢的一行代码，展示了使用UNIX的find、awk和tr查找最大可达文件系统深度的概念：

find / -depth | tr -dc '/\n' \
    | awk '{if (length($0) > max) { max=length($0)}}; END {print max}'

... find 是迭代器，tr 是一种数据操作，将一组字符“翻译”成另一组字符（在这种情况下，它被用于删除指定的单个字符集（/）的补集（-c）。因此，它将任何UNIX完整路径转换为仅使用/分隔符。从那里开始，我只需找到最长的输入行......那就是我的结果。

当然，这种方法对于你的家庭作业任务帮助不大。但是概念应该很清楚。 :)

- Jim Dennis