Implementare una struttura dati ad albero di ricerca binaria in C++

1. Implementare un albero di ricerca binario utilizzando la parola chiave struct in C++
2. Implementare l’algoritmo di ricerca binaria per un albero di ricerca binario in C++

Questa guida dimostrerà come implementare una struttura di dati ad albero di ricerca binaria in C++.

Implementare un albero di ricerca binario utilizzando la parola chiave struct in C++

Un albero di ricerca binario (BST) è un caso speciale di una struttura dati ad albero binario. La struttura dati viene solitamente utilizzata per memorizzare un elenco ordinato di elementi per la ricerca rapida utilizzando l’algoritmo di ricerca binaria. A differenza del normale albero binario, BST ha un membro dati speciale in ogni nodo chiamato key, che deve avere valori univoci.

Ogni nodo in un BST dovrebbe soddisfare il seguente requisito: il valore key deve essere maggiore di tutte le chiavi nel sottoalbero del suo figlio sinistro e minore di tutte le chiavi nel sottoalbero del suo figlio destro. L’affermazione precedente implica che gli elementi con valori chiave minori saranno posizionati sul lato sinistro della gerarchia ad albero; ciò si traduce in una struttura ottimale su cui utilizzare la ricerca binaria.

Nel seguente codice di esempio, definiamo una struct denominata BSTreeNode, composta da due puntatori ai nodi sinistro/destro e un membro stringa per denotare la chiave. Si noti che stiamo solo implementando la versione più semplice di BST, in cui il valore della chiave è lo stesso dei dati archiviati nel nodo.

In genere, il programmatore è libero di definire un nodo BST per memorizzare altri membri dati secondo necessità per il problema specifico. Questa definizione è più adatta per emulare l’array ordinato di stringhe, che deve essere cercato per una determinata stringa (chiave). Prima di implementare la funzione di ricerca binaria, l’oggetto BST deve essere costruito da zero. Pertanto, utilizziamo un vettore predefinito di stringhe per inizializzare un nuovo albero di ricerca binario.

La funzione insertNode è l’implementazione ricorsiva per creare un nuovo figlio BSTreeNode quando la radice dell’albero viene passata come argomento. Se dobbiamo creare un nodo radice stesso, puoi dichiarare un puntatore al tipo BSTreeNode, assegnargli nullptr e passarlo all’insertNode con il corrispondente valore string che deve essere memorizzato lì. Una volta che abbiamo inizializzato la lista con il contenuto v1, la funzione printTree può essere invocata per stampare tutti i valori chiave nell’ordine chiamato attraversamento inorder di BST.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

void printTree(BSTreeNode *n) {
  if (n != nullptr) {
    printTree(n->left);
    cout << n->key << "; ";
    printTree(n->right);
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printTree(root);

  return EXIT_SUCCESS;
}

Produzione:

aim;
born;
camel;
maya;
wind;
xen;
zero;

Implementare l’algoritmo di ricerca binaria per un albero di ricerca binario in C++

L’algoritmo di ricerca binaria è efficiente sulla struttura BST a causa dell’ordinamento, in cui le chiavi sono memorizzate nella gerarchia. Ci sono tre operazioni principali implementate per i BST: inserimento, cancellazione e ricerca.

Nell’esempio seguente, ci concentriamo maggiormente sulla ricerca. La funzione findNode è responsabile della ricerca della chiave data nel BST, che viene passata a una funzione utilizzando il suo nodo radice. Questo comando è di natura ricorsiva e restituisce il puntatore al BSTreeNode dove è memorizzata la chiave. Se il valore della chiave non viene trovato in nessun nodo, viene restituito nullptr. Per una migliore dimostrazione, abbiamo anche implementato una funzione printNode che prende il puntatore del nodo e restituisce il valore chiave al flusso cout per concatenare il valore di ritorno della funzione findNode direttamente nella funzione per stamparlo.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

BSTreeNode *findNode(BSTreeNode *root, const string &k) {
  if (root == nullptr) return nullptr;

  if (k == root->key) return root;

  if (k < root->key)
    return findNode(root->left, k);
  else
    return findNode(root->right, k);
}

void printNode(BSTreeNode *n) {
  if (n != nullptr) {
    cout << n->key << endl;
  } else {
    cout << "Not a valid node!" << endl;
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printNode(findNode(root, "zero"));
  printNode(findNode(root, "zeroo"));

  return EXIT_SUCCESS;
}

Produzione:

zero Not a valid node !