找到一棵树的最大深度 [英] Find the maximum depth of a tree

问题描述

我有一个树数据结构，其中也有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 -

这篇关于找到一棵树的最大深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！