UVOD V BINARNO DREVO - VADNICE ZA STRUKTURO PODATKOV IN ALGORITME - TECHCODEVIEW.COM

Binarno drevo je nelinearna struktura podatkov kjer ima vsako vozlišče največ dva otroka. V tem članku bomo obravnavali vse osnove binarnega drevesa, operacije na binarnem drevesu, njegovo implementacijo, prednosti in slabosti, kar vam bo pomagalo rešiti vse težave, ki temeljijo na binarnem drevesu.

Kazalo

začne se z javo

Kaj je binarno drevo?
Predstavitev binarnega drevesa
Vrste binarnega drevesa
Operacije na binarnem drevesu
Pomožne operacije na binarnem drevesu
Implementacija binarnega drevesa
Analiza kompleksnosti binarnih drevesnih operacij
Prednosti binarnega drevesa
Slabosti binarnega drevesa
Uporaba binarnega drevesa
Pogosta vprašanja o binarnem drevesu

Kaj je binarno drevo?

Binarno drevo je a drevesna podatkovna struktura (nelinearna) v kateri ima lahko vsako vozlišče največ dva otroka ki se imenujejo levi otrok in pravi otrok .

Najvišje vozlišče v binarnem drevesu se imenuje korenina , in pokličejo se skrajna spodnja vozlišča listi . Binarno drevo si lahko predstavljamo kot hierarhično strukturo s korenino na vrhu in listi na dnu.

Predstavitev binarnega drevesa

Vsako vozlišče v binarnem drevesu ima tri dele:

podatki
Kazalec na levega otroka
Kazalec na pravega otroka

Spodaj je predstavitev vozlišča binarnega drevesa v različnih jezikih:

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

Vrste binarnega drevesa

Binarno drevo je mogoče razvrstiti v več vrst na podlagi več dejavnikov:

Na podlagi števila otrok
- Polno binarno drevo
- Degenerirano binarno drevo
- Poševna binarna drevesa
Na podlagi dokončanja ravni
- Popolno binarno drevo
- Popolno binarno drevo
- Uravnoteženo binarno drevo
Na podlagi vrednosti vozlišča:
- Binarno iskalno drevo
- Drevo AVL
- Rdeče črno drevo
- B Drevo
- B+ Drevo
- Segmentno drevo

Operacije na binarnem drevesu

1. Vstavljanje v binarno drevo

Vozlišče lahko vstavimo kamor koli v binarnem drevesu tako, da vozlišče vstavimo kot levega ali desnega otroka katerega koli vozlišča ali da naredimo vozlišče kot koren drevesa.

Algoritem za vstavljanje vozlišča v binarno drevo:

Preverite, ali obstaja vozlišče v binarnem drevesu, ki ima manjkajočega levega otroka. Če takšno vozlišče obstaja, vstavite novo vozlišče kot njegov levi podrejeni element.
Preverite, ali obstaja vozlišče v binarnem drevesu, ki ima manjkajočega desnega otroka. Če takšno vozlišče obstaja, vstavite novo vozlišče kot njegov desni podrejeni element.
Če ne najdemo nobenega vozlišča z manjkajočim levim ali desnim podrejenim elementom, potem poiščemo vozlišče, v katerem manjkata oba podrejena elementa, in vstavimo vozlišče kot njegov levi ali desni podrejeni element.

2. Prehod binarnega drevesa

Prehod binarnega drevesa vključuje obisk vseh vozlišč binarnega drevesa. Algoritme prečkanja dreves lahko na splošno razvrstimo v dve kategoriji:

Algoritmi iskanja najprej v globino (DFS).
Algoritmi iskanja v širino (BFS).

Algoritmi za iskanje najprej v globino (DFS):

