INTRODUCCIÓ A L'ARBRE BINARI - TUTORIALS D'ESTRUCTURA DE DADES I ALGORISME - TECHCODEVIEW.COM

Arbre binari és un Estructura de dades no lineal on cada node té com a màxim dos fills. En aquest article, tractarem tots els conceptes bàsics de l'arbre binari, les operacions sobre l'arbre binari, la seva implementació, els avantatges i els inconvenients que us ajudaran a resoldre tots els problemes basats en l'arbre binari.

Taula de contingut

Què és l'arbre binari?
Representació de l'arbre binari
Tipus d'arbre binari
Operacions en arbre binari
Operacions auxiliars en arbre binari
Implementació de l'arbre binari
Anàlisi de complexitat d'operacions d'arbre binari
Avantatges de l'arbre binari
Inconvenients de l'arbre binari
Aplicacions de l'arbre binari
Preguntes freqüents sobre l'arbre binari

Què és l'arbre binari?

L'arbre binari és un estructura de dades en arbre (no lineal) en què cada node pot tenir com a màxim dos fills que s'anomenen els fill deixat i la fill dret .

El node superior d'un arbre binari s'anomena arrel , i els nodes més baixos s'anomenen fulles . Un arbre binari es pot visualitzar com una estructura jeràrquica amb l'arrel a la part superior i les fulles a la part inferior.

Representació de l'arbre binari

Cada node d'un arbre binari té tres parts:

Dades
Punter al nen esquerre
Apuntador al nen correcte

A continuació es mostra la representació d'un node d'arbre binari en diferents idiomes:

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

 // Structure of each node of the tree struct node {  int data;  struct node* left;  struct node* right; };>

Java

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

Python

 # 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>

 // 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

Tipus d'arbre binari

L'arbre binari es pot classificar en múltiples tipus basats en múltiples factors:

En funció del nombre de nens
- Arbre binari complet
- Arbre binari degenerat
- Arbres binaris esbiaixats
Sobre la base de la superació de nivells
- Arbre binari complet
- Arbre binari perfecte
- Arbre binari equilibrat
Sobre la base dels valors dels nodes:
- Arbre de cerca binari
- Arbre AVL
- Arbre negre vermell
- B Arbre
- Arbre B+
- Arbre de segments

Operacions en arbre binari

1. Inserció en arbre binari

Podem inserir un node en qualsevol lloc d'un arbre binari inserint el node com a fill esquerre o dret de qualsevol node o fent que el node sigui l'arrel de l'arbre.

Algorisme per inserir un node en un arbre binari:

Comproveu si hi ha un node a l'arbre binari, que té un fill esquerre perdut. Si aquest node existeix, inseriu el nou node com a fill esquerre.
Comproveu si hi ha un node a l'arbre binari al qual falta el fill dret. Si aquest node existeix, inseriu el nou node com a fill dret.
Si no trobem cap node amb el fill esquerre o dret que falta, busqueu el node que té els dos fills que falten i inseriu el node com a fill esquerre o dret.

2. Travessa de l'arbre binari

La travessa de l'arbre binari implica visitar tots els nodes de l'arbre binari. Els algorismes de travessa d'arbres es poden classificar a grans trets en dues categories:

Algorismes de cerca en profunditat (DFS).
Algorismes de cerca d'amplada primer (BFS).

Algorismes de cerca en profunditat (DFS):

Preordena Traversal (actual-esquerra-dreta): Visiteu el node actual abans de visitar qualsevol node dins dels subarbres esquerre o dret. Aquí, el recorregut és arrel - fill esquerre - fill dret. Vol dir que es travessa primer el node arrel, després el seu fill esquerre i finalment el fill dret.
Travessia en ordre (esquerra-actual-dreta): Visiteu el node actual després de visitar tots els nodes dins del subarbre esquerre però abans de visitar qualsevol node dins del subarbre dret. Aquí, el recorregut és fill esquerre - arrel - fill dret. Vol dir que es recorre primer el fill esquerre, després el seu node arrel i finalment el fill dret.
Travessia posterior a la comanda (esquerra-dreta-actual): Visiteu el node actual després de visitar tots els nodes dels subarbres esquerre i dret. Aquí, el recorregut és fill esquerre - fill dret - arrel. Vol dir que el fill esquerre ha travessat primer, després el fill dret i finalment el seu node arrel.

