ÚVOD DO BINÁRNEHO STROMU – ŠTRUKTÚRA ÚDAJOV A NÁVODY NA ALGORITMY

Binárny strom je a nelineárnu dátovú štruktúru kde každý uzol má najviac dve deti. V tomto článku pokryjeme všetky základy binárneho stromu, operácie s binárnym stromom, jeho implementáciu, výhody a nevýhody, ktoré vám pomôžu vyriešiť všetky problémy založené na binárnom strome.

Obsah

Čo je binárny strom?
Reprezentácia binárneho stromu
Typy binárnych stromov
Operácie na binárnom strome
Pomocné operácie na binárnom strome
Implementácia binárneho stromu
Analýza zložitosti operácií binárnych stromov
Výhody binárneho stromu
Nevýhody binárneho stromu
Aplikácie binárneho stromu
Často kladené otázky o binárnom strome

Čo je binárny strom?

Binárny strom je a stromová dátová štruktúra (nelineárna) v ktorom môže mať každý uzol najviac dve deti ktoré sa označujú ako ľavé dieťa a správne dieťa .

Najvyšší uzol v binárnom strome sa nazýva koreň a volajú sa najspodnejšie uzly listy . Binárny strom si možno predstaviť ako hierarchickú štruktúru s koreňom navrchu a listami naspodku.

odhlásiť sa z účtu Google v systéme Android

Reprezentácia binárneho stromu

Každý uzol v binárnom strome má tri časti:

Údaje
Ukazovateľ na ľavé dieťa
Ukazovateľ na správne dieťa

Nižšie je znázornenie uzla binárneho stromu v rôznych jazykoch:

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

Typy binárnych stromov

Binárny strom možno klasifikovať do viacerých typov na základe viacerých faktorov:

Na základe Počet detí
- Úplný binárny strom
- Degenerovaný binárny strom
- Šikmé binárne stromy
Na základe dokončenia úrovní
- Kompletný binárny strom
- Perfektný binárny strom
- Vyvážený binárny strom
Na základe hodnôt uzlov:
- Binárny vyhľadávací strom
- Strom AVL
- Červený čierny strom
- B strom
- Strom B+
- Segmentový strom

Operácie na binárnom strome

1. Vloženie do binárneho stromu

Uzol môžeme vložiť kamkoľvek do binárneho stromu vložením uzla ako ľavého alebo pravého potomka ľubovoľného uzla alebo tak, že uzol urobíme koreňom stromu.

Algoritmus na vloženie uzla do binárneho stromu:

Skontrolujte, či sa v binárnom strome nachádza uzol, ktorému chýba ľavé dieťa. Ak takýto uzol existuje, vložte nový uzol ako jeho ľavý potomok.
Skontrolujte, či je v binárnom strome uzol, ktorému chýba pravé dieťa. Ak takýto uzol existuje, vložte nový uzol ako jeho pravý potomok.
Ak nenájdeme žiadny uzol s chýbajúcim ľavým alebo pravým potomkom, nájdite uzol, v ktorom chýbajú obe deti, a vložte uzol ako jeho ľavé alebo pravé dieťa.

2. Prechod binárneho stromu

Prechod binárneho stromu zahŕňa návštevu všetkých uzlov binárneho stromu. Algoritmy prechodu cez strom možno rozdeliť do dvoch kategórií:

Algoritmy hĺbkového vyhľadávania (DFS).
Algoritmy BFS (Breadth-First Search).

Algoritmy hĺbkového vyhľadávania (DFS):

