5

私は、子を持つN個の第1レベルの子ノードを持つツリーデータ構造を持っています。

例えば：

  • 根
    • ノード1
      • ノード11
        • ノード111
          • ノード1111
      • ノード12
    • ノード 2
      • ノード21
        • ノード211

どのブランチが最も深いのか知りたいです。前の例のように、

Node1 - Node11 - Node111 - Node1111

4 レベルの深さがあります。

なにか提案を？

ありがとう！

4

5 に答える 5

4

すべてのノードをチェックする必要があります。数か月前、このアルゴリズムを次のように実装しました。

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 -
于 2010-02-21T03:10:23.337 に答える
0

ツリーに何らかの形式のイテレータがある場合は、完全に平凡なアプローチを最大深度に使用できます。

findUNIXを使用awkして到達可能なファイルシステムの最大深度を見つけるための概念を示すばかげたワンライナーを次に示しますtr。

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

...findは反復子でtrあり、ある文字セットを別の文字セットに「変換」するデータ操作です (この場合、指定されている単一の文字セット (/) の補数 (-c) を -d (削除) するために使用されています)。したがって、UNIX のフル パスを / 区切り記号だけに変換し、そこから入力の最も長い行を見つけます ... これが私の結果です。

もちろん、このアプローチは宿題にはあまり役に立ちません。しかし、コンセプトは明確でなければなりません。:)

于 2010-02-21T03:45:55.900 に答える
0 
The deepest branch from a node is:
    the longest of the respective deepest branches from each child node
    prepended with the current node.
于 2010-02-21T02:23:19.373 に答える
0

深さ優先または幅優先でツリーをトラバースし、各ノードにその深さを割り当てます。最も深いノードを覚えておいてください。

そのノードからルートに再帰的に移動します。これにより、lngest ブランチが得られます。同じ長さの分岐が複数ある場合があります。

于 2010-02-21T02:26:18.433 に答える
0

最も単純なのは、すべてのパスを列挙し、すべてのノードへのポインターを保存し、深さを測定するブルート フォース アルゴリズムです。前のパスよりも長いパスごとに、他のすべてのパスを忘れて、最も長いパスのみを覚えておいてください。

于 2010-02-21T02:11:35.843 に答える