Algoritmes de cerca de l'amplada primer (BFS):

Travessament de l'ordre de nivell: Visiteu els nodes nivell per nivell i d'esquerra a dreta al mateix nivell. Aquí, el recorregut és a nivell. Vol dir que primer ha recorregut el nen més esquerre i després els altres nens del mateix nivell d'esquerra a dreta han recorregut.

3. Eliminació en arbre binari

Podem suprimir qualsevol node de l'arbre binari i reordenar els nodes després de la supressió per tornar a formar un arbre binari vàlid.

per què la interfície del marcador a Java

Algorisme per eliminar un node en un arbre binari:

Començant per l'arrel, cerqueu el node més profund i més a la dreta de l'arbre binari i el node que volem suprimir.
Substituïu les dades del node més profund a la dreta pel node que cal suprimir.
A continuació, suprimiu el node més profund més a la dreta.

4. Cercar en arbre binari

Podem cercar un element al node utilitzant qualsevol de les tècniques de recorregut.

Algorisme per cercar un node en un arbre binari:

Comenceu des del node arrel.
Comproveu si el valor del node actual és igual al valor objectiu.
Si el valor del node actual és igual al valor objectiu, aquest node és el node necessari.
En cas contrari, si el valor del node no és igual al valor objectiu, inicieu la cerca al fill esquerre i dret.
Si no trobem cap node el valor del qual sigui igual a l'objectiu, aleshores el valor no està present a l'arbre.

Operacions auxiliars en arbre binari

Trobar l'alçada de l'arbre
Trobeu el nivell d'un node en un arbre binari
Trobar la mida de tot l'arbre

Implementació de l'arbre binari