Prehod prednaročila (trenutno-levo-desno): Obiščite trenutno vozlišče, preden obiščete katero koli vozlišče znotraj levega ali desnega poddrevesa. Tukaj je prečkanje koren – levi otrok – desni otrok. To pomeni, da se najprej prečka korensko vozlišče, nato njegov levi otrok in na koncu desni otrok.
Prehod po vrstnem redu (levo-trenutno-desno): Obiščite trenutno vozlišče po obisku vseh vozlišč v levem poddrevesu, vendar preden obiščete katero koli vozlišče v desnem poddrevesu. Tukaj je prehod levi otrok – koren – desni otrok. To pomeni, da se najprej prečka levi otrok, nato korensko vozlišče in na koncu desni otrok.
Prehod po naročilu (levo-desno-trenutno): Obiščite trenutno vozlišče po obisku vseh vozlišč levega in desnega poddrevesa. Tukaj je prehod levi otrok – desni otrok – koren. To pomeni, da je levi otrok najprej prečkal nato desnega otroka in nazadnje njegovo korensko vozlišče.

Algoritmi iskanja v širino (BFS):

Prehod ravni vrstnega reda: Obiščite vozlišča po stopnjah in od leve proti desni na isti ravni. Tukaj je prečenje nivojsko. Pomeni, da je prvi prečkal skrajno levi otrok, nato pa so prečkali drugi otroci iste ravni od leve proti desni.

3. Brisanje v binarnem drevesu

Izbrišemo lahko katero koli vozlišče v binarnem drevesu in prerazporedimo vozlišča po izbrisu, da ponovno tvorimo veljavno binarno drevo.

Algoritem za brisanje vozlišča v binarnem drevesu:

Začnite pri korenu in poiščite najgloblje in skrajno desno vozlišče v binarnem drevesu ter vozlišče, ki ga želimo izbrisati.
Zamenjajte podatke najglobljega skrajno desnega vozlišča z vozliščem, ki ga želite izbrisati.
Nato izbrišite najgloblje skrajno desno vozlišče.

4. Iskanje v binarnem drevesu

Element v vozlišču lahko iščemo s katero koli od tehnik prečkanja.

Algoritem za iskanje vozlišča v binarnem drevesu:

Začnite s korenskim vozliščem.
Preverite, ali je vrednost trenutnega vozlišča enaka ciljni vrednosti.
Če je vrednost trenutnega vozlišča enaka ciljni vrednosti, je to vozlišče zahtevano vozlišče.
V nasprotnem primeru, če vrednost vozlišča ni enaka ciljni vrednosti, začnite iskanje v levem in desnem podrejenem elementu.
Če ne najdemo nobenega vozlišča, katerega vrednost je enaka ciljni, potem vrednost ni prisotna v drevesu.

Pomožne operacije na binarnem drevesu

Iskanje višine drevesa
Poiščite raven vozlišča v binarnem drevesu
Iskanje velikosti celotnega drevesa

Implementacija binarnega drevesa

