IEVADS BINĀRAJĀ KOKĀ — DATU STRUKTŪRAS UN ALGORITMU APMĀCĪBAS

Binārais koks ir nelineāra datu struktūra kur katram mezglam ir ne vairāk kā divi bērni. Šajā rakstā mēs apskatīsim visus binārā koka pamatus, darbības ar bināro koku, tā ieviešanu, priekšrocības un trūkumus, kas palīdzēs atrisināt visas problēmas, kuru pamatā ir binārais koks.

Satura rādītājs

Kas ir binārais koks?
Binārā koka attēlojums
Bināro koku veidi
Operācijas ar bināro koku
Binārā koka palīgoperācijas
Binārā koka ieviešana
Bināro koku operāciju sarežģītības analīze
Binārā koka priekšrocības
Binārā koka trūkumi
Binārā koka lietojumprogrammas
Bieži uzdotie jautājumi par bināro koku

Kas ir binārais koks?

Binārais koks ir a koka datu struktūra (nelineāra) kurā var būt katrs mezgls ne vairāk kā divi bērni kas tiek saukti par atstāts bērns un pareizais bērns .

Binārā koka augšējo mezglu sauc par sakne , un tiek izsaukti zemākie mezgli lapas . Bināro koku var vizualizēt kā hierarhisku struktūru ar sakni augšpusē un lapām apakšā.

Binārā koka attēlojums

Katram binārā koka mezglam ir trīs daļas:

Dati
Rādītājs uz kreiso bērnu
Norādiet uz pareizo bērnu

