1

на входе дается список к примеру:

List<string> path = new List<string>() { "первый", "второй"});

Элементы этого списка это вложенные в друг друга ноды. Например в данном случае значит надо в ноде root создать ноду первый в которой создать ноду второй. я написал код, но при использовании рекурсивного метода добавлении ноды каждый раз внутрь другой ноды, почему то в главной ноде root изменений не происходит. Вот код с данной проблемой и с примером. Подскажите как его поправить.

class Program
{
    private static Node rootNode;
    static void Main(string[] args)
    {
        rootNode = new Node("root");
        List<string> path;
        
        AddNode(rootNode, path = new List<string>() { "первый", "второй"});
        AddNode(rootNode, path = new List<string>() { "второй" });
        AddNode(rootNode, path = new List<string>() { "первый","1" });
        AddNode(rootNode, path = new List<string>() { "третий","1" });
        AddNode(rootNode, path = new List<string>() { "четвертый","1" });
        AddNode(rootNode, path = new List<string>() { "первый" });
        AddNode(rootNode, path = new List<string>() { "первый" });
    }

    static void AddNode(Node node, List<string> path)
    {
        Node childNode;

        if (node.ChildList.Count == 0)
        {
            node.ChildList.Add( new Node(path[0]));
            if (path.Count > 1)
            {
                List<string> path1 = path.GetRange(1, path.Count-1);
                AddNode(new Node(path[0]), path1);
            }
        }
        else
        {
            bool True = false;
            for (int i = 0; i < node.ChildList.Count; i++)
                if (node.ChildList[i].Name == path[0])
                {
                    True = true;
                    if (path.Count > 1)
                    {
                        List<string> path1 = path.GetRange(1, path.Count-1);
                        AddNode(new Node(path[0]), path1);
                    }
                }

            if (!True)
            {
                node.ChildList.Add(childNode = new Node(path[0]));
                if (path.Count > 1)
                {
                    List<string> path1 = path.GetRange(1, path.Count-1);
                    AddNode(new Node(path[0]), path1);
                }
            }
        }
    }

    static Node searchNode(int number)
    {
        return null;
    }
}

class Node
{
    private static int number = 0;
    public Node(string name)
    {
        Number = number;
        Name = name;
        ChildList = new List<Node>();
        number++;
    }
    public int Number { get; set; }
    public string Name { get; set; }
    public List<Node> ChildList { get; set; }
}
4
  • «... почему то в главной ноде root изменений не происходит. ...» Думаю, что стоит написать каким образом Вы это проверяете. Тогда участники смогут сами проггнать код и проверить результаты. 30 июл 2020 в 11:42
  • @defaultlocale его можно просто запустить и увидим результат
    – polsok
    30 июл 2020 в 12:07
  • Запустить-то можно, только он ничего не выводит. Вы в режиме отладки следите за rootNode? 30 июл 2020 в 12:22
  • @defaultlocale да конечно в режиме отладки ставлю остановку на закрывающую скобку метода main
    – polsok
    30 июл 2020 в 13:00

1 ответ 1

2

Вот эта строчка:

 AddNode(new Node(path[0]), path1);

Создает совершенно новый объект Node, который ни в какое дерево не входит, затем пытается добавить к нему path1. Естественно, связи с корневым элементом у нового нет.

Вместо этого, нужно передавать в метод уже созданные объекты Node. Либо вновь созданный узел дерева, либо найденный при поиске.

Небольшие замечания по стилю:

  • Проверка на отсутствие дочерних элементов (if (node.ChildList.Count == 0)) лишняя. Если дочерних узлов нет, то они просто не найдутся при поиске. Всю эту ветку можно убрать.
  • Никогда не называйте буллевую переменную True, это только сбивает с толку. Дайте ей осмысленное название, например, isNodeFound.

Попробуем внести изменения в код (предупреждаю, я его не тестировал):

Node childNode;
bool isNodeFound = false;
for (int i = 0; i < node.ChildList.Count; i++)
    if (node.ChildList[i].Name == path[0])
    {
        isNodeFound = true;
        if (path.Count > 1)
        {
             //получаем найденный узел
             childNode = node.ChildList[i];
             List<string> path1 = path.GetRange(1, path.Count-1);
             //передаем его в метод
             AddNode(childNode, path1);
        }
        //узел уже нашли, выходим из цикла
        break;
    }
if (!isNodeFound)
{
    childNode = new Node(path[0]);
    node.ChildList.Add(childNode);
    if (path.Count > 1)
    {
        List<string> path1 = path.GetRange(1, path.Count-1);
        //передаем сюда childNode
        AddNode(childNode, path1);
    }
}

Если дальше потребуется оптимизировать этот метод, то предложил бы:

  • Реализовать его без рекурсии, обычным циклом. Так можно будет избежать всех манипуляций с «вырезанием» первого элемента.
  • Вместо списка дочерних узлов хранить словарь (Dictionary<string,Node>). Так будет легче найти узел по имени. Учтите, что при этом потеряется порядок узлов. Если важно, чтобы узлы шли по порядку, то можно вести как список, так и словарь.

Получилось бы что-то вроде:

for(var name : path) 
{
    node.Children.TryGetValue(name, out var childNode);
    if(childNode==null) 
    { 
         childNode = new Node(name);
         node.Children[name] = childNode;
    }
    node = childNode;
}
1
  • 1
    Все отлично работает.
    – polsok
    30 июл 2020 в 13:15

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.