Spodaj je koda za vstavljanje, brisanje in prečkanje binarnega drevesa:

 #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->podatki = val;  temp->levo = temp->desno = NULL;  povratna temperatura; } // Funkcija za vstavljanje vozlišč Node* insert(Node* root, int data) { // Če je drevo prazno, postane novo vozlišče koren if (root == NULL) { root = newNode(data);  povratni koren;  } // Čakalna vrsta za prečkanje drevesa in iskanje položaja za vstavljanje vozlišča Node* queue[100];  int spredaj = 0, zadaj = 0;  čakalna vrsta [zadaj++] = koren;  medtem ko (spredaj != zadaj) { Node* temp = queue[front++];  // Vstavi vozlišče kot levi podrejeni element nadrejenega vozlišča if (temp->left == NULL) { temp->left = newNode(data);  odmor;  } // Če levi podrejeni element ni nič, ga potisnite v čakalno vrsto else queue[rear++] = temp->left;  // Vstavi vozlišče kot desnega podrejenega nadrejenega vozlišča if (temp->right == NULL) { temp->right = newNode(data);  odmor;  } // Če desni podrejeni ni nič, ga potisni v čakalno vrsto else queue[rear++] = temp->right;  } vrni koren; } /* Funkcija za brisanje danega najglobljega vozlišča (d_node) v binarnem drevesu */ void deletDeepest(Node* root, Node* d_node) { Node* queue[100];  int spredaj = 0, zadaj = 0;  čakalna vrsta [zadaj++] = koren;  // Izvedite prečkanje vrstnega reda ravni do zadnjega vozlišča Node* temp;  medtem ko (spredaj != zadaj) { temp = čakalna vrsta[spredaj++];  if (temp == d_node) {temp = NULL;  brezplačno (d_node);  vrnitev;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  brezplačno (d_node);  vrnitev;  } else queue[rear++] = temp->right;  } if (temp->left) { if (temp->left == d_node) { temp->left = NULL;  brezplačno (d_node);  vrnitev;  } else queue[rear++] = temp->left;  } } } /* Funkcija za brisanje elementa v binarnem drevesu */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL;  drugače vrni koren;  } Vozlišče* čakalna vrsta [100];  int spredaj = 0, zadaj = 0;  čakalna vrsta [zadaj++] = koren;  Vozlišče* temp;  Vozlišče* ključno_vozlišče = NULL;  // Izvedite prečkanje vrstnega reda ravni, da poiščete najgloblje vozlišče (temp) in vozlišče, ki ga želite izbrisati (key_node), medtem ko (spredaj != zadaj) { temp = queue[front++];  if (temp->data == ključ) key_node = temp;  if (temp->left) queue[rear++] = temp->left;  if (temp->desno) queue[rear++] = temp->desno;  } if (key_node != NULL) { int x = temp->data;  ključno_vozlišče->podatki = x;  deletDeepest(root, temp);  } vrni koren; } // Prehod drevesa po vrstnem redu (levo - koren - desno) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(root->left);  printf('%d ', root->data);  inorderTraversal(root->desno); } // Prednaročilo prehod drevesa (Koren - levo - desno) void preorderTraversal(Node* root) { if (!root) return;  printf('%d ', root->data);  preorderTraversal(root->left);  preorderTraversal(root->desno); } // Prehod drevesa po naročilu (levo - desno - koren) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(root->left);  postorderTraversal(root->desno);  printf('%d ', root->data); } // Funkcija za prečkanje drevesa vrstnega reda ravni void levelorderTraversal(Node* root) { if (root == NULL) return;  // Čakalna vrsta za prečkanje vrstnega reda ravni Node* queue[100];  int spredaj = 0, zadaj = 0;  čakalna vrsta [zadaj++] = koren;  medtem ko (spredaj != zadaj) { Node* temp = queue[front++];  printf('%d ', temp->podatki);  // Potisni levega otroka v čakalno vrsto if (temp->left) queue[rear++] = temp->left;  // Potisni desnega otroka v čakalno vrsto if (temp->right) queue[rear++] = temp->right;  } } /* Funkcija gonilnika za preverjanje zgornjega algoritma. */ int main() { Node* root = NULL;  // Vstavljanje vozlišč root = insert(root, 10);  koren = vstavi(koren, 20);  koren = vstavi(koren, 30);  koren = vstavi (koren, 40);  printf('Prehod prednaročila: ');  preorderTraversal(root);  printf('