Tālāk ir parādīts binārā koka mezgla attēlojums dažādās valodās:

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

   >>    Bināro koku veidi  
  Bināro koku var iedalīt vairākos veidos, pamatojoties uz vairākiem faktoriem:  
       Pamatojoties uz bērnu skaitu        Pilns binārais koks   
   Deģenerēts binārais koks   
   Sašķiebti binārie koki   
 
 
     Pamatojoties uz līmeņu pabeigšanu         Pilnīgs binārais koks    
   Ideāls binārais koks   
    Līdzsvarots binārais koks    
 
 
     Pamatojoties uz mezgla vērtībām:        Binārais meklēšanas koks   
    AVL koks    
    Sarkans melns koks    
    B Koks    
    B+ koks    
   Segmentu koks   
 
 
 
     Operācijas ar bināro koku     
  1. Ievietošana binārajā kokā  
  Mēs varam ievietot mezglu jebkurā vietā binārā kokā, ievietojot mezglu kā jebkura mezgla kreiso vai labo atvasi vai padarot mezglu par koka sakni.  
      Algoritms mezgla ievietošanai binārajā kokā:     
    Pārbaudiet, vai binārajā kokā nav mezgls, kuram trūkst kreisā bērna. Ja šāds mezgls pastāv, ievietojiet jauno mezglu kā tā kreiso atvasi.  
  Pārbaudiet, vai binārajā kokā nav mezgls, kuram trūkst labā atvasinājuma. Ja šāds mezgls pastāv, ievietojiet jauno mezglu kā tā labo atvasi.  
  Ja mēs neatrodam nevienu mezglu ar trūkstošu kreiso vai labo atvasi, atrodiet mezglu, kurā trūkst abu bērnu, un ievietojiet mezglu kā kreiso vai labo bērnu.  
 
  2. Binārā koka šķērsošana  
  Binārā koka šķērsošana ietver visu binārā koka mezglu apmeklēšanu. Koku šķērsošanas algoritmus var iedalīt divās kategorijās:  
    Dziļuma pirmās meklēšanas (DFS) algoritmi  
  Platuma pirmās meklēšanas (BFS) algoritmi  
 
  Dziļuma pirmās meklēšanas (DFS) algoritmi:  
        Priekšpasūtīšanas šķērsošana (pašreizējais-pa kreisi-pa labi):          Apmeklējiet pašreizējo mezglu pirms jebkuru mezglu apmeklēšanas kreisajā vai labajā apakškokā. Šeit šķērsošana ir sakne – kreisais bērns – labais bērns. Tas nozīmē, ka vispirms tiek šķērsots saknes mezgls, pēc tam tā kreisais bērns un visbeidzot labais bērns.  
       Pasūtījuma šķērsošana (kreisais-strāva-pa labi):               Apmeklējiet pašreizējo mezglu pēc visu mezglu apmeklēšanas kreisajā apakškokā, bet pirms jebkura mezgla apmeklēšanas labajā apakškokā. Šeit šķērsošana ir kreisais bērns – sakne – labais bērns. Tas nozīmē, ka vispirms tiek šķērsots kreisais bērns, pēc tam tā saknes mezgls un visbeidzot labais bērns.  
       Postorder Traversal (kreisais-labais-strāva):       Apmeklējiet pašreizējo mezglu pēc visu kreisā un labā apakškoku mezglu apmeklēšanas.           Šeit šķērsošana ir kreisais bērns – labais bērns – sakne. Tas nozīmē, ka vispirms ir šķērsojis kreisais bērns, tad labais bērns un visbeidzot tā saknes mezgls.  
 
  Platuma pirmās meklēšanas (BFS) algoritmi:  
        Līmeņa pasūtījuma apceļošana:               Apmeklējiet mezglus pa vienam līmenim un vienā līmenī no kreisās uz labo pusi. Šeit šķērsošana notiek līmenī. Tas nozīmē, ka pirmais ir šķērsojis visvairāk kreisais bērns un pēc tam ir šķērsojuši pārējie tā paša līmeņa bērni no kreisās puses uz labo.  
 
  3. Dzēšana binārajā kokā  
  Mēs varam dzēst jebkuru binārā koka mezglu un pēc dzēšanas pārkārtot mezglus, lai atkal izveidotu derīgu bināro koku.  
      Algoritms mezgla dzēšanai binārajā kokā:     
    Sākot no saknes, atrodiet dziļāko un vistālāk labējo binārā koka mezglu un mezglu, kuru vēlamies dzēst.  
  Aizstāt dziļākā, galējā labās puses mezgla datus ar dzēšamo mezglu.  
  Pēc tam izdzēsiet dziļāko labo malējo mezglu.  
 
  4. Meklēšana binārajā kokā  
  Mēs varam meklēt elementu mezglā, izmantojot jebkuru no šķērsošanas metodēm.  
      Algoritms mezgla meklēšanai binārajā kokā:     
    Sāciet no saknes mezgla.  
  Pārbaudiet, vai pašreizējā mezgla vērtība ir vienāda ar mērķa vērtību.  
  Ja pašreizējā mezgla vērtība ir vienāda ar mērķa vērtību, tad šis mezgls ir nepieciešamais mezgls.  
  Pretējā gadījumā, ja mezgla vērtība nav vienāda ar mērķa vērtību, sāciet meklēšanu kreisajā un labajā bērnā.  
  Ja mēs neatrodam nevienu mezglu, kura vērtība ir vienāda ar mērķi, tad vērtība kokā nav.  
 
     Binārā koka palīgoperācijas     
     Koka augstuma atrašana    
   Atrodiet mezgla līmeni binārajā kokā   
   Visa koka izmēra atrašana   
 
  Binārā koka ieviešana  
  Zemāk ir kods binārā koka ievietošanai, dzēšanai un šķērsošanai:  
