Определить номер уровня в котором содержится максимальное количество вершин - C#
Формулировка задачи:
В бинарном поисковом дереве необходимо проделать данную операцию.
Сделал обход по ширине. Как быть дальше не знаю
public IEnumerable<int> TraverseLevelOrder()
{
if (root == null)
yield break;
var queue = new Queue<Item>();
queue.Enqueue(root);
while (queue.Count > 0) {
var node = queue.Dequeue();
yield return node.info;
if (node.lSon != null) queue.Enqueue(node.lSon);
if (node.rSon != null) queue.Enqueue(node.rSon);
}
}Решение задачи: «Определить номер уровня в котором содержится максимальное количество вершин»
textual
Листинг программы
public int GetWidth()
{
return GetWidth(root);
}
protected int GetWidth(Item root)
{
int level=2, cur = 1, max = 0;
while(cur > 0)
{
cur = GetWidth(root, level++);
max = Math.Max(cur, max);
}
return max;
}
private int GetWidth(Item root, int level)
{
if (root == null) return 0;
if (level == 1) return 1;
return GetWidth(root.lSon, level-1) + GetWidth(root.rSon, level-1) ;
}