logo

TechCodeview

Introduzione all'albero binario: tutorial sulla struttura dei dati e sugli algoritmi

Albero binario è un struttura dati non lineare dove ogni nodo ha al massimo due figli. In questo articolo tratteremo tutte le nozioni di base sull'albero binario, le operazioni sull'albero binario, la sua implementazione, i vantaggi e gli svantaggi che ti aiuteranno a risolvere tutti i problemi basati sull'albero binario.

Tabella dei contenuti



restituendo un array java

Cos'è l'albero binario?

L'albero binario è a struttura dati ad albero (non lineare) in cui ogni nodo può avere al massimo due figli che sono indicati come bambino sinistro e il bambino giusto .

Il nodo più in alto in un albero binario è chiamato radice e vengono chiamati i nodi più in basso foglie . Un albero binario può essere visualizzato come una struttura gerarchica con la radice in alto e le foglie in basso.

Rappresentazione dell'albero binario

Ogni nodo in un albero binario è composto da tre parti:



  • Dati
  • Puntatore al bambino sinistro
  • Puntatore al bambino giusto

Di seguito la rappresentazione di un Nodo dell'Albero Binario in diverse lingue:

C++ 
// Use any below method to implement Nodes of tree // Method 1: Using 'struct' to make // user-define data type struct node {  int data;  struct node* left;  struct node* right; }; // Method 2: Using 'class' to make // user-define data type class Node { public:  int data;  Node* left;  Node* right; };>
C 
// Structure of each node of the tree struct node {  int data;  struct node* left;  struct node* right; };>
Giava 
// Class containing left and right child // of current node and key value class Node {  int key;  Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } }>
Pitone 
# A Python class that represents # an individual node in a Binary Tree class Node: def __init__(self, key): self.left = None self.right = None self.val = key>
C# 
// Class containing left and right child // of current node and key value class Node {  int key;  Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } }>
JavaScript 
>

Tipi di albero binario

L'albero binario può essere classificato in più tipologie in base a molteplici fattori:



Operazioni sull'albero binario

1. Inserimento nell'albero binario

Possiamo inserire un nodo ovunque in un albero binario inserendo il nodo come figlio sinistro o destro di qualsiasi nodo o rendendo il nodo come radice dell'albero.

Algoritmo per inserire un nodo in un albero binario:

  • Controlla se c'è un nodo nell'albero binario a cui manca il figlio sinistro. Se tale nodo esiste, inserisci il nuovo nodo come figlio sinistro.
  • Controlla se c'è un nodo nell'albero binario a cui manca il figlio destro. Se tale nodo esiste, inserisci il nuovo nodo come figlio destro.
  • Se non troviamo alcun nodo con il figlio sinistro o destro mancante, trova il nodo in cui mancano entrambi i figli e inserisci il nodo come figlio sinistro o destro.

2. Attraversamento dell'albero binario

L'attraversamento dell'albero binario implica la visita di tutti i nodi dell'albero binario. Gli algoritmi di Tree Traversal possono essere classificati sostanzialmente in due categorie:

  • Algoritmi di ricerca in profondità (DFS).
  • Algoritmi di ricerca in ampiezza (BFS).

Algoritmi Depth-First Search (DFS):

  • Traslazione preordine (attuale-sinistra-destra): Visita il nodo corrente prima di visitare qualsiasi nodo all'interno dei sottoalberi sinistro o destro. Qui la traversata è radice – figlio sinistro – figlio destro. Ciò significa che viene attraversato prima il nodo radice, poi il figlio sinistro e infine il figlio destro.
  • Attraversamento in ordine (sinistra-corrente-destra): Visita il nodo corrente dopo aver visitato tutti i nodi all'interno del sottoalbero sinistro ma prima di visitare qualsiasi nodo all'interno del sottoalbero destro. Qui, la traversata è figlio sinistro – radice – figlio destro. Ciò significa che viene attraversato prima il figlio di sinistra, poi il suo nodo radice e infine il figlio di destra.
  • Attraversamento Postorder (sinistra-destra-corrente): Visita il nodo corrente dopo aver visitato tutti i nodi dei sottoalberi sinistro e destro. Qui, la traversata è figlio sinistro – figlio destro – radice. Significa che il figlio sinistro ha attraversato prima il figlio destro e infine il suo nodo radice.

