algorithm
Drzewa

Uwagi

Wprowadzenie

Drzewa są podtypem bardziej ogólnej struktury danych grafowych na krawędziach węzłów.

Aby być drzewem, wykres musi spełniać dwa wymagania:

• To jest acykliczne. Nie zawiera cykli (ani „pętli”).
• Jest podłączony. Każdy węzeł na wykresie jest dostępny dla każdego węzła. Wszystkie węzły są osiągalne jedną ścieżką na wykresie.

Struktura danych drzewa jest dość powszechna w informatyce. Drzewa są używane do modelowania wielu różnych struktur danych algorytmicznych, takich jak zwykłe drzewa binarne, drzewa czerwono-czarne, drzewa B, drzewa AB, drzewa 23, sterty i próby.

Powszechnie nazywa się Drzewo Drzewem Rooted Tree przez:

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)

wspólny symbol drzew: T

Typowa reprezentacja drzewa anarynowego

Zazwyczaj reprezentujemy drzewo anaryjne (jedno z potencjalnie nieograniczoną liczbą potomków na węzeł) jako drzewo binarne (jedno z dokładnie dwoma potomkami na węzeł). „Następne” dziecko jest uważane za rodzeństwo. Zauważ, że jeśli drzewo jest binarne, reprezentacja ta tworzy dodatkowe węzły.

Następnie iterujemy po rodzeństwie i wracamy do dzieci. Ponieważ większość drzew jest stosunkowo płytka - wiele dzieci, ale tylko kilka poziomów hierarchii, daje to początek wydajnemu kodowi. Uwaga: genealogie ludzkie są wyjątkiem (wiele poziomów przodków, tylko kilka dzieci na poziom).

W razie potrzeby można zachować wskaźniki cofania, aby umożliwić wstąpienie do drzewa. Są trudniejsze do utrzymania.

Zauważ, że typowe jest posiadanie jednej funkcji do wywoływania w katalogu głównym i funkcji rekurencyjnej z dodatkowymi parametrami, w tym przypadku głębokością drzewa.

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

Aby sprawdzić, czy dwa drzewa binarne są takie same, czy nie

1. Na przykład, jeśli dane wejściowe to:

Przykład 1

za)

b)

Dane wyjściowe powinny być prawdziwe.

Przykład: 2

Jeśli dane wejściowe to:

za)

b)

Dane wyjściowe powinny być fałszywe.

Pseudo kod dla tego samego:

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;

}