Prehod po vrstnem redu: ');  inorderTraversal(root);  printf('
Prehod po naročilu: ');  postorderTraversal(root);  printf('
Prehod ravni vrstnega reda: ');  levelorderTraversal(root);  // Izbriši vozlišče s podatki = 20 root = deletion(root, 20);  printf('
Prehod po vrstnem redu po brisanju: ');  inorderTraversal(root);  vrni 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 = nov LinkedList();  q.offer(root);  medtem ko (!q.isEmpty()) { Node temp = q.poll();  // Vstavi vozlišče kot levi podrejeni element nadrejenega vozlišča if (temp.left == null) { temp.left = new Node(data);  odmor;  } // Če levi podrejeni element ni ničelni, ga potisnite // v čakalno vrsto else q.offer(temp.left);  // Vstavi vozlišče kot desnega podrejenega nadrejenega vozlišča if (temp.right == null) { temp.right = novo vozlišče(podatki);  odmor;  } // Če desni otrok ni ničelni, ga potisnite // v čakalno vrsto else q.offer(temp.right);  } vrni koren;  } /* funkcija za brisanje podanega najglobljega vozlišča (d_node) v binarnem drevesu */ public static void deletDeepest(Node root, Node d_node) { Queueq = nov LinkedList();  q.offer(root);  // Izvedite prečkanje vrstnega reda ravni do zadnjega vozlišča Node temp;  medtem ko (!q.isEmpty()) { temp = q.poll();  if (temp == d_node) {temp = null;  d_node = nič;  vrnitev;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = nič;  vrnitev;  } else q.offer(temp.right);  } if (temp.left != null) { if (temp.left == d_node) { temp.left = null;  d_node = nič;  vrnitev;  } else q.offer(temp.left);  } } } /* funkcija za brisanje elementa v binarnem drevesu */ public static Node deletion(Node root, int key) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == key) return null;  drugače vrni koren;  } Čakalna vrstaq = nov LinkedList();  q.offer(root);  Temp vozlišča = novo vozlišče(0);  Vozlišče key_node = nič;  // Izvedite prečkanje vrstnega reda ravni, da najdete // najgloblje vozlišče(temp) in vozlišče, ki ga želite izbrisati (key_node) while (!q.isEmpty()) { temp = q.poll();  if (temp.data == ključ) 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);  } vrni koren;  } // Prehod drevesa po vrstnem redu (levo - koren - desno) public static void inorderTraversal(Node root) { if (root == null) return;  inorderTraversal(root.left);  System.out.print(root.data + ' ');  inorderTraversal(root.right);  } // Prednaročilo prehod drevesa (Koren - levo - desno) public static void preorderTraversal(Node root) { if (root == null) return;  System.out.print(root.data + ' ');  preorderTraversal(root.left);  preorderTraversal(root.right);  } // Prehod drevesa po naročilu (levo - desno - koren) public static void postorderTraversal(koren vozlišča) { if (root == null) return;  postorderTraversal(root.left);  postorderTraversal(root.right);  System.out.print(root.data + ' ');  } // Funkcija za prečkanje drevesa vrstnega reda ravni public static void levelorderTraversal(Node root) { if (root == null) return;  // Čakalna vrsta za prečkanje vrstnega reda ravni Čakalna vrstaq = nov LinkedList();  q.offer(root);  medtem ko (!q.isEmpty()) { Node temp = q.poll();  System.out.print(temp.data + ' ');  // Potisni levega otroka v čakalno vrsto if (temp.left != null) q.offer(temp.left);  // Potisnite desnega otroka v čakalno vrsto if (temp.right != null) q.offer(temp.right);  } } /* Funkcija gonilnika za preverjanje zgornjega algoritma. */ public static void main(String[] args) { Node root = null;  // Vstavljanje vozlišč root = insert(root, 10);  koren = vstavi(koren, 20);  koren = vstavi(koren, 30);  koren = vstavi (koren, 40);  System.out.print('Prehod prednaročila: ');  preorderTraversal(root);  System.out.print('
Prehod po vrstnem redu: ');  inorderTraversal(root);  System.out.print('
Prehod po naročilu: ');  postorderTraversal(root);  System.out.print('
Prehod ravni vrstnega reda: ');  levelorderTraversal(root);  // Izbriši vozlišče s podatki = 20 root = deletion(root, 20);  System.out.print('
Prehod po vrstnem redu po brisanju: ');  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 = nova čakalna vrsta();  q.Enqueue(root);  medtem ko (q.Count != 0) { Node temp = q.Dequeue();  // Vstavi vozlišče kot levi podrejeni element nadrejenega vozlišča if (temp.left == null) { temp.left = new Node(data);  odmor;  } // Če levi podrejeni element ni nič, ga potisnite v čakalno vrsto else q.Enqueue(temp.left);  // Vstavi vozlišče kot desnega podrejenega nadrejenega vozlišča if (temp.right == null) { temp.right = novo vozlišče(podatki);  odmor;  } // Če desni podrejeni element ni nič, ga potisnite v čakalno vrsto else q.Enqueue(temp.right);  } vrni koren;  } /* funkcija za brisanje danega najglobljega vozlišča (d_node) v binarnem drevesu */ public static void DeleteDeepest(Node root, Node d_node) { Queueq = nova čakalna vrsta();  q.Enqueue(root);  // Izvedite prečkanje vrstnega reda ravni do zadnjega vozlišča Node temp;  medtem ko (q.Count != 0) { temp = q.Dequeue();  if (temp == d_node) {temp = null;  d_node = nič;  vrnitev;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = nič;  vrnitev;  } else q.Enqueue(temp.right);  } if (temp.left != null) { if (temp.left == d_node) { temp.left = null;  d_node = nič;  vrnitev;  } else q.Enqueue(temp.left);  } } } /* funkcija za brisanje elementa v binarnem drevesu */ public static Node Deletion(Node root, int key) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == key) return null;  drugače vrni koren;  } Čakalna vrstaq = nova čakalna vrsta();  q.Enqueue(root);  Temp vozlišča = novo vozlišče(0);  Vozlišče key_node = nič;  // Izvedite prečkanje vrstnega reda ravni, da poiščete najgloblje vozlišče (temp) in vozlišče, ki ga želite izbrisati (key_node), medtem ko (q.Count != 0) { temp = q.Dequeue();  if (temp.data == ključ) 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);  } vrni koren;  } // Inorder drevesno prečkanje (levo - koren - desno) public static void InorderTraversal(Node root) { if (root == null) return;  InorderTraversal(root.left);  Console.Write(root.data + ' ');  InorderTraversal(root.right);  } // Prednaročilo prečkanje drevesa (Koren - Levo - Desno) public static void PreorderTraversal(Node root) { if (root == null) return;  Console.Write(root.data + ' ');  PredorderTraversal(root.left);  PredorderTraversal(root.right);  } // Prehod drevesa po naročilu (levo - desno - koren) public static void PostorderTraversal(koren vozlišča) { if (root == null) return;  PostorderTraversal(root.left);  PostorderTraversal(root.right);  Console.Write(root.data + ' ');  } // Funkcija za prečkanje drevesa vrstnega reda ravni public static void LevelorderTraversal(Node root) { if (root == null) return;  // Čakalna vrsta za prečkanje vrstnega reda ravni Čakalna vrstaq = nova čakalna vrsta();  q.Enqueue(root);  medtem ko (q.Count != 0) { Node temp = q.Dequeue();  Console.Write(temp.data + ' ');  // Potisni levega otroka v čakalno vrsto if (temp.left != null) q.Enqueue(temp.left);  // Potisnite desnega otroka v čakalno vrsto if (temp.right != null) q.Enqueue(temp.right);  } } /* Funkcija gonilnika za preverjanje zgornjega algoritma. */ public static void Main(string[] args) { Node root = null;  // Vstavljanje vozlišč root = Insert(root, 10);  koren = Vstavi(koren, 20);  koren = Vstavi(koren, 30);  koren = Vstavi(koren, 40);  Console.Write('Prehod prednaročila: ');  PredorderTraversal(root);  Console.Write('
Prehod po vrstnem redu: ');  InorderTraversal(root);  Console.Write('
Prehod po naročilu: ');  PostorderTraversal(root);  Console.Write('
Prehod ravni vrstnega reda: ');  LevelorderTraversal(root);  // Izbriši vozlišče s podatki = 20 root = Deletion(root, 20);  Console.Write('
Prehod po vrstnem redu po brisanju: ');  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(root);  medtem ko (!q.empty()) { Node* temp = q.front();  q.pop();  // Vstavi vozlišče kot levi podrejeni element nadrejenega vozlišča if (temp->left == NULL) { temp->left = new Node(data);  odmor;  } // Če levi podrejeni element ni nič, ga potisnite v // čakalno vrsto else q.push(temp->left);  // Vstavi vozlišče kot desnega podrejenega nadrejenega vozlišča if (temp->right == NULL) { temp->right = new Node(data);  odmor;  } // Če desni podrejeni ni ničelni, ga potisnite // v čakalno vrsto else q.push(temp->right);  } vrni koren; } /* funkcija za brisanje podanega najglobljega vozlišča (d_node) v binarnem drevesu */ void deletDeepest(Node* root, Node* d_node) { queueq;  q.push(root);  // Izvedite prečkanje vrstnega reda ravni do zadnjega vozlišča Node* temp;  medtem ko (!q.empty()) { temp = q.front();  q.pop();  if (temp == d_node) {temp = NULL;  izbriši (d_node);  vrnitev;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  izbriši (d_node);  vrnitev;  } else q.push(temp->right);  } if (temp->left) { if (temp->left == d_node) { temp->left = NULL;  izbriši (d_node);  vrnitev;  } else q.push(temp->left);  } } } /* funkcija za brisanje elementa v binarnem drevesu */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL;  drugače vrni koren;  } čakalna vrstaq;  q.push(root);  Vozlišče* temp;  Vozlišče* ključno_vozlišče = NULL;  // Izvedite prečkanje vrstnega reda ravni, da najdete // najgloblje vozlišče (temp) in vozlišče, ki ga želite izbrisati (key_node) medtem ko (!q.empty()) { temp = q.front();  q.pop();  if (temp->data == key) key_node = temp;  if (temp->left) q.push(temp->left);  če (temp->desno) q.push(temp->desno);  } if (key_node != NULL) { int x = temp->data;  ključno_vozlišče->podatki = x;  deletDeepest(root, temp);  } vrni koren; } // Prehod drevesa po vrstnem redu (levo - koren - desno) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(root->left);  cout<< root->podatke<< ' ';  inorderTraversal(root->prav); } // Prednaročilo prehod drevesa (Koren - levo - desno) void preorderTraversal(Node* root) { if (!root) return;  cout<< root->podatke<< ' ';  preorderTraversal(root->levo);  preorderTraversal(root->desno); } // Prehod drevesa po naročilu (levo - desno - koren) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(root->left);  postorderTraversal(root->desno);  cout<< root->podatke<< ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) {  if (root == NULL)  return;  // Queue for level order traversal  queueq;  q.push(root);  medtem ko (!q.empty()) { Node* temp = q.front();  q.pop();  cout<< temp->podatke<< ' ';  // Push left child in the queue  if (temp->levo) q.push(temp->levo);  // Potisnite desnega otroka v čakalno vrsto if (temp->right) q.push(temp->right);  } } /* Funkcija gonilnika za preverjanje zgornjega algoritma. */ int main() { Node* root = NULL;  // Vstavljanje vozlišč root = insert(root, 10);  koren = vstavi(koren, 20);  koren = vstavi(koren, 30);  koren = vstavi (koren, 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); }>

