Нужна помощь в реализации n дерева

Question

Я пытаюсь реализовать n-ary структуру данных с использованием C#. Дерево будет иметь корневой узел и массив дочерних элементов, и каждый дочерний элемент в массиве children также будет иметь набор дочерних узлов. То, что я пытаюсь сделать, - это когда мы добавляем дочерний массив, который должен быть добавлен ко всему дочернему элементу, присутствующему в листовом узле. мой код

 public void addChildren(Node root, Node[] children) 
     { 

      if (root.children == null) 
      { 
       root.children = children; 

      } 
      else 
      { 
       for (int i = 0; i < root.children.Length; i++) 
       { 

        addChildren(root.children[i], children); 
       } 
      } 

     } 

Основная программа результаты

 Dictionary<String, String[]> measurelist = new Dictionary<string, string[]>(); 
     String[] values = { "y", "n" }; 
     measurelist.Add("m1", values); 
     measurelist.Add("m2", values); 
     measurelist.Add("m3", values);   
     foreach (KeyValuePair<String, String[]> entry in measurelist) 
     { 
      Node[] children = new Node[entry.Value.Length]; 
      for(int i = 0; i < entry.Value.Length ;i ++) 
      { 
       Node child = new Node(entry.Key+":"+entry.Value[i]); 
       children[i] = child; 
      } 

      clustertree.addChildren(clustertree.root, children);    
     } 

, но этот код в бесконечных рекурсивных вызовов. Я пытался, но не мог понять, что происходит не так? Пожалуйста, помогите мне узнать, что я делаю неправильно. I have described the problem in the image

Решение: С помощью вас я нашел решение этой проблемы. Если я объясню основную причину, я думаю, что это будет полезно для других, которые могут столкнуться с одной и той же проблемой. Основная причина проблемы, когда я передаю массив дочерних узлов, передается как ссылка не по значениям. Я немного изменил свой код, чтобы удостовериться, что ссылка на один и тот же дочерний массив не передается на следующий вызов рекурсии.

Вот мой исправленный код:

public void addChildren(Node root, Node[] children) 
     { 

      if (root.children == null) 
      { 

       root.children = children; 

      } 
      else 
      { 
       for (int i = 0; i < root.children.Length; i++) 
       {      
        Node[] children1 = new Node[children.Length]; 
      //I am creating a new array and nodes and passing the newly created array to          the next recursive call 
        for (int j = 0; j < children.Length; j++) 
        { 
         Node node = new Node(children[j].key);       
         node.children = children[j].children; 
         children1[j] = node; 
        } 
        addChildren(root.children[i], children1); 
       } 
      } 

     } 

Еще раз спасибо :)

Answer 1

Вы не создаете дерево, как вы показали на диаграмме, а вы делаете что-то, как показано ниже:

 R 
    /\ 
    / \ 
    a1 a2 (children of this are actually b1 and b2) 
/\ 
/ \ 
b1 b2 

При добавлении b1, b2 как дети от a2 вы ссылаетесь на то же самое b1 and b2, которые были добавлены к a1.

В следующей итерации при добавлении c1 and c2, согласно вашему алгоритму вы ссылаетесь c1 and c2 к обоим b1 and b2 во-первых, с помощью a1, но ваша функция не останавливается, она идет снова b1 and b2 на этот раз с помощью a2, но так как c1 and c2 уже добавлены как дети b1 and b2, алгоритм запутывается и переходит в непрерывный цикл.

Чтобы решить эту проблему:

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

public boolean addChildren(Node root, Node[] children) 
{ 

    if (root.children == null) 
    { 
     root.children = children; 
     return true; 
    } 
    else 
    { 
     for (int i = 0; i < root.children.Length; i++) 
     { 
      /* if it returns true then it was last level 
        else break */ 
      if(!addChildren(root.children[i], children)) 
      { 
       /* this is non-last level break */ 
       break; 
      } 
     } 
    } 
    return false; 
} 

Answer 2

Вы должны, вероятно, сделать ваш внутренний node[] в list<node> вместо массива.

Затем используйте этот код

 public void addChildren(Node root, Node[] children) 
     { 

      if (root.children == null) 
      { 
       root.children = new List<Node>(); 

      } 

      root.children.AddRange(children); 

     }