A continuació es mostra el codi per a la inserció, la supressió i el recorregut de l'arbre binari:

 #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->dades = val;  temp->esquerra = temp->dreta = NULL;  temperatura de retorn; } // Funció per inserir nodes Node* insert(Node* arrel, dades int) { // Si l'arbre està buit, el nou node es converteix en l'arrel if (arrel == NULL) { arrel = nouNode (dades);  retornar l'arrel;  } // Cua per recórrer l'arbre i trobar la posició per inserir el node Node* queue[100];  int davant = 0, posterior = 0;  cua[rear++] = arrel;  while (front != posterior) { Node* temp = cua[front++];  // Insereix el node com a fill esquerre del node pare if (temp->left == NULL) { temp->left = newNode(data);  trencar;  } // Si el fill esquerre no és nul, premeu-lo a la cua else queue[rear++] = temp->left;  // Insereix el node com a fill dret del node pare if (temp->right == NULL) { temp->right = newNode(data);  trencar;  } // Si el fill correcte no és nul, empènyer-lo a la cua else queue[rear++] = temp->right;  } retornar l'arrel; } /* Funció per eliminar el node més profund donat (d_node) a l'arbre binari */ void deletDeepest(Node* arrel, Node* d_node) { Node* queue[100];  int davant = 0, posterior = 0;  cua[rear++] = arrel;  // Fer un recorregut per ordre de nivell fins a l'últim node Node* temp;  while (davant != posterior) { temp = cua[front++];  if (temp == d_node) { temp = NULL;  lliure(d_node);  tornar;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  lliure(d_node);  tornar;  } else queue[rear++] = temp->dreta;  } if (temp->esquerra) { if (temp->esquerra == d_node) { temp->esquerra = NULL;  lliure(d_node);  tornar;  } else queue[rear++] = temp->esquerra;  } } } /* Funció per eliminar l'element de l'arbre binari */ Node* deletion(Node* arrel, clau int) { if (!root) return NULL;  if (arrel->esquerra == NULL && arrel->dreta == NULL) { if (arrel->dades == clau) retorna NULL;  sinó retornar l'arrel;  } Node* cua[100];  int davant = 0, posterior = 0;  cua[rear++] = arrel;  Node* temp;  Node* key_node = NULL;  // Fes un recorregut per ordre de nivell per trobar el node més profund (temp) i el node que cal suprimir (key_node) mentre (front != posterior) { temp = queue[front++];  if (temp->dades == clau) key_node = temp;  if (temp->esquerra) queue[rear++] = temp->esquerra;  if (temp->right) queue[rear++] = temp->right;  } if (key_node != NULL) { int x = temp->data;  key_node->data = x;  deletDeepest (arrel, temp);  } retornar l'arrel; } // Inorder travessa de l'arbre (Esquerra - Arrel - Dreta) void inorderTraversal(Node* arrel) { if (!root) return;  inorderTraversal(arrel->esquerra);  printf('%d', arrel->dades);  inorderTraversal(arrel->dreta); } // Preordena el recorregut de l'arbre (Arrel - Esquerra - Dreta) void preorderTraversal(Node* arrel) { if (!root) return;  printf('%d', arrel->dades);  preordena Traversal (arrel->esquerra);  preordena Traversal (arrel->dreta); } // Travessia de l'arbre posterior a l'ordre (Esquerra - Dreta - Arrel) void postorderTraversal(Node* arrel) { if (arrel == NULL) retorn;  postorderTraversal(arrel->esquerra);  postorderTraversal(arrel->dreta);  printf('%d', arrel->dades); } // Funció per al recorregut de l'arbre d'ordre de nivell void levelorderTraversal(Node* arrel) { if (root == NULL) return;  // Cua per a l'ordre de nivell Node* queue[100];  int davant = 0, posterior = 0;  cua[rear++] = arrel;  while (front != posterior) { Node* temp = cua[front++];  printf('%d', temp->dades);  // Empènyer el fill esquerre a la cua si (temp->esquerra) queue[rear++] = temp->esquerra;  // Empènyer el fill dret a la cua si (temp->right) queue[rear++] = temp->right;  } } /* Funció de controlador per comprovar l'algorisme anterior. */ int main() { Node* arrel = NULL;  // Inserció de nodes arrel = insert(arrel, 10);  arrel = inserir (arrel, 20);  arrel = inserir (arrel, 30);  arrel = inserir (arrel, 40);  printf('Recorreu la comanda prèvia: ');  preordena Traversal (arrel);  printf('
