Baum-Datenstruktur in C#

1. Baumdatenstruktur in C#
2. Schritte zum Erstellen einer Baumdatenstruktur in C#

Bäume in C# werden das Diskussionsthema in diesem Artikel sein. Die Datenstruktur ist das erste, was wir wissen müssen.

Sie können Ihre Daten auf dem Computer mit einer Datenstruktur effizienter anordnen und speichern. Stapel, verkettete Listen und Warteschlangen sind alles Beispiele für sequentielle Datenstrukturen.

Baumdatenstruktur in C#

Eine Art hierarchischer Daten, die in Form eines Baums organisiert sind, wird als Baumdatenstruktur bezeichnet. Es besteht aus einem zentralen Knoten, strukturellen Knoten und Unterknoten, die durch Kanten miteinander verbunden sind.

Es ist auch möglich anzugeben, dass die Wurzeln, Zweige und Blätter der Baumdatenstruktur verknüpft sind.

Ein Baum könnte verwendet werden, um Daten in einer hierarchischen Struktur darzustellen. Jeder Knoten, aus dem ein Baum besteht, besteht aus zwei Unterteilen: Daten und Referenzen.

Der Knoten ganz oben im Baum wird als Wurzel bezeichnet. Die beiden Produkte direkt darunter werden als linker Teilbaum und rechter Teilbaum bezeichnet.

Der Code zum Schreiben eines Baumknotens könnte so aussehen:

struct node {
  int Data;
  struct node
  *Leftchild;
  struct node
  *Rightchild;
};

Grundlegende Terminologien in der Baumdatenstruktur in C#

Nachfolgend finden Sie die grundlegenden Terminologien, die Sie in der Baumdatenstruktur in C# kennen müssen:

• Wurzelknoten: Der Knoten an der Spitze des Baums wird als Wurzel bezeichnet. Jeder Baum hat eine einzige Wurzel, und eine einzige Route führt von der Wurzel zu jedem anderen Knoten.
• Level-Knoten: Die Ebenen der Knoten spiegeln die Anzahl der generierten Knoten wider. Knoten steigen in Ebenenschritten von 1, 2 usw. ab, wobei der Wurzelknoten immer oben liegt.
• Teilbaumknoten: Die Nachkommen eines Knotens werden durch den Teilbaum repräsentiert.
• Elternknoten: Wenn ein anderer Knoten als der Wurzelknoten mit einem Elternknoten verbunden ist, wird er als Elternknoten bezeichnet.
• Kind-Knoten: Wenn die Kante eines Knotens abfällt, wird er als sein Child-Knoten bezeichnet.

Vorteile der Baumdatenstruktur in C#

Hier sind zwei Vorteile der Verwendung der Baumdatenstruktur in C#:

1. Es ist unnötig, die Größe eines Baums anzugeben, wenn man ihn mit anderen Datenstrukturen wie Arrays oder verketteten Listen vergleicht. Dadurch ist der Baum effizient in Bezug auf seinen Lagerraum.
2. Im Gegensatz dazu eliminiert das Arbeiten mit Bäumen arbeitsintensive Operationen wie das Einfügen, Entfernen und Suchen von Knoten, die für verknüpfte Listen erforderlich sind.

Schritte zum Erstellen einer Baumdatenstruktur in C#

Wir haben hier ein Beispiel für eine Baumdatenstruktur in C#. Lesen Sie die folgenden Schritte, um mitzumachen.

1. Zu Beginn benötigen wir die folgenden Bibliotheken:

   using System;
   using System.Collections.Generic;
   using System.Linq;
   using System.Text;
   using System.Threading.Tasks;
   

2. Erstellen Sie eine Klasse namens node in der Shanii-Klasse, die die int-Typ-Variablen key, leftn als linken Knoten und rightn als rechten Knoten speichert.

   class node {
     public int key;
     public node leftn, rightn;
   };
   

3. Erstellen Sie dann aus dem Objekt eines Knotens einen Wurzelknoten und eine Liste von Knoten mit dem Namen z.

   static node rootnode = null;
   static List<node> z = new List<node>();
   

4. Um einen Knoten mit den Daten zu generieren, müssen wir eine Funktion namens newnode schreiben, die dies tut. Anfänglich sind beide Kinder dieses neuen Knotens null.

   static node newnode(int val) {
     node y = new node();
     y.key = val;
     y.leftn = null;
     y.rightn = null;
     return y;
   }
   

5. Jetzt sehen wir, ob der Knoten erreichbar ist, indem wir die if-Prüfung verwenden. Wenn ja, dann wird das linke Kind des aktuellen Knotens verwendet.

   if (rootnode == null) {
     rootnode = node;
   }
   

6. Falls verfügbar, wird das aktuelle Kind des Knotens verwendet. Da das linke Kind dieses Knotens bereits verwendet wurde, wird das rechte Kind verwendet.

   else if (z[0].leftn == null) {
     z[0].leftn = node;
   }
   

7. Die Adresse eines neu hinzugefügten Knotens im Baum wird der Warteschlange hinzugefügt. Daher kann er verwendet werden, um Informationen über die Knoten seiner Kinder zu speichern.

   else {
     z[0].rightn = node;
     z.RemoveAt(0);
   }
   z.Add(node);
   

8. Die folgende Klasse wird verwendet, um einen Baum zu konstruieren.

   static void Constructtree(int[] ar, int a) {
     for (int i = 0; i < a; i++) InsrtVal(ar[i]);
   }
   

9. Die folgende Funktion organisiert die Knoten nach ihrer Ebene.

   static void OrderData(node root) {}
   

10. Schließlich rufen wir die Funktionen auf, die zum Erstellen und Organisieren eines Baums und seiner Parameter erforderlich sind.

    static void Main() {
      int[] array = { 29, 39, 49, 59, 69, 79 };
      int n = array.Length;
      Constructtree(array, n);
      OrderData(rootnode);
      Console.ReadKey();
    }
    

Vollständiger Quellcode:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace tree_example {
  class Shanii {
    class node {
      public int key;
      public node leftn, rightn;
    };
    static node rootnode = null;
    static List<node> z = new List<node>();

    static node newnode(int val) {
      node y = new node();
      y.key = val;
      y.leftn = null;
      y.rightn = null;
      return y;
    }

    static void InsrtVal(int newval) {
      node node = newnode(newval);
      if (rootnode == null) {
        rootnode = node;
      }

      else if (z[0].leftn == null) {
        z[0].leftn = node;
      }

      else {
        z[0].rightn = node;
        z.RemoveAt(0);
      }
      z.Add(node);
    }

    static void Constructtree(int[] ar, int a) {
      for (int i = 0; i < a; i++) InsrtVal(ar[i]);
    }

    static void OrderData(node root) {
      if (root == null)
        return;
      List<node> n = new List<node>();
      n.Add(root);
      while (n.Count > 0) {
        Console.Write(n[0].key + " ");
        if (n[0].leftn != null)
          n.Add(n[0].leftn);
        if (n[0].rightn != null)
          n.Add(n[0].rightn);
        n.RemoveAt(0);
      }
    }

    static void Main() {
      int[] array = { 29, 39, 49, 59, 69, 79 };
      int n = array.Length;
      Constructtree(array, n);
      OrderData(rootnode);
      Console.ReadKey();
    }
  }
}

Ausgabe:

29 39 49 59 69 79