Implementare la struttura dati ad albero binario in C++

1. Implementare l’albero binario utilizzando la parola chiave struct in C++
2. Implementa funzioni per calcolare la dimensione e l’altezza della struttura ad albero e una funzione per stampare elementi in C++

Questo articolo spiegherà come implementare la struttura dati dell’albero binario in C++.

Implementare l’albero binario utilizzando la parola chiave struct in C++

Gli alberi sono strutture dati astratte utilizzate in vari algoritmi fondamentali. Sono generalmente strutture gerarchiche in cui è necessario un nodo radice e i suoi figli che formano sottoalberi. Inoltre, ci sono più tipi di struttura ad albero, ognuno adatto a particolari esigenze e che fornisce alcuni compromessi.

Un albero binario è una delle sottoclassi delle strutture dati ad albero ed è definito come un albero in cui ogni nodo deve avere al massimo due figli, inclusi i nodi figli designati come left e right. In questo caso, implementiamo un albero binario utilizzando la funzione struct poiché dichiara una classe in cui i membri sono pubblici per impostazione predefinita. Un nodo in un albero binario contiene due puntatori ai nodi sinistro/destro e ai dati necessari. Nota che abbiamo dichiarato un singolo membro int per rappresentare i dati memorizzati nel nodo solo a scopo di spiegazione.

Definiamo un costruttore che prende un intero come argomento e inizializza il membro data con il suo valore. Quindi, inizializza i puntatori a due nodi con valori nullptr, che è un modo comune per denotare i nodi foglia. Il codice del driver di esempio costruisce un grafico di esempio e memorizza numeri interi casuali in ogni nodo. Esistono più sottotipi di alberi binari, ad esempio un albero binario completo è una struttura in cui ogni nodo ha figli 0 o 2. Un altro è chiamato albero binario perfetto, in cui tutti i nodi interni hanno due figli e tutti i nodi foglia hanno profondità identiche.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  root->left = new BinTreeNode(distr(eng));
  root->right = new BinTreeNode(distr(eng));
  root->right->left = new BinTreeNode(distr(eng));
  root->right->right = new BinTreeNode(distr(eng));

  return EXIT_SUCCESS;
}

Si noti che il codice precedente risulta in una struttura ad albero binario completa, come mostrato nel grafico seguente. Abbiamo allocato ciascun nodo utilizzando l’operatore new e passato un valore di inizializzazione utilizzando il generatore di numeri pseudo-casuali.

root / left right / \ / nullptr nullptr left right /   \ /
    nullptr nullptr nullptr nullptr

Implementa funzioni per calcolare la dimensione e l’altezza della struttura ad albero e una funzione per stampare elementi in C++

Poiché la struttura ad albero è la forma in cui vengono eseguiti gli algoritmi di divisione e conquista, quest’ultimo metodo viene spesso utilizzato per implementare le funzioni che manipolano i loro elementi. La funzione treeSize recupera la dimensione dell’albero che denota il numero di tutti i nodi, inclusa la radice. Nota che abbiamo solo bisogno di usare una semplice ricorsione e restituire la dimensione del valore root (che è 1) più le dimensioni dei nodi sinistro/destro.

La funzione successiva è treeHeight che recupera l’altezza dell’albero, generalmente nota come la quantità di nodi nel percorso più lungo da una radice a una foglia. Questa funzione utilizza anche la ricorsione richiamandosi su entrambi i nodi figli e restituendo l’altezza del valore root (che è 1) più il valore maggiore delle chiamate precedenti.

D’altra parte, la funzione printData invia il membro data da ciascun nodo al flusso cout. Esistono diversi modi di attraversamento per la struttura ad albero binario: attraversamento inordine, preordine e postordine.

Nell’esempio seguente viene utilizzata la via di attraversamento in ordine. Il processo stampa i dati dai nodi foglia più a sinistra andando prima a destra alla stessa profondità e poi si sposta ai livelli superiori. Il prossimo frammento di codice costruisce un albero binario parzialmente casuale e quindi chiama su di esso ciascuna delle funzioni precedenti. Se la natura ricorsiva di queste funzioni sembra confondere a prima vista, dovresti provare a eseguirne il debug passo dopo passo sugli oggetti dell’albero più piccoli e osservare il comportamento su ogni chiamata di funzione ricorsiva.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

int treeSize(BinTreeNode *n) {
  if (n == nullptr)
    return 0;
  else
    return 1 + treeSize(n->left) + treeSize(n->right);
}

int treeHeight(BinTreeNode *n) {
  int lh, rh;

  if (n == nullptr)
    return -1;
  else {
    lh = treeHeight(n->left);
    rh = treeHeight(n->right);
    return 1 + (lh > rh ? lh : rh);
  }
}

void printData(BinTreeNode *n) {
  if (n != nullptr) {
    printData(n->left);
    cout << n->data << "; ";
    printData(n->right);
  }
}

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  auto tmp = root;

  auto iter = 100;
  while (iter > 0) {
    auto val = distr(eng);
    if (val % 5 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
      tmp = tmp->left;
    } else if (val % 4 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
      tmp = tmp->right;
    } else if (val % 6 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
    } else if (val % 100 == 0) {
      tmp = root;
    } else if (val % 2 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
    }
    iter -= 1;
  }

  cout << "size of tree = " << treeSize(root) << endl;
  cout << "height of tree = " << treeHeight(root) << endl;
  printData(root);

  return EXIT_SUCCESS;
}

Produzione:

size of tree = 45 height of tree = 37 ...(elements in the tree)