Algoritmi BFS (Breadth-First Search):

  • Attraversamento dell'ordine di livello: Visita i nodi livello per livello e da sinistra a destra allo stesso livello. Qui la traversata è in piano. Significa che il bambino più a sinistra ha attraversato per primo e poi hanno attraversato gli altri bambini dello stesso livello da sinistra a destra.

3. Cancellazione nell'albero binario

Possiamo eliminare qualsiasi nodo nell'albero binario e riorganizzare i nodi dopo l'eliminazione per formare nuovamente un albero binario valido.

Algoritmo per eliminare un nodo in un albero binario:

  • Partendo dalla radice, trova il nodo più profondo e più a destra nell'albero binario e il nodo che vogliamo eliminare.
  • Sostituisci i dati del nodo più a destra con il nodo da eliminare.
  • Quindi elimina il nodo più profondo a destra.

4. Ricerca nell'albero binario

Possiamo cercare un elemento nel nodo utilizzando una qualsiasi delle tecniche di attraversamento.

Algoritmo per cercare un nodo in un albero binario:

  • Inizia dal nodo radice.
  • Controlla se il valore del nodo corrente è uguale al valore di destinazione.
  • Se il valore del nodo corrente è uguale al valore di destinazione, allora questo nodo è il nodo richiesto.
  • Altrimenti, se il valore del nodo non è uguale al valore di destinazione, avvia la ricerca nel figlio sinistro e destro.
  • Se non troviamo nessun nodo il cui valore sia uguale a target, allora il valore non è presente nell'albero.

Operazioni ausiliarie sull'albero binario

Implementazione dell'albero binario

Di seguito il codice per l'inserimento, la cancellazione e l'attraversamento dell'albero binario:

