Обход сложной древовидной структуры

Question

У меня есть такая древовидная структура:

A (20,40)
    B (21,22)
    C (23,33)
        D (24,29)
            E (25,26)
            F (27,28)
        G (30,31)
        H (32,33)
    I (34,37)
        J(35,36)
    K (38,39)

Уровни могут быть сколь угодно глубокими, поэтому мне нужно использовать рекурсию.Как найти дочерние элементы данного узла и значения их уровней (например, «B» будет уровнем 2)?

Я довольно застрял в этой проблеме, но мой псевдокод до сих пор примерно такой:

Передать узел -> если разница между его левым значением и его правым значением> 1, найдите следующего потомка, используя левое значение + 1

Answer 1

Есть много способов сделать это! Взгляните на Дерево обхода для идей.

Из вашего примера видно, что у вас есть несколько диапазонов на каждом узле, которые вы должны использовать.

Просто для забавы я попытался (очень быстро) построить некоторый код - опять же, это делается без знания тех параметров, которые вы используете при поиске. Обратите внимание, что это только пример, построенный очень быстро:

Структура узла

class Node
{
    public int Min { get; set; }
    public int Max { get; set; }

    public List<Node> Children { get; set; }

    public Node(int min, int max)
    {
        this.Min = min;
        this.Max = max;
        this.Children = new List<Node>();
    }

    public void Add(Node child)
    {
        this.Children.Add(child);
    }
}

А основной класс

Класс содержит функцию для построения дерева (не симпатичную) и рекурсивную функцию, которая возвращает уровень и выдает объект узла.

class Program
{
    static void Main(string[] args)
    {
        var tree = GetTree();
        Node node;
        var val = Find(tree, 21, 1, out node);

        Console.WriteLine("depth: {0}", val);
        Console.WriteLine("\t{0}, {1}", node.Min, node.Max);
        Console.ReadKey();
    }

    private static int Find(Node curNode, int value, int level, out Node foundNode)
    {
        foundNode = curNode;
        foreach (var child in curNode.Children)
        {
            if (child.Min <= value && child.Max >= value)
                return Find(child, value, level + 1, out foundNode);
        }
        return level;
    }

    private static Node GetTree()
    {
        var a = new Node(20, 40);
        var b = new Node(21, 22);
        var c = new Node(23, 33);
        var d = new Node(24, 29);
        var e = new Node(25, 26);
        var f = new Node(27, 28);
        var g = new Node(30, 31);
        var h = new Node(32, 33);
        var i = new Node(34, 37);
        var j = new Node(35, 36);
        var k = new Node(38, 39);

        d.Add(e);
        d.Add(f);

        c.Add(d);
        c.Add(g);
        c.Add(h);

        i.Add(j);

        a.Add(b);
        a.Add(c);
        a.Add(i);
        a.Add(k);

        return a;
    }
}

private static Node GetTree()
{
    var a = new Node(20, 40);
    var b = new Node(21, 22);
    var c = new Node(23, 33);
    var d = new Node(24, 29);
    var e = new Node(25, 26);
    var f = new Node(27, 28);
    var g = new Node(30, 31);
    var h = new Node(32, 33);
    var i = new Node(34, 37);
    var j = new Node(35, 36);
    var k = new Node(38, 39);

    d.Add(e);
    d.Add(f);

    c.Add(d);
    c.Add(g);
    c.Add(h);

    i.Add(j);

    a.Add(b);
    a.Add(c);
    a.Add(i);
    a.Add(k);

    return a;
}

Answer 2

Вы всегда можете использовать регулярные выражения, верно? :)

Вы можете сделать глобальное совпадение для этого:

([    ]+)([A-Z]+) \(\d+,\d+\)

и посчитайте, сколько раз повторяются четыре пробела, что в основном является уровнем буквы.

Если вы хотите сохранить фактическое дерево, вы должны также вести учет родительского узла.