algorithm
träd

Anmärkningar

Introduktion

Träd är en undertyp av den mer allmänna nodkanten-grafstrukturen.

För att vara ett träd måste en graf uppfylla två krav:

• Det är acykliskt. Den innehåller inga cykler (eller "slingor").
• Den är ansluten. För varje given nod i grafen kan varje nod nås. Alla noder kan nås via en sökväg i diagrammet.

Trädatasstrukturen är ganska vanlig inom datavetenskap. Träd används för att modellera många olika algoritmiska datastrukturer, såsom vanliga binära träd, röd-svarta träd, B-träd, AB-träd, 23-träd, Heap och försök.

det är vanligt att hänvisa till ett träd som ett Rooted Tree av:

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)

gemensam symbol för träd: T

Typisk anary trädrepresentation

Vanligtvis representerar vi ett anärt träd (ett med potentiellt obegränsat barn per nod) som ett binärt träd (ett med exakt två barn per nod). Det "nästa" barnet betraktas som ett syskon. Observera att om ett träd är binärt, skapar denna representation extra noder.

Vi iterererar sedan över syskon och rekryterar barnen. Eftersom de flesta träd är relativt grunt - massor av barn men bara några få nivåer av hierarki ger detta upphov till effektiv kod. Observera att mänskliga släktforskningar är ett undantag (många nivåer av förfäder, endast ett fåtal barn per nivå).

Om nödvändigt kan ryggpekarna hållas för att låta trädet stiga. Dessa är svårare att underhålla.

Observera att det är typiskt att ha en funktion för att anropa roten och en rekursiv funktion med extra parametrar, i detta fall träddjup.

  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);
  }

För att kontrollera om två binära träd är samma eller inte

1. Till exempel om ingångarna är:

Exempel: 1

a)

b)

Output bör vara sant.

Exempel: 2

Om ingångarna är:

a)

b)

Output bör vara falsk.

Pseudokod för samma:

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;

}