matrice di stringhe del programma c
C 
#include  // Node structure to define the structure of the node typedef struct Node {  int data;  struct Node *left, *right; } Node; // Function to create a new node Node* newNode(int val) {  Node* temp = (Node*)malloc(sizeof(Node));  temp->dati = val;  temp->sinistra = temp->destra = NULL;  temperatura di ritorno; } // Funzione per inserire i nodi Node* insert(Node* root, int data) { // Se l'albero è vuoto, il nuovo nodo diventa la root if (root == NULL) { root = newNode(data);  restituisce radice;  } // Coda per attraversare l'albero e trovare la posizione in cui inserire il nodo Node* coda[100];  int anteriore = 0, posteriore = 0;  coda[posteriore++] = root;  while (anteriore!= posteriore) { Nodo* temp = coda[anteriore++];  // Inserisci il nodo come figlio sinistro del nodo genitore if (temp->left == NULL) { temp->left = newNode(data);  rottura;  } // Se il figlio sinistro non è nullo, lo inserisce nella coda else code[rear++] = temp->left;  // Inserisci il nodo come figlio destro del nodo genitore if (temp->right == NULL) { temp->right = newNode(data);  rottura;  } // Se il figlio destro non è nullo, invialo alla coda else code[rear++] = temp->right;  } restituisce root; } /* Funzione per eliminare il nodo più profondo specificato (d_node) nell'albero binario */ void deletDeepest(Node* root, Node* d_node) { Node* Queue[100];  int anteriore = 0, posteriore = 0;  coda[posteriore++] = radice;  // Effettua l'attraversamento dell'ordine dei livelli fino all'ultimo nodo Node* temp;  while (anteriore!= posteriore) { temp = coda[anteriore++];  if (temp == d_nodo) { temp = NULL;  libero(d_nodo);  ritorno;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  libero(d_nodo);  ritorno;  } else coda[retro++] = temp->destra;  } if (temp->sinistra) { if (temp->sinistra == nodo_d) { temp->sinistra = NULL;  libero(d_nodo);  ritorno;  } else coda[retro++] = temp->sinistra;  } } } /* Funzione per eliminare l'elemento nell'albero binario */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL;  altrimenti restituisce root;  } Nodo* coda[100];  int anteriore = 0, posteriore = 0;  coda[posteriore++] = radice;  Nodo* temperatura;  Nodo* nodo_chiave = NULL;  // Esegue l'attraversamento dell'ordine dei livelli per trovare il nodo più profondo (temp) e il nodo da eliminare (key_node) while (front != posterior) { temp = tail[front++];  if (temp->data == chiave) key_node = temp;  if (temp->sinistra) coda[retro++] = temp->sinistra;  if (temp->destra) coda[retro++] = temp->destra;  } if (nodo_chiave!= NULL) { int x = temp->dati;  nodo_chiave->dati = x;  deleteDeepest(root, temp);  } restituisce root; } // Attraversamento dell'albero in ordine (Sinistra - Radice - Destra) void inorderTraversal(Nodo* root) { if (!root) return;  inorderTraversal(radice->sinistra);  printf('%d', root->dati);  inorderTraversal(radice->destra); } // Preordina l'attraversamento dell'albero (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return;  printf('%d', root->dati);  preorderTraversal(root->left);  preorderTraversal(root->right); } // Attraversamento dell'albero postorder (Sinistra - Destra - Radice) void postorderTraversal(Nodo* root) { if (root == NULL) return;  postorderTraversal(radice->sinistra);  postorderTraversal(radice->destra);  printf('%d', root->dati); } // Funzione per l'attraversamento dell'albero dell'ordine dei livelli void levelorderTraversal(Node* root) { if (root == NULL) return;  // Coda per l'attraversamento dell'ordine di livello Node* coda[100];  int anteriore = 0, posteriore = 0;  coda[posteriore++] = root;  while (anteriore!= posteriore) { Nodo* temp = coda[anteriore++];  printf('%d ', temp->dati);  // Spingi il figlio sinistro nella coda se (temp->left) tail[rear++] = temp->left;  // Spingi il figlio destro nella coda se (temp->right) tail[rear++] = temp->right;  } } /* Funzione del driver per verificare l'algoritmo di cui sopra. */ int main() { Nodo* root = NULL;  // Inserimento dei nodi root = insert(root, 10);  radice = inserisci(radice, 20);  radice = inserisci(radice, 30);  radice = inserisci(radice, 40);  printf('Attraversamento preordine: ');  preorderTraversal(root);  printf('
Attraversamento in ordine: ');  inorderTraversal(radice);  printf('
Attraversamento postordine: ');  postorderTraversal(radice);  printf('
Attraversamento dell'ordine dei livelli: ');  levelorderTraversal(root);  // Elimina il nodo con dati = 20 root = delete(root, 20);  printf('
Attraversamento in ordine dopo l'eliminazione: ');  inorderTraversal(radice);  restituire 0; }>
Giava 
import java.util.LinkedList; import java.util.Queue; // Node class to define the structure of the node class Node {  int data;  Node left, right;  // Parameterized Constructor  Node(int val) {  data = val;  left = right = null;  } } public class BinaryTree {  // Function to insert nodes  public static Node insert(Node root, int data) {  // If tree is empty, new node becomes the root  if (root == null) {  root = new Node(data);  return root;  }  // Queue to traverse the tree and find the position to  // insert the node  Queueq = nuova ListaCollegata();  q.offerta(root);  while (!q.isEmpty()) { Node temp = q.poll();  // Inserisci il nodo come figlio sinistro del nodo genitore if (temp.left == null) { temp.left = new Node(data);  rottura;  } // Se il figlio sinistro non è nullo, spingilo nella // coda else q.offer(temp.left);  // Inserisci il nodo come figlio destro del nodo genitore if (temp.right == null) { temp.right = new Node(data);  rottura;  } // Se il figlio giusto non è nullo, spingilo nella // coda else q.offer(temp.right);  } restituisce root;  } /* funzione per eliminare il nodo più profondo specificato (d_node) nell'albero binario */ public static void deletDeepest(Node root, Node d_node) { Queueq = nuova ListaCollegata();  q.offerta(root);  // Effettua l'attraversamento dell'ordine dei livelli fino all'ultimo nodo Node temp;  while (!q.isEmpty()) { temp = q.poll();  if (temp == d_nodo) { temp = null;  d_nodo = nullo;  ritorno;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_nodo = nullo;  ritorno;  } else q.offer(temp.right);  } if (temp.sinistra!= null) { if (temp.sinistra == d_nodo) { temp.sinistra = null;  d_nodo = nullo;  ritorno;  } else q.offer(temp.left);  } } } /* funzione per eliminare l'elemento nell'albero binario */ public static Node deletion(Node root, int key) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == key) return null;  altrimenti restituisce root;  }  Codaq = nuova ListaCollegata();  q.offerta(root);  Temp. nodo = nuovo nodo(0);  Nodo chiave_nodo = null;  // Esegue l'attraversamento dell'ordine dei livelli per trovare il nodo più profondo // node(temp) e il nodo da eliminare (key_node) while (!q.isEmpty()) { temp = q.poll();  if (temp.data == chiave) key_node = temp;  if (temp.sinistra!= null) q.offerta(temp.sinistra);  if (temp.right != null) q.offer(temp.right);  } if (nodo_chiave!= null) { int x = temp.data;  chiave_nodo.data = x;  deleteDeepest(root, temp);  } restituisce root;  } // Attraversamento dell'albero in ordine (Sinistra - Radice - Destra) public static void inorderTraversal(Radice del nodo) { if (radice == null) return;  inorderTraversal(root.left);  System.out.print(root.data + ' ');  inorderTraversal(root.right);  } // Preordina l'attraversamento dell'albero (Root - Left - Right) public static void preorderTraversal(Node root) { if (root == null) return;  System.out.print(root.data + ' ');  preorderTraversal(root.left);  preorderTraversal(root.right);  } // Attraversamento dell'albero postorder (Sinistra - Destra - Radice) public static void postorderTraversal(Nodo root) { if (root == null) return;  postorderTraversal(root.left);  postorderTraversal(root.right);  System.out.print(root.data + ' ');  } // Funzione per l'attraversamento dell'albero dell'ordine dei livelli public static void levelorderTraversal(Node root) { if (root == null) return;  // Coda per l'attraversamento dell'ordine di livello Queueq = nuova ListaCollegata();  q.offerta(root);  while (!q.isEmpty()) { Node temp = q.poll();  System.out.print(temp.data + ' ');  // Spingi il figlio sinistro nella coda if (temp.left != null) q.offer(temp.left);  // Inserisci il figlio destro nella coda if (temp.right != null) q.offer(temp.right);  } } /* Funzione del driver per verificare l'algoritmo di cui sopra. */ public static void main(String[] args) { Node root = null;  // Inserimento dei nodi root = insert(root, 10);  radice = inserisci(radice, 20);  radice = inserisci(radice, 30);  radice = inserisci(radice, 40);  System.out.print('Attraversamento preordine: ');  preorderTraversal(root);  System.out.print('
Attraversamento dell'ordine: ');  inorderTraversal(radice);  System.out.print('
Attraversamento postorder: ');  postorderTraversal(radice);  System.out.print('
Attraversamento dell'ordine di livello: ');  levelorderTraversal(root);  // Elimina il nodo con dati = 20 root = delete(root, 20);  System.out.print('
Attraversamento dell'ordine dopo l'eliminazione: ');  inorderTraversal(radice);  } }>
Pitone 
from collections import deque # Node class to define the structure of the node class Node: def __init__(self, val): self.data = val self.left = self.right = None # Function to insert nodes def insert(root, data): # If tree is empty, new node becomes the root if root is None: root = Node(data) return root # Queue to traverse the tree and find the position to insert the node q = deque() q.append(root) while q: temp = q.popleft() # Insert node as the left child of the parent node if temp.left is None: temp.left = Node(data) break # If the left child is not null push it to the queue else: q.append(temp.left) # Insert node as the right child of parent node if temp.right is None: temp.right = Node(data) break # If the right child is not null push it to the queue else: q.append(temp.right) return root # Function to delete the given deepest node (d_node) in binary tree def deletDeepest(root, d_node): q = deque() q.append(root) # Do level order traversal until last node while q: temp = q.popleft() if temp == d_node: temp = None del d_node return if temp.right: if temp.right == d_node: temp.right = None del d_node return else: q.append(temp.right) if temp.left: if temp.left == d_node: temp.left = None del d_node return else: q.append(temp.left) # Function to delete element in binary tree def deletion(root, key): if not root: return None if root.left is None and root.right is None: if root.data == key: return None else: return root q = deque() q.append(root) temp = None key_node = None # Do level order traversal to find deepest node (temp) and node to be deleted (key_node) while q: temp = q.popleft() if temp.data == key: key_node = temp if temp.left: q.append(temp.left) if temp.right: q.append(temp.right) if key_node is not None: x = temp.data key_node.data = x deletDeepest(root, temp) return root # Inorder tree traversal (Left - Root - Right) def inorderTraversal(root): if not root: return inorderTraversal(root.left) print(root.data, end=' ') inorderTraversal(root.right) # Preorder tree traversal (Root - Left - Right) def preorderTraversal(root): if not root: return print(root.data, end=' ') preorderTraversal(root.left) preorderTraversal(root.right) # Postorder tree traversal (Left - Right - Root) def postorderTraversal(root): if root is None: return postorderTraversal(root.left) postorderTraversal(root.right) print(root.data, end=' ') # Function for Level order tree traversal def levelorderTraversal(root): if root is None: return # Queue for level order traversal q = deque() q.append(root) while q: temp = q.popleft() print(temp.data, end=' ') # Push left child in the queue if temp.left: q.append(temp.left) # Push right child in the queue if temp.right: q.append(temp.right) # Driver function to check the above algorithm if __name__ == '__main__': root = None # Insertion of nodes root = insert(root, 10) root = insert(root, 20) root = insert(root, 30) root = insert(root, 40) print('Preorder traversal:', end=' ') preorderTraversal(root) print('
Inorder traversal:', end=' ') inorderTraversal(root) print('
Postorder traversal:', end=' ') postorderTraversal(root) print('
Level order traversal:', end=' ') levelorderTraversal(root) # Delete the node with data = 20 root = deletion(root, 20) print('
Inorder traversal after deletion:', end=' ') inorderTraversal(root)>
C# 
using System; using System.Collections.Generic; // Node class to define the structure of the node public class Node {  public int data;  public Node left, right;  // Parameterized Constructor  public Node(int val)  {  data = val;  left = right = null;  } } public class Program {  // Function to insert nodes  public static Node Insert(Node root, int data)  {  // If tree is empty, new node becomes the root  if (root == null)  {  root = new Node(data);  return root;  }  // Queue to traverse the tree and find the position to insert the node  Queueq = nuova coda();  q.Enqueue(root);  while (q.Count!= 0) { Temp. nodo = q.Dequeue();  // Inserisci il nodo come figlio sinistro del nodo genitore if (temp.left == null) { temp.left = new Node(data);  rottura;  } // Se il figlio sinistro non è nullo, invialo alla coda else q.Enqueue(temp.left);  // Inserisci il nodo come figlio destro del nodo genitore if (temp.right == null) { temp.right = new Node(data);  rottura;  } // Se il figlio destro non è nullo, invialo alla coda else q.Enqueue(temp.right);  } restituisce root;  } /* funzione per eliminare il nodo più profondo specificato (d_node) nell'albero binario */ public static void DeleteDeepest(Node root, Node d_node) { Queueq = nuova coda();  q.Enqueue(root);  // Effettua l'attraversamento dell'ordine dei livelli fino all'ultimo nodo Node temp;  while (q.Count!= 0) { temp = q.Dequeue();  if (temp == d_nodo) { temp = null;  d_nodo = nullo;  ritorno;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_nodo = nullo;  ritorno;  } else q.Enqueue(temp.right);  } if (temp.sinistra!= null) { if (temp.sinistra == d_nodo) { temp.sinistra = null;  d_nodo = nullo;  ritorno;  } else q.Enqueue(temp.left);  } } } /* funzione per eliminare l'elemento nell'albero binario */ public static Node Deletion(Node root, int key) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == key) return null;  altrimenti restituisce root;  }  Codaq = nuova coda();  q.Enqueue(root);  Temp. nodo = nuovo nodo(0);  Nodo chiave_nodo = null;  // Esegue l'attraversamento dell'ordine dei livelli per trovare il nodo più profondo (temp) e il nodo da eliminare (key_node) while (q.Count != 0) { temp = q.Dequeue();  if (temp.data == chiave) key_node = temp;  if (temp.left!= null) q.Enqueue(temp.left);  if (temp.right!= null) q.Enqueue(temp.right);  } if (nodo_chiave!= null) { int x = temp.data;  chiave_nodo.data = x;  EliminaDeepest(root, temp);  } restituisce root;  } // Attraversamento dell'albero in ordine (Sinistra - Radice - Destra) public static void InorderTraversal(Nodo root) { if (root == null) return;  InorderTraversal(root.left);  Console.Write(root.data + ' ');  InorderTraversal(root.right);  } // Preordina l'attraversamento dell'albero (Root - Left - Right) public static void PreorderTraversal(Node root) { if (root == null) return;  Console.Write(root.data + ' ');  PreorderTraversal(root.left);  PreorderTraversal(root.right);  } // Attraversamento dell'albero Postorder (Sinistra - Destra - Radice) public static void PostorderTraversal(Nodo root) { if (root == null) return;  PostorderTraversal(root.left);  PostorderTraversal(root.right);  Console.Write(root.data + ' ');  } // Funzione per l'attraversamento dell'albero dell'ordine dei livelli public static void LevelorderTraversal(Node root) { if (root == null) return;  // Coda per l'attraversamento dell'ordine di livello Queueq = nuova coda();  q.Enqueue(root);  while (q.Count!= 0) { Temp. nodo = q.Dequeue();  Console.Write(temp.data + ' ');  // Spinge il figlio sinistro nella coda if (temp.left != null) q.Enqueue(temp.left);  // Spinge il figlio destro nella coda if (temp.right != null) q.Enqueue(temp.right);  } } /* Funzione del driver per verificare l'algoritmo di cui sopra. */ public static void Main(string[] args) { Node root = null;  // Inserimento dei nodi root = Insert(root, 10);  radice = Inserisci(radice, 20);  radice = Inserisci(radice, 30);  radice = Inserisci(radice, 40);  Console.Write('Attraversamento preordine: ');  PreorderTraversal(radice);  Console.Write('
Attraversamento dell'ordine: ');  InorderTraversal(radice);  Console.Write('
Attraversamento postordine: ');  PostorderTraversal(radice);  Console.Write('
Attraversamento ordine di livello: ');  LevelorderTraversal(radice);  // Elimina il nodo con dati = 20 root = Deletion(root, 20);  Console.Write('
Attraversamento dell'ordine dopo l'eliminazione: ');  InorderTraversal(radice);  } }>
Javascript 
// Node class to define the structure of the node class Node {  constructor(val) {  this.data = val;  this.left = null;  this.right = null;  } } // Function to insert nodes function insert(root, data) {  // If tree is empty, new node becomes the root  if (root === null) {  root = new Node(data);  return root;  }  // queue to traverse the tree and find the position to  // insert the node  const q = [];  q.push(root);  while (q.length !== 0) {  const temp = q.shift();  // Insert node as the left child of the parent node  if (temp.left === null) {  temp.left = new Node(data);  break;  }  // If the left child is not null push it to the  // queue  else  q.push(temp.left);  // Insert node as the right child of parent node  if (temp.right === null) {  temp.right = new Node(data);  break;  }  // If the right child is not null push it to the  // queue  else  q.push(temp.right);  }  return root; } /* function to delete the given deepest node (d_node) in binary tree */ function deletDeepest(root, d_node) {  const q = [];  q.push(root);  // Do level order traversal until last node  let temp;  while (q.length !== 0) {  temp = q.shift();  if (temp === d_node) {  temp = null;  delete d_node;  return;  }  if (temp.right) {  if (temp.right === d_node) {  temp.right = null;  delete d_node;  return;  }  else  q.push(temp.right);  }  if (temp.left) {  if (temp.left === d_node) {  temp.left = null;  delete d_node;  return;  }  else  q.push(temp.left);  }  } } /* function to delete element in binary tree */ function deletion(root, key) {  if (!root)  return null;  if (root.left === null && root.right === null) {  if (root.data === key)  return null;  else  return root;  }  const q = [];  q.push(root);  let temp;  let key_node = null;  // Do level order traversal to find deepest  // node(temp) and node to be deleted (key_node)  while (q.length !== 0) {  temp = q.shift();  if (temp.data === key)  key_node = temp;  if (temp.left)  q.push(temp.left);  if (temp.right)  q.push(temp.right);  }  if (key_node !== null) {  const x = temp.data;  key_node.data = x;  deletDeepest(root, temp);  }  return root; } // Inorder tree traversal (Left - Root - Right) function inorderTraversal(root) {  if (!root)  return;  inorderTraversal(root.left);  console.log(root.data + ' ');  inorderTraversal(root.right); } // Preorder tree traversal (Root - Left - Right) function preorderTraversal(root) {  if (!root)  return;  console.log(root.data + ' ');  preorderTraversal(root.left);  preorderTraversal(root.right); } // Postorder tree traversal (Left - Right - Root) function postorderTraversal(root) {  if (root === null)  return;  postorderTraversal(root.left);  postorderTraversal(root.right);  console.log(root.data + ' '); } // Function for Level order tree traversal function levelorderTraversal(root) {  if (root === null)  return;  // Queue for level order traversal  const q = [];  q.push(root);  while (q.length !== 0) {  const temp = q.shift();  console.log(temp.data + ' ');  // Push left child in the queue  if (temp.left)  q.push(temp.left);  // Push right child in the queue  if (temp.right)  q.push(temp.right);  } } /* Driver function to check the above algorithm. */ let root = null; // Insertion of nodes root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); console.log('Preorder traversal: '); preorderTraversal(root); console.log('
Inorder traversal: '); inorderTraversal(root); console.log('
Postorder traversal: '); postorderTraversal(root); console.log('
Level order traversal: '); levelorderTraversal(root); // Delete the node with data = 20 root = deletion(root, 20); console.log('
Inorder traversal after deletion: '); inorderTraversal(root);>
C++14 
#include  using namespace std; // Node class to define the structure of the node class Node { public:  int data;  Node *left, *right;  // Parameterized Constructor  Node(int val)  {  data = val;  left = right = NULL;  } }; // Function to insert nodes Node* insert(Node* root, int data) {  // If tree is empty, new node becomes the root  if (root == NULL) {  root = new Node(data);  return root;  }  // queue to traverse the tree and find the position to  // insert the node  queueQ;  q.push(root);  while (!q.empty()) { Node* temp = q.front();  q.pop();  // Inserisci il nodo come figlio sinistro del nodo genitore if (temp->left == NULL) { temp->left = new Node(data);  rottura;  } // Se il figlio sinistro non è nullo, spingilo nella // coda else q.push(temp->left);  // Inserisci il nodo come figlio destro del nodo genitore if (temp->right == NULL) { temp->right = new Node(data);  rottura;  } // Se il figlio destro non è nullo, spingilo nella // coda else q.push(temp->right);  } restituisce root; } /* funzione per eliminare il nodo più profondo specificato (d_node) nell'albero binario */ void deletDeepest(Node* root, Node* d_node) { codaQ;  q.push(root);  // Effettua l'attraversamento dell'ordine dei livelli fino all'ultimo nodo Node* temp;  while (!q.empty()) { temp = q.front();  q.pop();  if (temp == d_nodo) { temp = NULL;  elimina (d_nodo);  ritorno;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  elimina (d_nodo);  ritorno;  } else q.push(temp->right);  } if (temp->sinistra) { if (temp->sinistra == nodo_d) { temp->sinistra = NULL;  elimina (d_nodo);  ritorno;  } else q.push(temp->left);  } } } /* funzione per eliminare l'elemento nell'albero binario */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL;  altrimenti restituisce root;  }  codaQ;  q.push(root);  Nodo* temperatura;  Nodo* nodo_chiave = NULL;  // Esegue l'attraversamento dell'ordine dei livelli per trovare il nodo più profondo // node(temp) e il nodo da eliminare (key_node) while (!q.empty()) { temp = q.front();  q.pop();  if (temp->data == chiave) key_node = temp;  if (temp->sinistra) q.push(temp->sinistra);  if (temp->destra) q.push(temp->destra);  } if (nodo_chiave!= NULL) { int x = temp->dati;  nodo_chiave->dati = x;  deleteDeepest(root, temp);  } restituisce root; } // Attraversamento dell'albero in ordine (Sinistra - Radice - Destra) void inorderTraversal(Nodo* root) { if (!root) return;  inorderTraversal(radice->sinistra);  cout<< root->dati<< ' ';  inorderTraversal(root->Giusto); } // Preordina l'attraversamento dell'albero (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return;  cout<< root->dati<< ' ';  preorderTraversal(root->Sinistra);  preorderTraversal(root->right); } // Attraversamento dell'albero postorder (Sinistra - Destra - Radice) void postorderTraversal(Nodo* root) { if (root == NULL) return;  postorderTraversal(radice->sinistra);  postorderTraversal(radice->destra);  cout<< root->dati<< ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) {  if (root == NULL)  return;  // Queue for level order traversal  queueQ;  q.push(root);  while (!q.empty()) { Node* temp = q.front();  q.pop();  cout<< temp->dati<< ' ';  // Push left child in the queue  if (temp->sinistra) q.push(temp->sinistra);  // Spingi il figlio destro nella coda if (temp->right) q.push(temp->right);  } } /* Funzione del driver per verificare l'algoritmo di cui sopra. */ int main() { Nodo* root = NULL;  // Inserimento dei nodi root = insert(root, 10);  radice = inserisci(radice, 20);  radice = inserisci(radice, 30);  radice = inserisci(radice, 40);  cout<< 'Preorder traversal: ';  preorderTraversal(root);  cout << '
Inorder traversal: ';  inorderTraversal(root);  cout << '
Postorder traversal: ';  postorderTraversal(root);  cout << '
Level order traversal: ';  levelorderTraversal(root);  // Delete the node with data = 20  root = deletion(root, 20);  cout << '
Inorder traversal after deletion: ';  inorderTraversal(root); }>
Produzione 
Preorder traversal: 10 20 40 30 Inorder traversal: 40 20 10 30 Postorder traversal: 40 20 30 10 Level order traversal: 10 20 30 40 Inorder traversal after deletion: 40 10 30>

Analisi della complessità delle operazioni sugli alberi binari

Operazioni Complessità temporale

Complessità spaziale

applicazioni di cloud computing
Inserimento SU)