C dati);  inorderTraversal(sakne->pa labi); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return;  printf('%d ', saknes->dati);  preorderTraversal(root->left);  preorderTraversal(root->right); } // Postorder tree traversal (Left - Right - Root) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(sakne->pa kreisi);  postorderTraversal(sakne->pa labi);  printf('%d ', saknes->dati); } // Funkcija līmeņu secības kokam traversal void levelorderTraversal(Node* root) { if (root == NULL) return;  // Rinda līmeņa pasūtījuma traversal Node* rinda[100];  int priekšā = 0, aizmugurē = 0;  rinda [aizmugure++] = sakne;  while (priekšpuse != aizmugure) { Mezgls* temp = rinda[priekšpuse++];  printf('%d ', temp->data);  // Nospiediet kreiso bērnu rindā if (temp->left) queue[rear++] = temp->left;  // Nospiediet rindā labo bērnu if (temp->right) queue[rear++] = temp->right;  } } /* Draivera funkcija, lai pārbaudītu iepriekš minēto algoritmu. */ int main() { Mezgls* sakne = NULL;  // Mezglu ievietošana sakne = insert(root, 10);  sakne = ievietot(sakne, 20);  sakne = ievietot(sakne, 30);  sakne = ievietot(sakne, 40);  printf('Priekšpasūtīšanas traversal: ');  preorderTraversal(sakne);  printf('
Pasaukuma šķērsošana: ');  inorderTraversal(sakne);  printf('
Postorder traversal: ');  postorderTraversal(sakne);  printf('
Līmeņa pasūtījuma šķērsošana: ');  levelorderTraversal(sakne);  // Dzēst mezglu ar datiem = 20 root = deletion(root, 20);  printf('
Pasūtījuma caurbraukšana pēc dzēšanas: ');  inorderTraversal(sakne);  atgriezties 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  Queue q = jauns LinkedList();  q.piedāvājums(sakne);  while (!q.isEmpty()) { Mezgla temp = q.poll();  // Ievietot mezglu kā vecākmezgla kreiso atvasi if (temp.left == null) { temp.left = new Node(data);  pārtraukums;  } // Ja kreisais atvasinātais nav nulle, spiediet to uz // rindu else q.offer(temp.left);  // Ievietot mezglu kā vecākmezgla labo atvasinājumu if (temp.right == null) { temp.right = new Node(data);  pārtraukums;  } // Ja pareizais atvasinātais nav nulle, nospiediet to uz // rindu else q.offer(temp.right);  } atgriezties sakne;  } /* funkcija, lai dzēstu doto dziļāko mezglu (d_node) binārajā kokā */ public static void deletDeepest(Node root, Node d_node) { Queue q = jauns LinkedList();  q.piedāvājums(sakne);  // Do level order traversal līdz pēdējam mezglam Node temp;  while (!q.isEmpty()) { temp = q.poll();  if (temp == d_node) { temp = null;  d_node = null;  atgriešanās;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = null;  atgriešanās;  } else q.offer(temp.right);  } if (temp.left != null) { if (temp.left == d_node) { temp.left = null;  d_node = null;  atgriešanās;  } else q.offer(temp.left);  } } } /* funkcija elementa dzēšanai binārajā kokā */ public static Mezgla dzēšana(Node root, int key) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == atslēga) return null;  citādi atgriezt sakni;  } Rinda q = jauns LinkedList();  q.piedāvājums(sakne);  Mezgla temp = jauns mezgls(0);  Mezgls key_node = null;  // Veiciet līmeņa secības šķērsošanu, lai atrastu dziļāko // mezglu(temp) un dzēšamo mezglu (key_node), kamēr (!q.isEmpty()) { temp = q.poll();  if (temp.data == atslēga) 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;  dzēstDeepest(sakne, temp);  } atgriezties sakne;  } // Kārtības koka šķērsošana (pa kreisi - sakne - pa labi) public static void inorderTraversal(Node root) { if (root == null) return;  inorderTraversal(root.left);  System.out.print(root.data + ' ');  inorderTraversal(root.right);  } // Preorder tree traversal (Root - Left - Right) public static void preorderTraversal(Node root) { if (root == null) return;  System.out.print(root.data + ' ');  preorderTraversal(root.left);  preorderTraversal(root.right);  } // Postorder tree traversal (Left - Right - Root) public static void postorderTraversal(Node root) { if (root == null) return;  postorderTraversal(root.left);  postorderTraversal(root.right);  System.out.print(root.data + ' ');  } // Funkcija Līmeņa secības koka traversal public static void levelorderTraversal(Node root) { if (root == null) return;  // Rinda līmeņa pasūtījuma šķērsošanai Rinda q = jauns LinkedList();  q.piedāvājums(sakne);  while (!q.isEmpty()) { Mezgla temp = q.poll();  System.out.print(temp.data + ' ');  // Nospiediet kreiso bērnu rindā if (temp.left != null) q.offer(temp.left);  // Nospiediet rindā labo bērnu if (temp.right != null) q.offer(temp.right);  } } /* Draivera funkcija, lai pārbaudītu iepriekš minēto algoritmu. */ public static void main(String[] args) { Mezgla sakne = null;  // Mezglu ievietošana sakne = insert(root, 10);  sakne = ievietot(sakne, 20);  sakne = ievietot(sakne, 30);  sakne = ievietot(sakne, 40);  System.out.print('Priekšpasūtīšanas caurlaide: ');  preorderTraversal(sakne);  System.out.print('
Inorder traversal: ');  inorderTraversal(sakne);  System.out.print('
Postorder traversal: ');  postorderTraversal(sakne);  System.out.print('
Līmeņa pasūtījuma šķērsošana: ');  levelorderTraversal(sakne);  // Dzēst mezglu ar datiem = 20 root = deletion(root, 20);  System.out.print('
Pavēles caurbraukšana pēc dzēšanas: ');  inorderTraversal(sakne);  } }

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  Queue q = jauna rinda ();  q.Enqueue(sakne);  while (q.Count != 0) { Node temp = q.Dequeue();  // Ievietot mezglu kā vecākmezgla kreiso atvasi if (temp.left == null) { temp.left = new Node(data);  pārtraukums;  } // Ja kreisais atvasinātais nav nulle, nobīdiet to uz rindu else q.Enqueue(temp.left);  // Ievietot mezglu kā vecākmezgla labo atvasinājumu if (temp.right == null) { temp.right = new Node(data);  pārtraukums;  } // Ja pareizais atvasinātais nav nulle, nobīdiet to uz rindu else q.Enqueue(temp.right);  } atgriezties sakne;  } /* funkcija, lai dzēstu doto dziļāko mezglu (d_node) binārajā kokā */ public static void DeleteDeepest(Node root, Node d_node) { Queue q = jauna rinda ();  q.Enqueue(sakne);  // Do level order traversal līdz pēdējam mezglam Node temp;  while (q.Count != 0) { temp = q.Dequeue();  if (temp == d_node) { temp = null;  d_node = null;  atgriešanās;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = null;  atgriešanās;  } else q.Enqueue(temp.right);  } if (temp.left != null) { if (temp.left == d_node) { temp.left = null;  d_node = null;  atgriešanās;  } else q.Enqueue(temp.left);  } } } /* funkcija elementa dzēšanai binārajā kokā */ public static Node Deletion(Node root, int key) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == atslēga) return null;  citādi atgriezt sakni;  } Rinda q = jauna rinda ();  q.Enqueue(sakne);  Mezgla temp = jauns mezgls(0);  Mezgls key_node = null;  // Veiciet līmeņa secības šķērsošanu, lai atrastu dziļāko mezglu (temp) un dzēšamo mezglu (key_node), kamēr (q.Count != 0) { temp = q.Dequeue();  if (temp.data == atslēga) 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;  DzēstDeepest(sakne, temp);  } atgriezties sakne;  } // Kārtības koka šķērsošana (pa kreisi - sakne - pa labi) public static void InorderTraversal(Node root) { if (root == null) return;  InorderTraversal(root.left);  Console.Write(root.data + ' ');  InorderTraversal(root.right);  } // Preorder tree traversal (Root - Left - Right) public static void PreorderTraversal(Node root) { if (root == null) return;  Console.Write(root.data + ' ');  PreorderTraversal(root.left);  PreorderTraversal(root.right);  } // Postorder tree traversal (Left - Right - Root) public static void PostorderTraversal(Node root) { if (root == null) return;  PostorderTraversal(root.left);  PostorderTraversal(root.right);  Console.Write(root.data + ' ');  } // Funkcija līmeņu secības koka traversal public static void LevelorderTraversal(Node root) { if (root == null) return;  // Rinda līmeņa pasūtījuma šķērsošanai Rinda q = jauna rinda ();  q.Enqueue(sakne);  while (q.Count != 0) { Node temp = q.Dequeue();  Console.Write(temp.data + ' ');  // Nospiediet kreiso bērnu rindā if (temp.left != null) q.Enqueue(temp.left);  // Nospiediet rindā labo bērnu if (temp.right != null) q.Enqueue(temp.right);  } } /* Draivera funkcija, lai pārbaudītu iepriekš minēto algoritmu. */ public static void Main(string[] args) { Mezgla sakne = null;  // Mezglu ievietošana sakne = Insert(sakne, 10);  sakne = Ievietot(sakne, 20);  sakne = Ievietot(sakne, 30);  sakne = Ievietot(sakne, 40);  Console.Write('Priekšpasūtīšanas traversal: ');  PreorderTraversal(sakne);  Console.Write('
Inorder traversal: ');  InorderTraversal(sakne);  Console.Write('
Postorder traversal: ');  PostorderTraversal(sakne);  Console.Write('
Līmeņa pasūtījuma šķērsošana: ');  LevelorderTraversal(sakne);  // Dzēst mezglu ar datiem = 20 root = Dzēst(sakne, 20);  Console.Write('
Pasūtīt pārvietošanu pēc dzēšanas: ');  InorderTraversal(sakne);  } }

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  queue q;  q.push(root);  while (!q.empty()) { Node* temp = q.front();  q.pop();  // Ievietot mezglu kā vecākmezgla kreiso atvasi if (temp->left == NULL) { temp->left = new Node(data);  pārtraukums;  } // Ja kreisais bērns nav nulle, spiediet to uz // rindu else q.push(temp->left);  // Ievietot mezglu kā vecākmezgla labo atvasinājumu if (temp->right == NULL) { temp->right = new Node(data);  pārtraukums;  } // Ja pareizais atvasinātais nav nulle, nospiediet to uz // rindu else q.push(temp->right);  } atgriezties sakne; } /* funkcija, lai dzēstu doto dziļāko mezglu (d_node) binārajā kokā */ void deletDeepest(Node* root, Node* d_node) { rinda q;  q.push(root);  // Veikt līmeņa pasūtījuma šķērsošanu līdz pēdējam mezglam Node* temp;  while (!q.empty()) { temp = q.front();  q.pop();  if (temp == d_node) { temp = NULL;  dzēst (d_node);  atgriešanās;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  dzēst (d_node);  atgriešanās;  } else q.push(temp->right);  } if (temp->left) { if (temp->left == d_node) { temp->left = NULL;  dzēst (d_node);  atgriešanās;  } else q.push(temp->left);  } } } /* funkcija elementa dzēšanai binārajā kokā */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == atslēga) return NULL;  citādi atgriezt sakni;  } rindā q;  q.push(root);  Mezgls* temp;  Node* key_node = NULL;  // Veiciet līmeņa secības šķērsošanu, lai atrastu dziļāko // mezglu(temp) un dzēšamo mezglu (key_node), kamēr (!q.empty()) { temp = q.front();  q.pop();  if (temp->data == atslēga) 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;  atslēgas_mezgls->dati = x;  dzēstDeepest(sakne, temp);  } atgriezties sakne; } // Kārtības koka traversal (Left - Root - Right) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(sakne->pa kreisi);  cout < < root->datus < < ' ';  inorderTraversal(root->pa labi); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return;  cout < < root->datus < < ' ';  preorderTraversal(root->pa kreisi);  preorderTraversal(root->right); } // Postorder tree traversal (Left - Right - Root) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(sakne->pa kreisi);  postorderTraversal(sakne->pa labi);  cout < < root->datus < < ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) {  if (root == NULL)  return;  // Queue for level order traversal  queue q;  q.push(root);  while (!q.empty()) { Node* temp = q.front();  q.pop();  cout < < temp->datus < < ' ';  // Push left child in the queue  if (temp->pa kreisi) q.push(temp->left);  // Nospiest labo bērnu rindā if (temp->right) q.push(temp->right);  } } /* Draivera funkcija, lai pārbaudītu iepriekš minēto algoritmu. */ int main() { Mezgls* sakne = NULL;  // Mezglu ievietošana sakne = insert(root, 10);  sakne = ievietot(sakne, 20);  sakne = ievietot(sakne, 30);  sakne = ievietot(sakne, 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); }

Izvade

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

Bināro koku operāciju sarežģītības analīze

Operācijas	Laika sarežģītība	Kosmosa sarežģītība
Ievietošana	O(N)	O(N)
Iepriekšpasūtīšanas šķērsošana	O(N)	O(N)
Pasūtījuma šķērsošana	O(N)	O(N)
Pasta pasūtījumu šķērsošana	O(N)	O(N)
Līmeņa pasūtījumu izbraukšana	O(N)	O(N)
Dzēšana	O(N)	O(N)
Meklēšana	O(N)	O(N)

Varam izmantot Moriss Traversals lai šķērsotu visus binārā koka mezglus O(1) laikā.

Binārā koka priekšrocības

Efektīva meklēšana: Binārie koki ir efektīvi, meklējot konkrētu elementu, jo katram mezglam ir ne vairāk kā divi pakārtotie mezgli, kas ļauj Efektīva atmiņa: Binārajiem kokiem ir nepieciešams mazāk atmiņas, salīdzinot ar citām koku datu struktūrām, tāpēc tie ir atmiņu efektīvi.
Bināros kokus ir salīdzinoši viegli ieviest un saprast, jo katram mezglam ir ne vairāk kā divi bērni, kreisais bērns un labais bērns.

Binārā koka trūkumi

Binārā koka lietojumprogrammas

Bināro koku var izmantot, lai pārstāv hierarhiskus datus .
Tiek izmantoti Huffman kodēšanas koki datu saspiešanas algoritmi .
Prioritātes rinda ir vēl viena binārā koka lietojumprogramma, ko izmanto, lai meklētu maksimālo vai minimumu O(1) laika sarežģītībā.
Noderīga indeksēšanai, kas segmentēta datu bāzē, ir noderīga kešatmiņas saglabāšanai sistēmā,
Bināros kokus var izmantot, lai ieviestu lēmumu kokus, kas ir mašīnmācīšanās algoritma veids, ko izmanto klasifikācijai un regresijas analīzei.

Bieži uzdotie jautājumi par bināro koku

1. Kas ir binārais koks?

Binārais koks ir nelineāra datu struktūra, kas sastāv no mezgliem, kur katram mezglam ir ne vairāk kā divi bērni (kreisais bērns un labais bērns).

2. Kādi ir bināro koku veidi?

Bināros kokus var klasificēt dažādos veidos, ieskaitot pilnos bināros kokus, pilnos bināros kokus, perfektos bināros kokus, līdzsvarotos bināros kokus (piemēram, AVL kokus un sarkanmelnos kokus) un deģenerētus (vai patoloģiskus) bināros kokus.

3. Kāds ir binārā koka augstums?

Binārā koka augstums ir garākā ceļa garums no saknes mezgla līdz lapas mezglam. Tas attēlo malu skaitu garākajā ceļā no saknes mezgla līdz lapas mezglam.

4. Kāds ir binārā koka mezgla dziļums?

Binārā koka mezgla dziļums ir ceļa garums no saknes mezgla līdz konkrētajam mezglam. Saknes mezgla dziļums ir 0.

5. Kā jūs veicat koka šķērsošanu binārajā kokā?

Koka pārvietošanu binārajā kokā var veikt dažādos veidos: šķērsošana secībā, šķērsošana pirms pasūtījuma, šķērsošana pēc pasūtījuma un šķērsošana pēc līmeņa (pazīstama arī kā šķērsošana pēc platuma).

6. Kas ir Inorder šķērsošana binārajā kokā?

Inorder traversal mezgli tiek rekursīvi apmeklēti šādā secībā: kreisais bērns, sakne, labais bērns. Šīs šķērsošanas rezultātā mezgli tiek apmeklēti nesamazināmā secībā binārā meklēšanas kokā.

7. Kas ir priekšpasūtīšanas šķērsošana pakalpojumā Binary Tree?

Veicot priekšpasūtīšanas šķērsošanu, mezgli tiek rekursīvi apmeklēti šādā secībā: sakne, kreisais bērns, labais bērns. Šīs šķērsošanas rezultātā saknes mezgls ir pirmais apmeklētais mezgls.

8. Kas ir postorder traversal in Binary Tree?

Postorder traversal mezgli tiek rekursīvi apmeklēti šādā secībā: kreisais bērns, labais bērns un sakne. Šīs šķērsošanas rezultātā saknes mezgls ir pēdējais apmeklētais mezgls.

9. Kāda ir atšķirība starp bināro koku un bināro meklēšanas koku?

Binārais koks ir hierarhiska datu struktūra, kurā katram mezglam ir ne vairāk kā divi bērni, turpretim binārais meklēšanas koks ir bināra koka veids, kurā mezgla kreisais atvasinātais satur vērtības, kas ir mazākas par mezgla vērtību, bet labajā bērnā ir vērtības. lielāka par mezgla vērtību.

10. Kas ir līdzsvarots binārais koks?

Līdzsvarots binārais koks ir binārs koks, kurā katra mezgla kreisā un labā apakškoka augstums atšķiras ne vairāk kā par vienu. Līdzsvaroti koki palīdz uzturēt efektīvas darbības, piemēram, meklēšanu, ievietošanu un dzēšanu, ar laika sarežģītību tuvu O(log n).

Secinājums:

Koks ir hierarhiska datu struktūra. Galvenie koku lietojumi ietver hierarhisku datu uzturēšanu, mērenas piekļuves nodrošināšanu un ievietošanas/dzēšanas darbības. Binārie koki ir īpaši koku gadījumi, kad katram mezglam ir ne vairāk kā divi bērni.