Prechod predobjednávky (aktuálne-vľavo-vpravo): Pred návštevou akéhokoľvek uzla v ľavom alebo pravom podstrome navštívte aktuálny uzol. Tu je prechod koreň – ľavé dieťa – pravé dieťa. To znamená, že najprv sa prejde koreňový uzol, potom jeho ľavé dieťa a nakoniec pravé dieťa.
Inorder Traversal (ľavý-prúd-pravý): Navštívte aktuálny uzol po návšteve všetkých uzlov v ľavom podstrome, ale pred návštevou ktoréhokoľvek uzla v pravom podstrome. Tu je prechod ľavé dieťa – koreň – pravé dieťa. To znamená, že najprv prejde ľavé dieťa, potom jeho koreňový uzol a nakoniec pravé dieťa.
Postorder Traversal (ľavo-pravý-prúd): Navštívte aktuálny uzol po návšteve všetkých uzlov ľavého a pravého podstromu. Tu je prechod ľavé dieťa – pravé dieťa – koreň. To znamená, že najprv prešlo ľavé dieťa, potom pravé dieťa a nakoniec jeho koreňový uzol.

Algoritmy BFS (Breadth-First Search):

Prechod na úrovni objednávky: Navštívte uzly po úrovni a zľava doprava na rovnakej úrovni. Tu je prechod po rovine. Znamená to, že najľavejšie dieťa prešlo ako prvé a potom ostatné deti rovnakej úrovne zľava doprava prešli.

3. Vymazanie v binárnom strome

Môžeme vymazať ktorýkoľvek uzol v binárnom strome a po odstránení zmeniť usporiadanie uzlov tak, aby opäť vytvorili platný binárny strom.

Algoritmus na odstránenie uzla v binárnom strome:

Začnite od koreňa, nájdite najhlbší a najpravejší uzol v binárnom strome a uzol, ktorý chceme vymazať.
Nahraďte údaje uzla najhlbšieho vpravo uzlom, ktorý sa má odstrániť.
Potom odstráňte najhlbší uzol úplne vpravo.

4. Vyhľadávanie v binárnom strome

Prvok v uzle môžeme vyhľadať pomocou ktorejkoľvek z techník prechodu.

verzie pre Android

Algoritmus na vyhľadávanie uzla v binárnom strome:

Začnite od koreňového uzla.
Skontrolujte, či sa hodnota aktuálneho uzla rovná cieľovej hodnote.
Ak sa hodnota aktuálneho uzla rovná cieľovej hodnote, potom je tento uzol požadovaným uzlom.
V opačnom prípade, ak sa hodnota uzla nerovná cieľovej hodnote, začnite vyhľadávanie v ľavom a pravom potomkovi.
Ak nenájdeme žiadny uzol, ktorého hodnota sa rovná cieľovej, hodnota sa v strome nenachádza.

Pomocné operácie na binárnom strome

Zistenie výšky stromu
Nájdite úroveň uzla v binárnom strome
Zistenie veľkosti celého stromu

Implementácia binárneho stromu