Izhod

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>

Analiza kompleksnosti binarnih drevesnih operacij

Operacije	Časovna zapletenost	Kompleksnost prostora
Vstavljanje	O(N)	O(N)
Prehod pred naročilom	O(N)	O(N)
Prehod po vrstnem redu	O(N)	O(N)
Prevoz poštnega naročila	O(N)	O(N)
Level Order Traversal	O(N)	O(N) java bubble sort
Izbris	O(N)	O(N)
Iskanje	O(N)	O(N)

Lahko uporabimo Morris Traversal prečkati vsa vozlišča binarnega drevesa v O(1) času.

število v niz java

Prednosti binarnega drevesa

Učinkovito iskanje: Binarna drevesa so učinkovita pri iskanju določenega elementa, saj ima vsako vozlišče največ dve podrejeni vozlišči, kar omogoča Učinkovitost pomnilnika: Binarna drevesa potrebujejo manj pomnilnika v primerjavi z drugimi drevesnimi podatkovnimi strukturami, zato so pomnilniško učinkovita.
Binarna drevesa je razmeroma enostavno implementirati in razumeti, saj ima vsako vozlišče največ dva otroka, levega in desnega otroka.

Slabosti binarnega drevesa

Uporaba binarnega drevesa

Binarno drevo je mogoče uporabiti za predstavljajo hierarhične podatke .
Huffmanova kodirna drevesa se uporabljajo v algoritmi stiskanja podatkov .
Prednostna čakalna vrsta je še ena aplikacija binarnega drevesa, ki se uporablja za iskanje največje ali najmanjše časovne kompleksnosti O(1).
Uporabno za segmentirano indeksiranje v zbirki podatkov je koristno pri shranjevanju predpomnilnika v sistemu,
Binarna drevesa je mogoče uporabiti za implementacijo odločitvenih dreves, vrste algoritma strojnega učenja, ki se uporablja za klasifikacijo in regresijsko analizo.

