Как реализовать не двоичное дерево

Question

У меня возникла проблема с реализацией небинодного дерева, где корневой узел может иметь произвольное количество дочерних узлов. В принципе, мне бы хотелось, чтобы некоторые идеи о том, как с этим идти, поскольку у меня есть код написанный, но я застрял в этом вопросе, что делать дальше. BTW Я не могу использовать ни один из классов Collections вообще. Я могу использовать только System.

using System; 

namespace alternate_solution 
{ 
//   [root] 
//  //  \ \ 
// text text text text 

class Node//not of type TreeNode (since Node is different from TreeNode) 
{ 
    public string data; 
    public Node child; 

    public Node(string data) 
    { 
     this.data = data; 
     this.child = null; 
    } 

} 

}

Answer 1

До сих пор решение Jerska является лучшим, но оно излишне сложно. .

Поскольку я предполагаю, это домашнее задание упражнения позвольте мне дать вам направление, вы должны возглавить в структуре данных вы хотите:

class TreeNode 
{ 
    public string Data { get; private set; } 
    public TreeNode FirstChild { get; private set; } 
    public TreeNode NextSibling { get; private set; } 
    public TreeNode (string data, TreeNode firstChild, TreeNode nextSibling) 
    { 
    this.Data = data; 
    this.FirstChild = firstChild; 
    this.NextSibling = nextSibling; 
    } 
} 

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

Root 
| 
p1 ----- p2 ----- p4 ----- p6 
|  |   |  | 
c1  p3  c4  p7 
      |     | 
      c2 - c3   c5 

Имеют смысл?

Теперь, можете ли вы написать код, который создает это дерево, используя эту структуру данных? Start из правых листьев и работать ваш путь к корню:

TreeNode c5 = new TreeNode("c5", null, null); 
TreeNode p7 = new TreeNode("p7", c5, null); 
TreeNode p6 = new TreeNode("p6", p6, null); 
... you do the rest ... 

Обратите внимание, что любое дерево просто бинарное дерево «поворачивается на 45 градусов», где корень не имеет «правильный» ребенок.Двоичные деревья и произвольные деревья: То же самое:; вы просто назначаете разные значения двум детям.

Answer 2

class Node 
{ 
    public string data; 
    public Node parent; 
    public IEnumerable<Node> children; 

    public Node(string data, Node parent, IEnumerable<Node> children) 
    { 
     this.data = data; 
     this.parent = parent; 
     this.children = children; 
    } 

} 

Answer 3

Если вы не можете использовать какие-либо коллекции, хранить ссылку всех дочерних элементов для родителей. Вы можете смоделировать свой график с помощью следующей структуры данных:

class Node 
{ 
    public string Data { get; set; } 
    public Node Parent { get; set; } 

    public Node(string data, Node parent) 
    { 
     Data = data; 
     Parent = parent; 
    } 
} 

Теперь вы можете иметь столько Чайлдс для каждого узла, как вам нравится:

var root = new Node("root", null); 

var parent = new Node("parent", root); 
var anotherParent = new Node("yetAnotherParent", root); 

var child = new Node("Child", parent); 
var anotherchild = new Node("anotherchild", parent); 

Answer 4

Некоторые случайные идеи:

• Узел потребует какой-то список дочерних узлов, рассмотрите возможность использования параллельной проверки, скорее всего IEnumerable<NodeType> поместит счет
• Вы может или не может хотеть обратный указатель на родителя - conisder один для скорейшего (читай: не слишком неточным) Обход
• Я рекомендую вам создать NodeType<T>, чтобы сделать жизнь проще, когда потребление дерева

Answer 5

Так как вы можете» t использовать коллекцию, почему бы вам не создать свой собственный список?

class Child { 
    Node node; 
    Child next = null; 

    public Child (Node node) { 
     this.node = node; 
    } 

    public void addChild (Node node) { 
     if (this.next == null) 
      this.next = new Child (node); 
     else 
      this.next.addChild (node); 
    } 
} 

class Node { 
    public string data; 
    public Child children = null; 

    public Node (string data) { 
     this.data = data; 
    } 

    public void addChild (Node node) { 
     if (this.children == null) 
      this.children = new Child (node); 
     else 
      this.children.addChild (node); 
    } 
} 