Nižšie je uvedený kód na vloženie, vymazanie a prechod binárneho stromu:

 #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->údaje = val;  temp->left = temp->right = NULL;  návratová teplota; } // Funkcia na vloženie uzlov Node* insert(Node* root, int data) { // Ak je strom prázdny, nový uzol sa stane koreňom if (root == NULL) { root = newNode(data);  vrátiť koreň;  } // Fronta na prechod stromom a nájdenie pozície na vloženie uzla Node* queue[100];  vnútorné predné = 0, zadné = 0;  fronta[zadna++] = root;  while (predný != zadný) { Node* temp = front[front++];  // Vloženie uzla ako ľavého potomka nadradeného uzla if (temp->left == NULL) { temp->left = newNode(data);  prestávka;  } // Ak ľavý potomok nie je null, posuňte ho do frontu else queue[rear++] = temp->left;  // Vloženie uzla ako pravého potomka nadradeného uzla if (temp->right == NULL) { temp->right = newNode(data);  prestávka;  } // Ak pravý potomok nie je null, posuňte ho do frontu else queue[rear++] = temp->right;  } return root; } /* Funkcia na zmazanie daného najhlbšieho uzla (d_node) v binárnom strome */ void deletHlboký(Node* root, Node* d_node) { Node* queue[100];  vnútorné predné = 0, zadné = 0;  fronta[zadna++] = root;  // Vykonanie prechodu poradia úrovne až po posledný uzol Node* temp;  while (predné != zadné) { temp = front[front++];  if (temp == d_node) { temp = NULL;  free(d_uzol);  návrat;  } if (temp->vpravo) { if (temp->vpravo == d_uzol) { temp->vpravo = NULL;  free(d_uzol);  návrat;  } else queue[zadna++] = temp->vpravo;  } if (temp->left) { if (temp->left == d_node) { temp->left = NULL;  free(d_uzol);  návrat;  } else queue[zadna++] = temp->left;  } } } /* Funkcia na vymazanie elementu v binárnom strome */ Node* vymazanie (Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL;  inak vrátiť koreň;  } Node* fronta[100];  vnútorné predné = 0, zadné = 0;  fronta[zadna++] = root;  Teplota uzla*;  Node* key_node = NULL;  // Vykonajte prechod podľa poradia úrovní, aby ste našli najhlbší uzol (temp) a uzol, ktorý chcete odstrániť (key_node) while (front != zadný) { temp = queue[front++];  if (temp->data == key) key_node = temp;  if (temp->left) queue[zadny++] = temp->left;  if (temp->vpravo) fronta[zadna++] = temp->vpravo;  } if (key_node != NULL) { int x = temp->data;  key_node->data = x;  deletDeepest(root, temp);  } return root; } // Prechod cez strom (vľavo - koreň - vpravo) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(root->left);  printf('%d ', root->data);  inorderTraversal(root->right); } // Prechod cez strom predobjednávky (koreň - vľavo - vpravo) void preorderTraversal(Node* root) { if (!root) return;  printf('%d ', root->data);  preorderTraversal(root->left);  preorderTraversal(root->right); } // Prechod stromom postordera (vľavo - vpravo - koreň) void postorderTraversal(Node* root) { if (koreň == NULL) return;  postorderTraversal(root->left);  postorderTraversal(root->right);  printf('%d ', root->data); } // Funkcia pre prechod stromom poradia úrovní void levelorderTraversal(Node* root) { if (root == NULL) return;  // Fronta na prechod poradia úrovne Node* queue[100];  vnútorné predné = 0, zadné = 0;  fronta[zadna++] = root;  while (predný != zadný) { Node* temp = front[front++];  printf('%d ', temp->data);  // Push ľavého potomka vo fronte if (temp->left) queue[rear++] = temp->left;  // Push right child vo fronte if (temp->right) queue[rear++] = temp->right;  } } /* Funkcia ovládača na kontrolu vyššie uvedeného algoritmu. */ int main() { Uzol* root = NULL;  // Vloženie uzlov root = insert(root, 10);  root = insert(root, 20);  root = insert(root, 30);  root = insert(root, 40);  printf('Prechod predobjednávky: ');  preorderTraversal(root);  printf('
Prechod poradia: ');  inorderTraversal(root);  printf('
Prechod postorderom: ');  postorderTraversal(root);  printf('
Prechod poradia na úrovni: ');  levelorderTraversal(root);  // Vymazanie uzla s datami = 20 root = deletion(root, 20);  printf('
Prechod poradia po vymazani: ');  inorderTraversal(root);  návrat 0; }>

