Дано упорядоченное дерево глубины N (N > 0 — четное) - C#

Узнай цену своей работы

Формулировка задачи:

Здравствуйте, нужна помощь с задачкой по программированию. Дано упорядоченное дерево глубины N (N > 0 — четное), каждая внутренняя вершина которого имеет два непосредственных потомка: A с весом 1 и B с весом –1. Корень дерева C имеет вес 0. Записать в текстовый файл все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов для любого начального отрезка пути неотрицателен1|неположителен2. Каждый путь записывается в отдельной строке файла. Перебирать пути, начиная с "самого левого" и заканчивая "самым правым", при этом первыми заменять конечные элементы пути.

Решение задачи: «Дано упорядоченное дерево глубины N (N > 0 — четное)»

textual
Листинг программы
private static void Main()
{
    var paths = new List<Path>();
    SetPaths(paths, 4, new Path(), 0);
 
    foreach (Path path in paths)
    {
        Console.WriteLine($"Path {path} with weight {path.Weight}");
    }
}
 
private static void SetPaths(ICollection<Path> paths, int n, Path path, int level)
{
    level++;
    if (level == n)
    {
        if (path.Length > 0)
        {
            paths.Add(path);
        }
    }
    else if (level < n)
    {
        SetPaths(paths, n, Path.Add(path, NodeType.Left, 1), level);
        SetPaths(paths, n, Path.Add(path, NodeType.Right, -1), level);
    }
}
 
public class Path
{
    public List<NodeType> Nodes { get; set; } = new List<NodeType>();
    public int Weight { get; set; }
    public int Length => Nodes.Count;
 
    public static Path Add(Path path, NodeType type, int weight)
    {
        return new Path
        {
            Nodes = new List<NodeType>(path.Nodes) { type },
            Weight = path.Weight + weight
        };
    }
 
    public override string ToString()
    {
        return string.Join(", ", Nodes);
    }
}
 
public enum NodeType
{
    Left,
    Right
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 3.929 из 5
Похожие ответы