SU)

Traversata del preordine SU)

SU)

Attraversamento in ordine

SU)

SU)

Traslazione vaglia postaleSU)

SU)

Attraversamento dell'ordine di livelloSU)

SU)

Cancellazione

Tutorial sul linguaggio di programmazione Java

SU)

SU)

Ricerca

SU)

SU)

Possiamo usare Morris Traversata per attraversare tutti i nodi dell'albero binario in tempo O(1).

Vantaggi dell'albero binario

Svantaggi dell'albero binario

Applicazioni dell'albero binario

Domande frequenti sull'albero binario

1. Cos'è un albero binario?

Un albero binario è una struttura dati non lineare costituita da nodi, in cui ciascun nodo ha al massimo due figli (figlio sinistro e figlio destro).

2. Quali sono i tipi di alberi binari?

Gli alberi binari possono essere classificati in vari tipi, inclusi alberi binari completi, alberi binari completi, alberi binari perfetti, alberi binari bilanciati (come alberi AVL e alberi rosso-neri) e alberi binari degenerati (o patologici).

3. Qual è l'altezza di un albero binario?

L'altezza di un albero binario è la lunghezza del percorso più lungo dal nodo radice al nodo foglia. Rappresenta il numero di spigoli nel percorso più lungo dal nodo radice al nodo foglia.