Trasversal en ordre: ');  inorderTraversal(arrel);  printf('
Travessament de Postorder: ');  postordeTraversal(arrel);  printf('
Recorregut per ordre de nivell: ');  levelorderTraversal (arrel);  // Esborra el node amb dades = 20 arrel = eliminació (arrel, 20);  printf('
Trascorregut en ordre després de la supressió: ');  inorderTraversal(arrel);  retorn 0; }>>>Javaq = new LinkedList();  q.oferta(arrel);  // Fes un recorregut de l'ordre de nivell fins a l'últim node Node temp;  mentre que (!q.isEmpty()) { temp = q.poll();  if (temp == d_node) { temp = nul;  d_node = nul;  tornar;  } if (temp.right != nul) { if (temp.right == d_node) { temp.right = nul;  d_node = nul;  tornar;  } else q.offer(temp.right);  } if (temp.esquerra != nul) { if (temp.esquerra == d_node) { temp.esquerra = nul;  d_node = nul;  tornar;  } else q.offer(temp.esquerra);  } } } /* funció per esborrar l'element de l'arbre binari */ public static Node deletion (arrel del node, clau int) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == clau) retorna null;  sinó retornar l'arrel;  } Cuaq = new LinkedList();  q.oferta(arrel);  Node temp = nou Node(0);  Node key_node = null;  // Fes un recorregut per ordre de nivell per trobar // el node (temp) i el node més profunds que s'han de suprimir (key_node) mentre (!q.isEmpty()) { temp = q.poll();  if (temp.data == clau) key_node = temp;  if (temp.esquerra != nul) q.offer(temp.esquerra);  if (temp.right != nul) q.offer(temp.right);  } if (key_node != null) { int x = temp.data;  key_node.data = x;  deletDeepest (arrel, temp);  } retornar l'arrel;  } // Inorder travessa de l'arbre (Esquerra - Arrel - Dreta) public static void inorderTraversal (Arrel del node) { if (arrel == null) retorn;  inorderTraversal(arrel.esquerra);  System.out.print(root.data + ' ');  inorderTraversal(arrel.dreta);  } // Preordena el recorregut de l'arbre (Arrel - Esquerra - Dreta) public static void preorderTraversal (Arrel del node) { if (arrel == null) retorn;  System.out.print(root.data + ' ');  preorderTraversal (arrel.esquerra);  preorderTraversal (arrel.dreta);  } // Travessia de l'arbre posterior a l'ordre (esquerra - dreta - arrel) public static void postorderTraversal (arrel del node) { if (arrel == null) retorn;  postorderTraversal(arrel.esquerra);  postorderTraversal(arrel.dreta);  System.out.print(root.data + ' ');  } // Funció per a la travessa de l'arbre d'ordre de nivell public static void levelorderTraversal(Arrel del node) { if (arrel == null) retorn;  // Cua per a la travessa de l'ordre de nivell Cuaq = new LinkedList();  q.oferta(arrel);  while (!q.isEmpty()) { Node temp = q.poll();  System.out.print (dades temp. + ' ');  // Empènyer el fill esquerre a la cua si (temp.left != null) q.offer(temp.left);  // Empènyer el fill dret a la cua si (temp.right != null) q.offer(temp.right);  } } /* Funció de controlador per comprovar l'algorisme anterior. */ public static void main(String[] args) { Arrel del node = nul;  // Inserció de nodes arrel = insert(arrel, 10);  arrel = inserir (arrel, 20);  arrel = inserir (arrel, 30);  arrel = inserir (arrel, 40);  System.out.print('Recorreu la comanda prèvia: ');  preordena Traversal (arrel);  System.out.print('
Trasversal en ordre: ');  inorderTraversal(arrel);  System.out.print('
Trasversal de Postorde: ');  postordeTraversal(arrel);  System.out.print('
Recorregut d'ordre de nivell: ');  levelorderTraversal (arrel);  // Esborra el node amb dades = 20 arrel = eliminació (arrel, 20);  System.out.print('
Recorregut en ordre després de la supressió: ');  inorderTraversal(arrel);  } }>>>Python

 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 = cua nova();  q.Enqueue(arrel);  while (q.Count != 0) { Node temp = q.Dequeue();  // Insereix el node com a fill esquerre del node pare if (temp.left == null) { temp.left = new Node(data);  trencar;  } // Si el fill esquerre no és nul, premeu-lo a la cua sinó q.Enqueue(temp.left);  // Insereix el node com a fill dret del node pare si (temp.right == null) { temp.right = nou Node (dades);  trencar;  } // Si el fill dret no és nul, introduïu-lo a la cua sinó q.Enqueue(temp.right);  } retornar l'arrel;  } /* funció per esborrar el node més profund donat (d_node) a l'arbre binari */ public static void DeleteDeepest(Node arrel, Node d_node) { Cuaq = cua nova();  q.Enqueue(arrel);  // Fes un recorregut de l'ordre de nivell fins a l'últim node Node temp;  mentre que (q.Compte != 0) { temp = q.Descua ();  if (temp == d_node) { temp = nul;  d_node = nul;  tornar;  } if (temp.right != nul) { if (temp.right == d_node) { temp.right = nul;  d_node = nul;  tornar;  } else q.Enqueue(temp.right);  } if (temp.esquerra != nul) { if (temp.esquerra == d_node) { temp.esquerra = nul;  d_node = nul;  tornar;  } else q.Enqueue(temp.left);  } } } /* funció per eliminar l'element de l'arbre binari */ public static Node Deletion (arrel del node, clau int) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == clau) retorna null;  sinó retornar l'arrel;  } Cuaq = cua nova();  q.Enqueue(arrel);  Node temp = nou Node(0);  Node key_node = null;  // Fes un recorregut per ordre de nivell per trobar el node més profund (temp) i el node que cal suprimir (key_node) mentre (q.Count != 0) { temp = q.Dequeue();  if (temp.data == clau) key_node = temp;  if (temp.esquerra != nul) q.Enqueue(temp.esquerra);  if (temp.right != nul) q.Enqueue(temp.right);  } if (key_node != null) { int x = temp.data;  key_node.data = x;  DeleteDeepest (arrel, temp);  } retornar l'arrel;  } // Travessa de l'arbre en ordre (Esquerra - Arrel - Dreta) public static void InorderTraversal (Arrel del node) { if (arrel == null) retorn;  InorderTraversal(arrel.esquerra);  Console.Write(root.data + ' ');  InorderTraversal(arrel.dreta);  } // Preordena el recorregut de l'arbre (Arrel - Esquerra - Dreta) public static void PreorderTraversal (Arrel del node) { if (arrel == null) retorn;  Console.Write(root.data + ' ');  Preordena Traversal (arrel.esquerra);  Preordena Traversal (arrel.dreta);  } // Travessia de l'arbre de l'ordre posterior (esquerra - dreta - arrel) public static void PostorderTraversal (arrel del node) { if (arrel == null) retorn;  PostorderTraversal (arrel.esquerra);  PostorderTraversal (arrel.dreta);  Console.Write(root.data + ' ');  } // Funció per a la travessa de l'arbre d'ordre de nivell public static void LevellorderTraversal (arrel del node) { if (root == null) return;  // Cua per a la travessa de l'ordre de nivell Cuaq = cua nova();  q.Enqueue(arrel);  while (q.Count != 0) { Node temp = q.Dequeue();  Console.Write(temp.data + ' ');  // Empènyer el fill esquerre a la cua si (temp.left != null) q.Enqueue(temp.left);  // Empènyer el fill dret a la cua si (temp.right != null) q.Enqueue(temp.right);  } } /* Funció de controlador per comprovar l'algorisme anterior. */ public static void Principal(string[] args) { Arrel del node = nul;  // Inserció de nodes arrel = Insert(arrel, 10);  arrel = Insereix (arrel, 20);  arrel = Insereix (arrel, 30);  arrel = Insereix (arrel, 40);  Console.Write('Recorreu la comanda prèvia: ');  Preordena Traversal (arrel);  Console.Write('
Trasversal en ordre: ');  InorderTraversal (arrel);  Console.Write('
Trasversal de Postorde: ');  PostorderTraversal (arrel);  Console.Write('
Travessa d'ordre de nivell: ');  LevellorderTraversal (arrel);  // Esborra el node amb dades = 20 root = Deletion(root, 20);  Console.Write('
Recorregut en ordre després de la supressió: ');  InorderTraversal (arrel);  } }>>>Javascript

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(arrel);  while (!q.empty()) { Node* temp = q.front();  q.pop();  // Insereix el node com a fill esquerre del node pare si (temp->esquerra == NULL) { temp->esquerra = nou Node (dades);  trencar;  } // Si el fill esquerre no és nul, envieu-lo a la // cua sinó q.push(temp->esquerra);  // Insereix el node com a fill dret del node pare si (temp->right == NULL) { temp->right = nou Node (dades);  trencar;  } // Si el fill correcte no és nul, introduïu-lo a la // cua, sinó q.push(temp->right);  } retornar l'arrel; } /* funció per eliminar el node més profund donat (d_node) a l'arbre binari */ void deletDeepest(Node* arrel, Node* d_node) { cuaq;  q.push(arrel);  // Fer un recorregut per ordre de nivell fins a l'últim node Node* temp;  mentre que (!q.buit()) { temp = q.front();  q.pop();  if (temp == d_node) { temp = NULL;  suprimir (d_node);  tornar;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  suprimir (d_node);  tornar;  } else q.push(temp->right);  } if (temp->esquerra) { if (temp->esquerra == d_node) { temp->esquerra = NULL;  suprimir (d_node);  tornar;  } else q.push(temp->esquerra);  } } } /* funció per eliminar l'element de l'arbre binari */ Node* deletion(Node* arrel, clau int) { if (!root) return NULL;  if (arrel->esquerra == NULL && arrel->dreta == NULL) { if (arrel->dades == clau) retorna NULL;  sinó retornar l'arrel;  } cuaq;  q.push(arrel);  Node* temp;  Node* key_node = NULL;  // Fes un recorregut per ordre de nivell per trobar // el node(temp) i el node més profunds que cal suprimir (key_node) mentre (!q.empty()) { temp = q.front();  q.pop();  if (temp->dades == clau) key_node = temp;  if (temp->esquerra) q.push(temp->esquerra);  if (temp->right) q.push(temp->right);  } if (key_node != NULL) { int x = temp->data;  key_node->data = x;  deletDeepest (arrel, temp);  } retornar l'arrel; } // Inorder travessa de l'arbre (Esquerra - Arrel - Dreta) void inorderTraversal(Node* arrel) { if (!arrel) retorn;  inorderTraversal(arrel->esquerra);  cout<< root->dades<< ' ';  inorderTraversal(root->dret); } // Preordena el recorregut de l'arbre (Arrel - Esquerra - Dreta) void preorderTraversal(Node* arrel) { if (!root) return;  cout<< root->dades<< ' ';  preorderTraversal(root->esquerra);  preordena Traversal (arrel->dreta); } // Travessia de l'arbre posterior a l'ordre (esquerra - dreta - arrel) void postorderTraversal(Node* arrel) { if (arrel == NULL) retorn;  postorderTraversal(arrel->esquerra);  postordreTraversal(arrel->dreta);  cout<< root->dades<< ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) {  if (root == NULL)  return;  // Queue for level order traversal  queueq;  q.push(arrel);  while (!q.empty()) { Node* temp = q.front();  q.pop();  cout<< temp->dades<< ' ';  // Push left child in the queue  if (temp->esquerra) q.push(temp->esquerra);  // Empènyer el fill dret a la cua if (temp->right) q.push(temp->right);  } } /* Funció de controlador per comprovar l'algorisme anterior. */ int main() { Node* arrel = NULL;  // Inserció de nodes arrel = insert(arrel, 10);  arrel = inserir (arrel, 20);  arrel = inserir (arrel, 30);  arrel = inserir (arrel, 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); }>

Sortida

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>

Anàlisi de complexitat d'operacions d'arbre binari

Operacions	Complexitat temporal	Complexitat espacial
Inserció	O(N)	O(N)
Reserva Traversal	O(N)	O(N)
Travessia de l'ordre algorisme per a la cerca binària	O(N)	O(N)
Travessia postal	O(N)	O(N)
Travessament de l'ordre de nivell	O(N)	O(N)
Supressió	O(N)	O(N)
Buscant	O(N)	O(N)

Podem utilitzar Morris Traversal per recórrer tots els nodes de l'arbre binari en temps O(1).

nombre a cadena java

Avantatges de l'arbre binari

Cerca eficient: Els arbres binaris són eficients a l'hora de cercar un element específic, ja que cada node té com a màxim dos nodes fills, permetent Eficient de memòria: Els arbres binaris requereixen menys memòria en comparació amb altres estructures de dades d'arbre, per tant són eficients en memòria.
Els arbres binaris són relativament fàcils d'implementar i d'entendre, ja que cada node té com a màxim dos fills, fill esquerre i fill dret.

Inconvenients de l'arbre binari

Aplicacions de l'arbre binari

Es pot utilitzar l'arbre binari representen dades jeràrquiques .
S'utilitzen arbres de codificació Huffman algorismes de compressió de dades .
Cua de prioritats és una altra aplicació de l'arbre binari que s'utilitza per cercar el màxim o el mínim en complexitat temporal O(1).
Útil per indexar segmentats a la base de dades és útil per emmagatzemar la memòria cau al sistema,
Els arbres binaris es poden utilitzar per implementar arbres de decisió, un tipus d'algorisme d'aprenentatge automàtic utilitzat per a la classificació i l'anàlisi de regressió.

Preguntes freqüents sobre l'arbre binari

1. Què és un arbre binari?

Un arbre binari és una estructura de dades no lineal que consta de nodes, on cada node té com a màxim dos fills (fill esquerre i fill dret).

2. Quins són els tipus d'arbres binaris?

Els arbres binaris es poden classificar en diversos tipus, inclosos arbres binaris complets, arbres binaris complets, arbres binaris perfectes, arbres binaris equilibrats (com ara arbres AVL i arbres vermell-negre) i arbres binaris degenerats (o patològics).

3. Quina és l'alçada d'un arbre binari?

L'alçada d'un arbre binari és la longitud del camí més llarg des del node arrel fins al node fulla. Representa el nombre d'arestes en el camí més llarg des del node arrel fins a un node fulla.

4. Quina és la profunditat d'un node en un arbre binari?

La profunditat d'un node en un arbre binari és la longitud del camí des del node arrel fins a aquest node en particular. La profunditat del node arrel és 0.

5. Com es realitza el recorregut d'arbres en un arbre binari?

La travessa d'arbres en un arbre binari es pot fer de diferents maneres: travessa en ordre, travessa prèvia a la comanda, travessa posterior a la comanda i travessa en ordre de nivell (també coneguda com a travessament de l'amplada primer).