Pogosta vprašanja o binarnem drevesu

1. Kaj je binarno drevo?

Binarno drevo je nelinearna podatkovna struktura, sestavljena iz vozlišč, kjer ima vsako vozlišče največ dva otroka (levega otroka in desnega otroka).

2. Katere so vrste binarnih dreves?

Binarna drevesa lahko razvrstimo v različne vrste, vključno s polnimi binarnimi drevesi, popolnimi binarnimi drevesi, popolnimi binarnimi drevesi, uravnoteženimi binarnimi drevesi (kot so drevesa AVL in rdeče-črna drevesa) in degeneriranimi (ali patološkimi) binarnimi drevesi.

3. Kakšna je višina binarnega drevesa?

Višina binarnega drevesa je dolžina najdaljše poti od korenskega vozlišča do listnega vozlišča. Predstavlja število robov na najdaljši poti od korenskega vozlišča do listnega vozlišča.

4. Kakšna je globina vozlišča v binarnem drevesu?

Globina vozlišča v binarnem drevesu je dolžina poti od korenskega vozlišča do tega določenega vozlišča. Globina korenskega vozlišča je 0.

5. Kako izvedete prečkanje drevesa v binarnem drevesu?

Prehod drevesa v binarnem drevesu je mogoče izvesti na različne načine: prehod po vrstnem redu, prehod pred naročilom, prehod po naročilu in prehod po vrstnem redu (znan tudi kot prehod najprej v širino).