4. Qual è la profondità di un nodo in un albero binario?

La profondità di un nodo in un albero binario è la lunghezza del percorso dal nodo radice a quel particolare nodo. La profondità del nodo radice è 0.

5. Come si esegue l'attraversamento dell'albero in un albero binario?

L'attraversamento dell'albero in un albero binario può essere eseguito in diversi modi: attraversamento in ordine, attraversamento pre-ordine, attraversamento post-ordine e attraversamento livello-ordine (noto anche come attraversamento in ampiezza).

6. Cos'è un attraversamento in ordine nell'albero binario?

Nell'attraversamento in ordine, i nodi vengono visitati ricorsivamente in questo ordine: figlio sinistro, radice, figlio destro. Questo attraversamento fa sì che i nodi vengano visitati in ordine non decrescente in un albero di ricerca binario.

7. Cos'è un attraversamento del preordine in Binary Tree?

Nell'attraversamento del preordine, i nodi vengono visitati ricorsivamente in questo ordine: radice, figlio sinistro, figlio destro. Questo attraversamento fa sì che il nodo radice sia il primo nodo ad essere visitato.

Java lancia un'eccezione

8. Cos'è un attraversamento Postorder in Binary Tree?

Nell'attraversamento Postorder, i nodi vengono visitati ricorsivamente in questo ordine: figlio sinistro, figlio destro e radice. Questo attraversamento fa sì che il nodo radice sia l'ultimo nodo ad essere visitato.

9. Qual è la differenza tra un albero binario e un albero di ricerca binario?

Un albero binario è una struttura dati gerarchica in cui ogni nodo ha al massimo due figli, mentre un albero di ricerca binario è un tipo di albero binario in cui il figlio sinistro di un nodo contiene valori inferiori al valore del nodo e il figlio destro contiene valori maggiore del valore del nodo.

10. Cos'è un albero binario equilibrato?

Un albero binario bilanciato è un albero binario in cui l'altezza dei sottoalberi sinistro e destro di ogni nodo differisce al massimo di uno. Gli alberi bilanciati aiutano a mantenere operazioni efficienti come la ricerca, l'inserimento e l'eliminazione con complessità temporali prossime a O(log n).

Conclusione:

L'albero è una struttura di dati gerarchica. Gli usi principali degli alberi includono il mantenimento dei dati gerarchici, la fornitura di accesso moderato e operazioni di inserimento/eliminazione. Gli alberi binari sono casi particolari di alberi in cui ogni nodo ha al massimo due figli.

Articoli Correlati:

  • Proprietà dell'albero binario
  • Tipi di albero binario