6. Què és un recorregut en ordre en arbre binari?

A Inorder traversal, els nodes es visiten recursivament en aquest ordre: fill esquerre, arrel, fill dret. Aquest recorregut fa que els nodes es visitin en ordre no decreixent en un arbre de cerca binari.

7. Què és un recorregut de preordre a l'arbre binari?

En el recorregut de preordre, els nodes es visiten recursivament en aquest ordre: arrel, fill esquerre, fill dret. Aquest recorregut fa que el node arrel sigui el primer node que es visita.

8. Què és un recorregut de Postorder en arbre binari?

En el recorregut de Postorder, els nodes es visiten recursivament en aquest ordre: fill esquerre, fill dret i arrel. Aquest recorregut fa que el node arrel sigui l'últim node visitat.

9. Quina diferència hi ha entre un arbre binari i un arbre de cerca binari?

Un arbre binari és una estructura de dades jeràrquica on cada node té com a màxim dos fills, mentre que un arbre de cerca binari és un tipus d'arbre binari en què el fill esquerre d'un node conté valors inferiors al valor del node i el fill dret conté valors. superior al valor del node.

10. Què és un arbre binari equilibrat?

Un arbre binari equilibrat és un arbre binari en el qual l'alçada dels subarbres esquerre i dret de cada node difereix com a màxim en un. Els arbres equilibrats ajuden a mantenir operacions eficients com la cerca, la inserció i la supressió amb complexitats temporals properes a O(log n).

Conclusió:

L'arbre és una estructura de dades jeràrquica. Els principals usos dels arbres inclouen el manteniment de dades jeràrquiques, l'accés moderat i les operacions d'inserció/eliminació. Els arbres binaris són casos especials d'arbre on cada node té com a màxim dos fills.

Articles relacionats:

Propietats de l'arbre binari
Tipus d'arbre binari

TechCodeview

Introducció a l'arbre binari - Estructura de dades i tutorials d'algorisme