6. Kaj je prehod po vrstnem redu v binarnem drevesu?

Pri prehodu po vrstnem redu so vozlišča rekurzivno obiskana v tem vrstnem redu: levi podrejeni, korenski, desni podrejeni. Posledica tega prečkanja so obiskana vozlišča v nepadajočem vrstnem redu v binarnem iskalnem drevesu.

7. Kaj je prečkanje prednaročila v binarnem drevesu?

Pri prehodu pred naročilom so vozlišča rekurzivno obiskana v tem vrstnem redu: koren, levi podrejeni, desni podrejeni. Rezultat tega prehoda je korensko vozlišče kot prvo obiskano vozlišče.

8. Kaj je prehod po naročilu v binarnem drevesu?

Pri prehodu po vrstnem redu so vozlišča rekurzivno obiskana v tem vrstnem redu: levi podrejeni, desni podrejeni in korenski. Rezultat tega prečkanja je korensko vozlišče zadnje obiskano vozlišče.

9. Kakšna je razlika med binarnim drevesom in binarnim iskalnim drevesom?

Binarno drevo je hierarhična podatkovna struktura, kjer ima vsako vozlišče največ dva otroka, medtem ko je binarno iskalno drevo vrsta binarnega drevesa, v katerem levi otrok vozlišča vsebuje vrednosti, manjše od vrednosti vozlišča, desni otrok pa vsebuje vrednosti večja od vrednosti vozlišča.

10. Kaj je uravnoteženo binarno drevo?

Uravnoteženo binarno drevo je binarno drevo, v katerem se višina levega in desnega poddrevesa vsakega vozlišča razlikujeta največ za eno. Uravnotežena drevesa pomagajo vzdrževati učinkovite operacije, kot so iskanje, vstavljanje in brisanje s časovno kompleksnostjo blizu O(log n).

Zaključek:

Drevo je hierarhična podatkovna struktura. Glavne uporabe dreves vključujejo vzdrževanje hierarhičnih podatkov, zagotavljanje zmernega dostopa in operacije vstavljanja/brisanja. Binarna drevesa so posebni primeri drevesa, kjer ima vsako vozlišče največ dva otroka.

Povezani članki:

Lastnosti binarnega drevesa
Vrste binarnega drevesa

TechCodeview

Uvod v binarno drevo – Vadnice za strukturo podatkov in algoritme