algorithm
bomen

Opmerkingen

Invoering

Bomen zijn een subtype van de meer algemene gegevensstructuur van de knooppuntrandgrafiek.

Om een boom te zijn, moet een grafiek aan twee vereisten voldoen:

• Het is acyclisch. Het bevat geen cycli (of "lussen").
• Het is verbonden. Voor elk gegeven knooppunt in de grafiek is elk knooppunt bereikbaar. Alle knooppunten zijn bereikbaar via één pad in de grafiek.

De structuur van de boomgegevens is vrij gebruikelijk in de informatica. Bomen worden gebruikt om veel verschillende algoritmische gegevensstructuren te modelleren, zoals gewone binaire bomen, rood-zwarte bomen, B-bomen, AB-bomen, 23-bomen, Heap en probeert.

het is gebruikelijk om naar een boom te verwijzen als een Rooted Tree door:

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)

gemeenschappelijk symbool voor bomen: T

Typische anaire boomweergave

Doorgaans vertegenwoordigen we een anary tree (één met potentieel onbeperkte kinderen per knooppunt) als een binaire boom (één met precies twee kinderen per knooppunt). Het "volgende" kind wordt beschouwd als een broer of zus. Merk op dat als een boom binair is, deze weergave extra knooppunten creëert.

We herhalen dan de broers en zussen en verplichten de kinderen. Omdat de meeste bomen relatief ondiep zijn - veel kinderen maar slechts een paar niveaus van hiërarchie, geeft dit aanleiding tot efficiënte code. Merk op dat menselijke genealogieën een uitzondering zijn (veel niveaus van voorouders, slechts een paar kinderen per niveau).

Indien nodig kunnen rugwijzers worden bewaard om de boom te laten stijgen. Deze zijn moeilijker te onderhouden.

Merk op dat het typisch is om een functie te hebben om de root aan te roepen en een recursieve functie met extra parameters, in dit geval boomdiepte.

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

Om te controleren of twee binaire bomen hetzelfde zijn of niet

1. Bijvoorbeeld als de ingangen zijn:

Voorbeeld 1

een)

b)

De uitvoer moet waar zijn.

Voorbeeld 2

Als de ingangen zijn:

een)

b)

Uitvoer moet onwaar zijn.

Pseudo-code voor hetzelfde:

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;

}