algorithm
Bäume

Bemerkungen

Einführung

Bäume sind ein Untertyp der allgemeineren Knotenstrukturdatenstruktur.

Um ein Baum zu sein, muss ein Diagramm zwei Anforderungen erfüllen:

• Es ist azyklisch. Es enthält keine Zyklen (oder "Schleifen").
• Es ist verbunden. Für jeden Knoten in der Grafik ist jeder Knoten erreichbar. Alle Knoten sind über einen Pfad in der Grafik erreichbar.

Die Baumdatenstruktur ist in der Informatik weit verbreitet. Bäume werden verwendet, um viele verschiedene algorithmische Datenstrukturen zu modellieren, z. B. gewöhnliche binäre Bäume, rotschwarze Bäume, B-Bäume, AB-Bäume, 23-Bäume, Heap und Versuche.

Es ist üblich, einen Baum als Rooted Tree indem

choosing 1 cell to be called `Root`
painting the `Root` at the top
creating lower layer for each cell in the graph depending on their distance from the root -the bigger the distance, the lower the cells (example above)

allgemeines Symbol für Bäume: T

Typische Darstellung eines Nebenbaums

Normalerweise stellen wir einen anary-Baum (einen mit potenziell unbegrenzten Kindern pro Knoten) als einen binären Baum dar (einen mit genau zwei Kindern pro Knoten). Das "nächste" Kind wird als Geschwister betrachtet. Wenn ein Baum binär ist, werden durch diese Darstellung zusätzliche Knoten erstellt.

Wir durchlaufen dann die Geschwister und rekursieren die Kinder. Da die meisten Bäume relativ flach sind - viele Kinder, aber nur wenige Hierarchieebenen, führt dies zu effizientem Code. Beachten Sie, dass die Genealogie des Menschen eine Ausnahme darstellt (viele Ahnenstufen, nur wenige Kinder pro Stufe).

Wenn nötig, können Rückwärtszeiger aufbewahrt werden, damit der Baum aufsteigen kann. Diese sind schwieriger zu warten.

Beachten Sie, dass es normalerweise typisch ist, eine Funktion für den Stamm aufzurufen und eine rekursive Funktion mit zusätzlichen Parametern, in diesem Fall die Baumtiefe.

  struct node
  {
     struct node *next;
     struct node *child;
     std::string data;
  }

  void printtree_r(struct node *node, int depth)
  {
     int i;

     while(node)
     {
         if(node->child)
         {
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
            printtree_r(node->child, depth +1);
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
    
            for(i=0;i<depth*3;i++)
               printf(" ");
             printf("%s\n", node->data.c_str());

             node = node->next;
          }
      }
  }

  void printtree(node *root)
  {
     printree_r(root, 0);
  }

Um zu überprüfen, ob zwei binäre Bäume gleich sind oder nicht

1. Zum Beispiel, wenn die Eingaben sind:

Beispiel 1

ein)

b)

Ausgabe sollte wahr sein.

Beispiel: 2

Wenn die Eingaben sind:

ein)

b)

Die Ausgabe sollte falsch sein.

Pseudo-Code für dasselbe:

boolean sameTree(node root1, node root2){

if(root1 == NULL && root2 == NULL)
return true;

if(root1 == NULL || root2 == NULL)
return false;

if(root1->data == root2->data 
     && sameTree(root1->left,root2->left)
        && sameTree(root1->right, root2->right))
return true;

}