Java

 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 = new LinkedList();  q.offer(koreň);  while (!q.isEmpty()) { Node temp = q.poll();  // Vloženie uzla ako ľavého potomka nadradeného uzla if (temp.left == null) { temp.left = new Node(data);  prestávka;  } // Ak ľavé dieťa nemá hodnotu null, zaradí ho do // frontu else q.offer(temp.left);  // Vloženie uzla ako pravého potomka nadradeného uzla if (temp.right == null) { temp.right = new Node(data);  prestávka;  } // Ak pravý potomok nie je null, pošli ho do // frontu else q.offer(temp.right);  } return root;  } /* funkcia na vymazanie daného najhlbšieho uzla (d_node) v binárnom strome */ public static void deletDeepest(koreň uzla, uzol d_node) { Queueq = new LinkedList();  q.offer(koreň);  // Vykonanie prechodu poradia úrovne do posledného uzla Node temp;  while (!q.isEmpty()) { temp = q.poll();  if (temp == d_node) { temp = null;  d_node = null;  návrat;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = null;  návrat;  } else q.offer(temp.right);  } if (ľavá temp != null) { if (ľavá temp == d_uzol) { ľavá temp = null;  d_node = null;  návrat;  } else q.offer(temp.left);  } } } /* funkcia na vymazanie prvku v binárnom strome */ public static Odstránenie uzla (koreň uzla, kľúč int) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == kľúč) return null;  inak vrátiť koreň;  } Poradieq = new LinkedList();  q.offer(koreň);  Teplota uzla = novy uzol(0);  Node key_node = null;  // Vykonajte prechod na úrovni poradia, aby ste našli najhlbší // node(temp) a uzol, ktorý sa má odstrániť (key_node) while (!q.isEmpty()) { temp = q.poll();  if (temp.data == kľúč) key_node = temp;  if (temp.left != null) q.offer(temp.left);  if (temp.right != null) q.offer(temp.right);  } if (key_node != null) { int x = temp.data;  key_node.data = x;  deletDeepest(root, temp);  } return root;  } // Prechádzanie cez strom (vľavo - koreň - vpravo) public static void inorderTraversal(koreň uzla) { if (koreň == null) return;  inorderTraversal(root.left);  System.out.print(root.data + ' ');  inorderTraversal(root.right);  } // Prechod cez strom predobjednávky (koreň - vľavo - vpravo) public static void preorderTraversal(koreň uzla) { if (root == null) return;  System.out.print(root.data + ' ');  preorderTraversal(root.left);  preorderTraversal(root.right);  } // Prechod stromom postordera (vľavo - vpravo - koreň) public static void postorderTraversal(koreň uzla) { if (koreň == null) return;  postorderTraversal(root.left);  postorderTraversal(root.right);  System.out.print(root.data + ' ');  } // Funkcia pre prechod stromom poradia úrovní public static void levelorderTraversal(koreň uzla) { if (koreň == null) return;  // Fronta na prechod poradia úrovníq = new LinkedList();  q.offer(koreň);  while (!q.isEmpty()) { Node temp = q.poll();  System.out.print(temp.data + ' ');  // Zatlačí ľavého potomka vo fronte if (temp.left != null) q.offer(temp.left);  // Vložiť pravého potomka do frontu if (temp.right != null) q.offer(temp.right);  } } /* Funkcia ovládača na kontrolu vyššie uvedeného algoritmu. */ public static void main(String[] args) { Koreň uzla = null;  // Vloženie uzlov root = insert(root, 10);  root = insert(root, 20);  root = insert(root, 30);  root = insert(root, 40);  System.out.print('Prechod predobjednávky: ');  preorderTraversal(root);  System.out.print('
Poradenie: ');  inorderTraversal(root);  System.out.print('
Postorder traversal: ');  postorderTraversal(root);  System.out.print('
Prechod objednávky na úrovni: ');  levelorderTraversal(root);  // Vymazanie uzla s datami = 20 root = deletion(root, 20);  System.out.print('
Poradenie po vymazaní: ');  inorderTraversal(root);  } }>

Python

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

 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 = nový front();  q.Enqueue(root);  while (q.Count != 0) { Teplota uzla = q.Dequeue();  // Vloženie uzla ako ľavého potomka nadradeného uzla if (temp.left == null) { temp.left = new Node(data);  prestávka;  } // Ak ľavý potomok nie je null, zaradí ho do frontu else q.Enqueue(temp.left);  // Vloženie uzla ako pravého potomka nadradeného uzla if (temp.right == null) { temp.right = new Node(data);  prestávka;  } // Ak pravý potomok nie je null, zaradí ho do frontu else q.Enqueue(temp.right);  } return root;  } /* funkcia na vymazanie daného najhlbšieho uzla (d_node) v binárnom strome */ public static void DeleteDeepest(Node root, Node d_node) { Queueq = nový front();  q.Enqueue(root);  // Vykonanie prechodu poradia úrovne do posledného uzla Node temp;  while (q.Count != 0) { temp = q.Dequeue();  if (temp == d_node) { temp = null;  d_node = null;  návrat;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = null;  návrat;  } else q.Enqueue(temp.right);  } if (ľavá temp != null) { if (ľavá temp == d_uzol) { ľavá temp = null;  d_node = null;  návrat;  } else q.Enqueue(temp.left);  } } } /* funkcia na vymazanie prvku v binárnom strome */ public static Vymazanie uzla(koreň uzla, kľúč int) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == kľúč) return null;  inak vrátiť koreň;  } Poradieq = nový front();  q.Enqueue(root);  Teplota uzla = novy uzol(0);  Node key_node = null;  // Vykonajte prechod na úrovni poradia, aby ste našli najhlbší uzol (temp) a uzol, ktorý sa má odstrániť (key_node) while (q.Count != 0) { temp = q.Dequeue();  if (temp.data == kľúč) key_node = temp;  if (temp.left != null) q.Enqueue(temp.left);  if (temp.right != null) q.Enqueue(temp.right);  } if (key_node != null) { int x = temp.data;  key_node.data = x;  DeleteDeepest(root, temp);  } return root;  } // Prechod cez strom (vľavo - koreň - vpravo) public static void Prechod uzla (koreň uzla) { if (koreň == null) return;  InorderTraversal(root.left);  Console.Write(root.data + ' ');  InorderTraversal(root.right);  } // Prechod stromu predobjednávky (koreň - vľavo - vpravo) public static void Prechod predobjednávky(koreň uzla) { if (root == null) return;  Console.Write(root.data + ' ');  PreorderTraversal(root.left);  PreorderTraversal(root.right);  } // Prechod stromom postorderu (vľavo - vpravo - koreň) public static void PostorderTraversal(koreň uzla) { if (root == null) return;  PostorderTraversal(root.left);  PostorderTraversal(root.right);  Console.Write(root.data + ' ');  } // Funkcia pre prechod stromom poradia úrovní public static void LevelorderTraversal(koreň uzla) { if (koreň == null) return;  // Fronta na prechod poradia úrovníq = nový front();  q.Enqueue(root);  while (q.Count != 0) { Teplota uzla = q.Dequeue();  Console.Write(temp.data + ' ');  // Zatlačí ľavého potomka vo fronte if (temp.left != null) q.Enqueue(temp.left);  // Vložiť pravého potomka do frontu if (temp.right != null) q.Enqueue(temp.right);  } } /* Funkcia ovládača na kontrolu vyššie uvedeného algoritmu. */ public static void Main(string[] args) { Koreň uzla = null;  // Vloženie uzlov root = Insert(root, 10);  root = Insert(root, 20);  root = Insert(root, 30);  root = Insert(root, 40);  Console.Write('Prechod predobjednávky: ');  PreorderTraversal(root);  Console.Write('
Prechádzanie po poradí: ');  InorderTraversal(root);  Console.Write('
Prechádzanie postorderom: ');  PostorderTraversal(root);  Console.Write('
Prechod objednávky úrovne: ');  LevelorderTraversal(root);  // Vymazanie uzla s datami = 20 root = Deletion(root, 20);  Console.Write('
Prechádzanie poradia po vymazaní: ');  InorderTraversal(root);  } }>

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(koreň);  while (!q.empty()) { Node* temp = q.front();  q.pop();  // Vloženie uzla ako ľavého potomka nadradeného uzla if (temp->left == NULL) { temp->left = new Node(data);  prestávka;  } // Ak ľavé dieťa nie je null, pošlite ho do // frontu else q.push(temp->left);  // Vloženie uzla ako pravého potomka nadradeného uzla if (temp->right == NULL) { temp->right = new Node(data);  prestávka;  } // Ak pravý potomok nie je null, pošli ho do // frontu else q.push(temp->right);  } return root; } /* funkcia na vymazanie daného najhlbšieho uzla (d_node) v binárnom strome */ void deletDeepest(Node* root, Node* d_node) { queueq;  q.push(koreň);  // Vykonanie prechodu poradia úrovne až po posledný uzol Node* temp;  while (!q.empty()) { temp = q.front();  q.pop();  if (temp == d_node) { temp = NULL;  delete (d_node);  návrat;  } if (temp->vpravo) { if (temp->vpravo == d_uzol) { temp->vpravo = NULL;  delete (d_node);  návrat;  } else q.push(temp->vpravo);  } if (temp->left) { if (temp->left == d_node) { temp->left = NULL;  delete (d_node);  návrat;  } else q.push(temp->left);  } } } /* funkcia na vymazanie elementu v binárnom strome */ Node* vymazanie(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL;  inak vrátiť koreň;  } frontaq;  q.push(koreň);  Teplota uzla*;  Node* key_node = NULL;  // Vykonajte prechod podľa poradia úrovní, aby ste našli najhlbší // node(temp) a uzol, ktorý sa má odstrániť (key_node) while (!q.empty()) { temp = q.front();  q.pop();  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) { int x = temp->data;  key_node->data = x;  deletDeepest(root, temp);  } return root; } // Prechod cez strom (vľavo - koreň - vpravo) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(root->left);  cout<< root->údajov<< ' ';  inorderTraversal(root->správny); } // Prechod cez strom predobjednávky (koreň - vľavo - vpravo) void preorderTraversal(Node* root) { if (!root) return;  cout<< root->údajov<< ' ';  preorderTraversal(root->vľavo);  preorderTraversal(root->right); } // Prechod stromom postordera (vľavo - vpravo - koreň) void postorderTraversal(Node* root) { if (koreň == NULL) return;  postorderTraversal(root->left);  postorderTraversal(root->right);  cout<< root->údajov<< ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) {  if (root == NULL)  return;  // Queue for level order traversal  queueq;  q.push(koreň);  while (!q.empty()) { Node* temp = q.front();  q.pop();  cout<< temp->údajov<< ' ';  // Push left child in the queue  if (temp->vľavo) q.push(temp->left);  // Push right child vo fronte if (temp->right) q.push(temp->right);  } } /* Funkcia ovládača na kontrolu vyššie uvedeného algoritmu. */ int main() { Uzol* root = NULL;  // Vloženie uzlov root = insert(root, 10);  root = insert(root, 20);  root = insert(root, 30);  root = insert(root, 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); }>

Výkon

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>

Analýza zložitosti operácií binárnych stromov

Operácie	Časová zložitosť	Priestorová zložitosť
Vkladanie	O(N)	O(N)
Preorder Traversal	O(N)	O(N)
Inorder Traversal	O(N)	O(N)
Prenos poštovej poukážky	O(N)	O(N)
Prechádzanie objednávky úrovne	O(N)	O(N)
Vymazanie nat vs postel	O(N)	O(N)
Hľadá sa	O(N)	O(N)

Môžeme použiť Morris Traversal prejsť všetky uzly binárneho stromu v čase O(1).

Výhody binárneho stromu

Efektívne vyhľadávanie: Binárne stromy sú efektívne pri hľadaní špecifického prvku, pretože každý uzol má maximálne dva podriadené uzly, čo umožňuje Pamäťová efektívnosť: Binárne stromy vyžadujú menšiu pamäť v porovnaní s inými stromovými dátovými štruktúrami, preto sú pamäťovo efektívne.
Binárne stromy sa dajú pomerne ľahko implementovať a pochopiť, pretože každý uzol má najviac dve deti, ľavé dieťa a pravé dieťa.

Nevýhody binárneho stromu

Aplikácie binárneho stromu

Binárny strom môže byť použitý predstavujú hierarchické údaje .
Používajú sa Huffmanove kódovacie stromy algoritmy kompresie údajov .
Prioritný front je ďalšia aplikácia binárneho stromu, ktorá sa používa na vyhľadávanie maxima alebo minima v časovej zložitosti O(1).
Užitočné pre indexovanie segmentované v databáze je užitočné pri ukladaní vyrovnávacej pamäte v systéme,
Binárne stromy možno použiť na implementáciu rozhodovacích stromov, čo je typ algoritmu strojového učenia používaného na klasifikáciu a regresnú analýzu.

Často kladené otázky o binárnom strome

1. Čo je to binárny strom?

Binárny strom je nelineárna dátová štruktúra pozostávajúca z uzlov, kde každý uzol má najviac dvoch potomkov (ľavé dieťa a pravé dieťa).

2. Aké sú typy binárnych stromov?

Binárne stromy možno klasifikovať do rôznych typov, vrátane úplných binárnych stromov, úplných binárnych stromov, dokonalých binárnych stromov, vyvážených binárnych stromov (ako sú AVL stromy a červeno-čierne stromy) a degenerovaných (alebo patologických) binárnych stromov.
mapový java iterátor

3. Akú výšku má binárny strom?

Výška binárneho stromu je dĺžka najdlhšej cesty od koreňového uzla po listový uzol. Predstavuje počet hrán na najdlhšej ceste od koreňového uzla po listový uzol.

4. Aká je hĺbka uzla v binárnom strome?

Hĺbka uzla v binárnom strome je dĺžka cesty od koreňového uzla k tomuto konkrétnemu uzlu. Hĺbka koreňového uzla je 0.

5. Ako vykonávate prechod cez strom v binárnom strome?

Prechod stromu v binárnom strome možno vykonať rôznymi spôsobmi: Prechod v poradí, Prechod pred objednávkou, Prechod po objednávke a Prechod v poradí podľa úrovne (známy aj ako prechod do šírky).

6. Čo je to Inorder traversal v binárnom strome?

V Inorder traversal sú uzly rekurzívne navštevované v tomto poradí: ľavé dieťa, koreň, pravé dieťa. Výsledkom tohto prechodu je návšteva uzlov v neklesajúcom poradí v binárnom vyhľadávacom strome.

7. Čo je to prechod predobjednávky v binárnom strome?

V Preorder traversal sú uzly rekurzívne navštevované v tomto poradí: koreň, ľavé dieťa, pravé dieťa. Výsledkom tohto prechodu je, že koreňový uzol je prvým navštíveným uzlom.

8. Čo je to Postorder traversal v binárnom strome?

V Postorder traversal sú uzly rekurzívne navštevované v tomto poradí: ľavé dieťa, pravé dieťa a koreň. Výsledkom tohto prechodu je, že koreňový uzol je posledným navštíveným uzlom.

9. Aký je rozdiel medzi binárnym stromom a binárnym vyhľadávacím stromom?

Binárny strom je hierarchická dátová štruktúra, kde každý uzol má najviac dvoch potomkov, zatiaľ čo binárny vyhľadávací strom je typ binárneho stromu, v ktorom ľavý potomok uzla obsahuje hodnoty menšie ako hodnota uzla a pravý potomok obsahuje hodnoty. väčšia ako hodnota uzla.

10. Čo je to vyvážený binárny strom?

Vyvážený binárny strom je binárny strom, v ktorom sa výška ľavého a pravého podstromu každého uzla líši najviac o jeden. Vyvážené stromy pomáhajú udržiavať efektívne operácie, ako je vyhľadávanie, vkladanie a mazanie s časovou zložitosťou blízkou O (log n).

záver:

Strom je hierarchická dátová štruktúra. Medzi hlavné použitia stromov patrí udržiavanie hierarchických údajov, poskytovanie mierneho prístupu a operácií vkladania/odstránenia. Binárne stromy sú špeciálne prípady stromu, kde každý uzol má najviac dve deti.

Súvisiace články:

Vlastnosti binárneho stromu
Typy binárnych stromov

TechCodeview

Úvod do binárneho stromu – Štruktúra údajov a návody na algoritmy