И использовать его как это:

Node root = new Node ("Hey"); 
root.addChild (new Node ("you")); 
root.addChild (new Node ("me")); 

Теперь вы будете иметь:

  Node ("Hey") 
     /   \ 
    Node ("you")  Node ("me") 

Затем вам необходимо будет выполнять различные функции (геттеры, пластырь, и т.д.). Но это твоя работа.

Answer 6

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

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

Указатель узла child Указатель используется для указания первого дочернего узла.

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

Я также добавил пример перечислимого, чтобы показать, как вы могли бы перебирать узлы дерева. Вы, вероятно, захотите поиграть с этим, чтобы получить результаты в разных заказах. ЕСЛИ использование перечислимого слишком сложно для того, что вам нужно, вам нужно будет написать свой собственный простой метод, чтобы посетить все узлы.

Обратите внимание, что тип узла является общим в этом примере, и я использую его только для хранения строковых данных. Вы можете просто заменить T на нужный вам тип, если вы не хотите общий тип.

using System; 
using System.Collections; 
using System.Collections.Generic; 

namespace Demo 
{ 
    sealed class Node<T> 
    { 
     public T Data; // Payload. 

     public Node<T> Next; // This will point to the next sibling node (if any), forming a linked-list. 
     public Node<T> Child; // This will point to the first child node (if any). 
    } 

    sealed class Tree<T>: IEnumerable<T> 
    { 
     public Node<T> Root; 

     public Node<T> AddChild(Node<T> parent, T data) 
     { 
      parent.Child = new Node<T> 
      { 
       Data = data, 
       Next = parent.Child // Prepare to place the new node at the head of the linked-list of children. 
      }; 

      return parent.Child; 
     } 

     public IEnumerator<T> GetEnumerator() 
     { 
      return enumerate(Root).GetEnumerator(); 
     } 

     private IEnumerable<T> enumerate(Node<T> root) 
     { 
      for (var node = root; node != null; node = node.Next) 
      { 
       yield return node.Data; 

       foreach (var data in enumerate(node.Child)) 
        yield return data; 
      } 
     } 

     IEnumerator IEnumerable.GetEnumerator() 
     { 
      return GetEnumerator(); 
     } 
    } 

    class Program 
    { 
     void run() 
     { 
      var tree = new Tree<string>(); 

      tree.Root = new Node<string>{Data = "Root"}; 

      var l1n3 = tree.AddChild(tree.Root, "L1 N3"); 
      var l1n2 = tree.AddChild(tree.Root, "L1 N2"); 
      var l1n1 = tree.AddChild(tree.Root, "L1 N1"); 

      tree.AddChild(l1n1, "L2 N1 C3"); 
      tree.AddChild(l1n1, "L2 N1 C2"); 
      var l2n1 = tree.AddChild(l1n1, "L2 N1 C1"); 

      tree.AddChild(l1n2, "L2 N2 C3"); 
      tree.AddChild(l1n2, "L2 N2 C2"); 
      tree.AddChild(l1n2, "L2 N2 C1"); 

      tree.AddChild(l1n3, "L2 N3 C3"); 
      tree.AddChild(l1n3, "L2 N3 C2"); 
      tree.AddChild(l1n3, "L2 N3 C1"); 

      tree.AddChild(l2n1, "L3 N1 C3"); 
      tree.AddChild(l2n1, "L3 N1 C2"); 
      tree.AddChild(l2n1, "L3 N1 C1"); 

      tree.Print(); 
     } 

     static void Main() 
     { 
      new Program().run(); 
     } 
    } 

    static class DemoUtil 
    { 
     public static void Print(this object self) 
     { 
      Console.WriteLine(self); 
     } 

     public static void Print(this string self) 
     { 
      Console.WriteLine(self); 
     } 

     public static void Print<T>(this IEnumerable<T> self) 
     { 
      foreach (var item in self) 
       Console.WriteLine(item); 
     } 
    } 
} 

(я знаю, что это похоже на ответ Эрика выше, и если бы я прочитал, что ответ, прежде чем писать этот я, вероятно, не был бы потрудился, - но я уже написал это, и я не сделал хотите просто выбросить его.)