Найдите максимальную глубину дерева
У меня есть древовидная структура данных с дочерними узлами первого уровня N, которые имеют childs также.
Например:
- Корень
- Node1
- Node11
- Node111
- Node1111
- Node12
- Node2
- Node21
- Node211
Я хотел бы знать, какое из ответвлений имеет самую большую глубину. Как в предыдущем примере это будет
Node1 - Node11 - Node111 - Node1111
это имеет глубину четырех уровней.
Какое-либо предложение?
Спасибо!
5 ответов
Вы должны проверить все узлы. Несколько месяцев назад я реализовал этот алгоритм следующим образом:
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.
Если у вас есть какой-либо итератор для вашего дерева, вы можете использовать совершенно повседневный подход к максимальной глубине.
Вот глупый однострочник, показывающий концепцию поиска максимальной глубины достижимой файловой системы с использованием 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 только в разделители /. Оттуда я просто нахожу самую длинную строку ввода ... и это мой результат.
Конечно, этот подход победил » Они не очень помогают с домашним заданием. Но концепция должна быть ясной. :)