logo

TechCodeview

Inleiding tot binaire boom – Tutorials voor gegevensstructuur en algoritmen

Binaire boom is een niet-lineaire datastructuur waarbij elk knooppunt maximaal twee kinderen heeft. In dit artikel behandelen we alle basisprincipes van Binary Tree, bewerkingen op Binary Tree, de implementatie ervan, voordelen en nadelen die u zullen helpen alle problemen op basis van Binary Tree op te lossen.

Inhoudsopgave



Wat is binaire boom?

Binaire boom is a boomdatastructuur (niet-lineair) waarin elk knooppunt kan hebben maximaal twee kinderen die worden aangeduid als de linker kind en de juiste kind .

Het bovenste knooppunt in een binaire boom wordt de wortel , en de onderste knooppunten worden aangeroepen bladeren . Een binaire boom kan worden gevisualiseerd als een hiërarchische structuur met de wortel bovenaan en de bladeren onderaan.

Vertegenwoordiging van binaire boom

Elk knooppunt in een binaire boom bestaat uit drie delen:



  • Gegevens
  • Wijzer naar het linker kind
  • Wijzer naar het juiste kind

Hieronder ziet u de weergave van een knooppunt van een binaire boom in verschillende talen:

C++ 
// Use any below method to implement Nodes of tree // Method 1: Using 'struct' to make // user-define data type struct node {  int data;  struct node* left;  struct node* right; }; // Method 2: Using 'class' to make // user-define data type class Node { public:  int data;  Node* left;  Node* right; };>
C 
// Structure of each node of the tree struct node {  int data;  struct node* left;  struct node* right; };>
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>
C# 
// Class containing left and right child // of current node and key value class Node {  int key;  Node left, right;  public Node(int item)  {  key = item;  left = right = null;  } }>
JavaScript 
>

Soorten binaire boom

Binaire boom kan worden ingedeeld in veelvoudstypen op basis van meerdere factoren:



Bewerkingen op binaire boom

1. Invoeging in binaire boom

We kunnen overal in een binaire boom een ​​knooppunt invoegen door het knooppunt in te voegen als het linker- of rechterkind van een willekeurig knooppunt of door het knooppunt als wortel van de boom te maken.

Algoritme om een ​​knooppunt in een binaire boom in te voegen:

  • Controleer of er een knooppunt in de binaire boom is waarin het linkerkind ontbreekt. Als zo'n knooppunt bestaat, voegt u het nieuwe knooppunt in als het linkerkind.
  • Controleer of er een knooppunt in de binaire boom is waarvan het rechterkind ontbreekt. Als zo'n knooppunt bestaat, voegt u het nieuwe knooppunt in als het rechterkind.
  • Als we geen enkel knooppunt vinden waarvan het linker- of rechterkind ontbreekt, zoek dan het knooppunt waarbij beide kinderen ontbreken en voeg het knooppunt in als het linker- of rechterkind.

2. Doorkruising van binaire boom

Bij het doorlopen van de binaire boom worden alle knooppunten van de binaire boom bezocht. Tree Traversal-algoritmen kunnen grofweg in twee categorieën worden ingedeeld:

  • Diepte-eerst zoeken (DFS)-algoritmen
  • Breadth-First Search (BFS)-algoritmen

Depth-First Search (DFS)-algoritmen:

  • Traversal vooraf bestellen (huidig-links-rechts): Bezoek het huidige knooppunt voordat u knooppunten in de linker- of rechtersubstructuur bezoekt. Hier is de doorgang wortel – linkerkind – rechterkind. Het betekent dat eerst het wortelknooppunt wordt doorlopen, daarna het linkerkind en ten slotte het rechterkind.
  • Inorder Traversal (links-huidig-rechts): Bezoek het huidige knooppunt nadat u alle knooppunten in de linker subboom heeft bezocht, maar voordat u een knooppunt in de rechter subboom bezoekt. Hier is de doorgang het linkerkind – de wortel – het rechterkind. Het betekent dat eerst het linkerkind wordt doorlopen, daarna het wortelknooppunt en ten slotte het rechterkind.
  • Postorder Traversal (links-rechts-stroom): Bezoek het huidige knooppunt nadat u alle knooppunten van de linker- en rechtersubboom hebt bezocht. Hier is de doorgang linkerkind – rechterkind – wortel. Het betekent dat het linkerkind eerst het rechterkind heeft gepasseerd en uiteindelijk het wortelknooppunt.

Breadth-First Search (BFS)-algoritmen:

  • Niveauordertransactie: Bezoek knooppunten niveau voor niveau en van links naar rechts op hetzelfde niveau. Hier is de verplaatsing niveaugewijs. Het betekent dat het meest linkse kind het eerst is overgestoken en daarna de andere kinderen van hetzelfde niveau van links naar rechts zijn overgestoken.

3. Verwijdering in binaire boom

We kunnen elk knooppunt in de binaire boom verwijderen en de knooppunten na verwijdering opnieuw rangschikken om opnieuw een geldige binaire boom te vormen.

Algoritme om een ​​knooppunt in een binaire boom te verwijderen:

  • Begin bij de wortel en zoek het diepste en meest rechtse knooppunt in de binaire boom en het knooppunt dat we willen verwijderen.
  • Vervang de gegevens van het meest rechtse knooppunt door het knooppunt dat moet worden verwijderd.
  • Verwijder vervolgens het diepste meest rechtse knooppunt.

4. Zoeken in binaire boom

We kunnen naar een element in het knooppunt zoeken met behulp van een van de traversale technieken.

Algoritme om een ​​knooppunt in een binaire boom te zoeken:

  • Begin vanaf het hoofdknooppunt.
  • Controleer of de waarde van het huidige knooppunt gelijk is aan de doelwaarde.
  • Als de waarde van het huidige knooppunt gelijk is aan de doelwaarde, dan is dit knooppunt het vereiste knooppunt.
  • Anders, als de waarde van het knooppunt niet gelijk is aan de doelwaarde, start u de zoekopdracht in het linker- en rechterkind.
  • Als we geen knooppunt vinden waarvan de waarde gelijk is aan het doel, dan is de waarde niet aanwezig in de boom.

Hulpbewerkingen op binaire boom

Implementatie van binaire boom

Hieronder vindt u de code voor het invoegen, verwijderen en doorlopen van de binaire boom:

C 
#include  // Node structure to define the structure of the node typedef struct Node {  int data;  struct Node *left, *right; } Node; // Function to create a new node Node* newNode(int val) {  Node* temp = (Node*)malloc(sizeof(Node));  temp->gegevens = waarde;  temp->links = temp->rechts = NULL;  retourtemperatuur; } // Functie voor het invoegen van knooppunten Node* insert(Node* root, int data) {// Als de boom leeg is, wordt het nieuwe knooppunt de root if (root == NULL) { root = newNode(data);  retourwortel;  } // Wachtrij om de boom te doorkruisen en de positie te vinden om het knooppunt Node* wachtrij [100] in te voegen;  int voorkant = 0, achterkant = 0;  wachtrij[achter++] = root;  while (voorkant!= achterkant) { Node* temp = wachtrij[voor++];  // Voeg een knooppunt in als het linkerkind van het bovenliggende knooppunt if (temp->left == NULL) { temp->left = newNode(data);  pauze;  } // Als het linkerkind niet null is, duw het dan naar de wachtrij else wachtrij[rear++] = temp->left;  // Voeg een knooppunt in als het juiste kind van het bovenliggende knooppunt if (temp->right == NULL) { temp->right = newNode(data);  pauze;  } // Als het juiste kind niet null is, duw het dan naar de wachtrij else wachtrij[rear++] = temp->right;  } return root; } /* Functie om het opgegeven diepste knooppunt (d_node) in de binaire boom te verwijderen */ void deleteDeepest(Node* root, Node* d_node) { Node* wachtrij[100];  int voorkant = 0, achterkant = 0;  wachtrij[achter++] = root;  // Voer niveauvolgorde uit tot het laatste knooppunt Node* temp;  while (voorkant!= achterkant) { temp = wachtrij[voor++];  if (temp == d_node) {temp = NULL;  gratis(d_knooppunt);  opbrengst;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  gratis(d_knooppunt);  opbrengst;  } else wachtrij[achter++] = temp->rechts;  } if (temp->left) { if (temp->left == d_node) { temp->left = NULL;  gratis(d_knooppunt);  opbrengst;  } else wachtrij[achter++] = temp->links;  } } } /* Functie om element in binaire boom te verwijderen */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == sleutel) return NULL;  anders retourneert root;  } Knooppunt* wachtrij[100];  int voorkant = 0, achterkant = 0;  wachtrij[achter++] = root;  Knooppunt* temperatuur;  Knooppunt* sleutel_knooppunt = NULL;  // Voer een niveauvolgorde uit om het diepste knooppunt (temp) en het knooppunt dat moet worden verwijderd (key_node) te vinden terwijl (voorkant!= achter) { temp = wachtrij[voor++];  if (temp->data == sleutel) key_node = temp;  if (temp->left) wachtrij[achter++] = temp->left;  if (temp->right) wachtrij[achter++] = temp->right;  } if (key_node != NULL) { int x = temp->data;  key_node->gegevens = x;  verwijderDeepest(root, temp);  } return root; } // Inorder tree traversal (Links - Root - Rechts) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(root->links);  printf('%d ', root->data);  inorderTraversal(root->rechts); } // Tree traversal vooraf bestellen (Root - Links - Rechts) void preorderTraversal(Node* root) { if (!root) return;  printf('%d ', root->data);  preorderTraversal(root->links);  preorderTraversal(root->right); } // Postorder tree traversal (Links - Rechts - Root) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(root->links);  postorderTraversal(root->right);  printf('%d ', root->data); } // Functie voor het doorlopen van boomstructuren op niveau void levelorderTraversal(Node* root) { if (root == NULL) return;  // Wachtrij voor het doorlopen van niveauvolgorde Node* wachtrij [100];  int voorkant = 0, achterkant = 0;  wachtrij[achter++] = root;  while (voorkant!= achterkant) { Node* temp = wachtrij[voor++];  printf('%d ', temp->data);  // Duw het linker kind in de wachtrij als (temp->left) wachtrij[achter++] = temp->left;  // Duw het rechter kind in de wachtrij als (temp->right) wachtrij[achter++] = temp->right;  } } /* Stuurprogrammafunctie om het bovenstaande algoritme te controleren. */ int main() { Knooppunt* root = NULL;  // Invoegen van knooppunten root = insert(root, 10);  wortel = invoegen(wortel, 20);  wortel = invoegen(wortel, 30);  wortel = invoegen(wortel, 40);  printf('Voorbestelling doorlopen: ');  preorderTraversal(root);  printf('
In volgorde doorlopen: ');  inorderTraversal(root);  printf('
Postorderdoorloop: ');  postorderTraversal(root);  printf('
Niveauvolgorde doorlopen: ');  niveauvolgordeTraversal(root);  // Verwijder het knooppunt met data = 20 root = deletion(root, 20);  printf('
In volgorde doorlopen na verwijdering: ');  inorderTraversal(root);  retour 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 = nieuwe LinkedList();  q.aanbieding(root);  while (!q.isEmpty()) { Knooppunttemperatuur = q.poll();  // Voeg een knooppunt in als het linkerkind van het bovenliggende knooppunt if (temp.left == null) {temp.left = new Node(data);  pauze;  } // Als het linkerkind niet null is, duw het dan naar de // wachtrij else q.offer(temp.left);  // Voeg een knooppunt in als het rechterkind van het bovenliggende knooppunt if (temp.right == null) {temp.right = new Node(data);  pauze;  } // Als het juiste kind niet null is, duw het dan naar de // wachtrij else q.offer(temp.right);  } return root;  } /* functie om het opgegeven diepste knooppunt (d_node) in de binaire boom te verwijderen */ public static void deletDeepest(Node root, Node d_node) { Queueq = nieuwe LinkedList();  q.aanbieding(root);  // Voer niveauvolgorde uit tot het laatste knooppunt Knooppunttemperatuur;  terwijl (!q.isEmpty()) { temp = q.poll();  if (temp == d_node) {temp = null;  d_knooppunt = nul;  opbrengst;  } if (temp.right!= null) { if (temp.right == d_node) { temp.right = null;  d_knooppunt = nul;  opbrengst;  } anders q.offer(temp.right);  } if (temp.left!= null) { if (temp.left == d_node) { temp.left = null;  d_knooppunt = nul;  opbrengst;  } anders q.offer(temp.left);  } } } /* functie om element in binaire boom te verwijderen */ openbare statische knooppuntverwijdering (knooppuntroot, int-sleutel) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == sleutel) return null;  anders retourneer root;  }  Wachtrijq = nieuwe LinkedList();  q.aanbieding(root);  Knooppunttemperatuur = nieuw knooppunt (0);  Knooppunt sleutel_knooppunt = nul;  // Voer een niveauvolgorde uit om de diepste // node(temp) en node te verwijderen (key_node) while (!q.isEmpty()) { temp = q.poll();  if (temp.data == sleutel) 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;  sleutel_knooppunt.data = x;  verwijderDeepest(root, temp);  } return root;  } // Inorder tree traversal (Links - Root - Rechts) public static void inorderTraversal(Node root) { if (root == null) return;  inorderTraversal(root.left);  Systeem.uit.print(root.data + ' ');  inorderTraversal(root.right);  } // Tree traversal vooraf bestellen (Root - Links - Rechts) public static void preorderTraversal (Node root) { if (root == null) return;  Systeem.uit.print(root.data + ' ');  preorderTraversal(root.left);  preorderTraversal(root.right);  } // Postorder tree traversal (Links - Rechts - Root) public static void postorderTraversal(Node root) { if (root == null) return;  postorderTraversal(root.left);  postorderTraversal(root.right);  Systeem.uit.print(root.data + ' ');  } // Functie voor boomdoorgang op niveauvolgorde public static void levelorderTraversal(Node root) { if (root == null) return;  // Wachtrij voor het doorlopen van niveauvolgorde. Wachtrijq = nieuwe LinkedList();  q.aanbieding(root);  while (!q.isEmpty()) { Knooppunttemperatuur = q.poll();  Systeem.uit.afdruk(temp.data + ' ');  // Duw het linker kind in de wachtrij if (temp.left != null) q.offer(temp.left);  // Duw het juiste kind in de wachtrij if (temp.right != null) q.offer(temp.right);  } } /* Stuurprogrammafunctie om het bovenstaande algoritme te controleren. */ public static void main(String[] args) { Node root = null;  // Invoegen van knooppunten root = insert(root, 10);  wortel = invoegen(wortel, 20);  wortel = invoegen(wortel, 30);  wortel = invoegen(wortel, 40);  System.out.print('Voorbestelling doorlopen: ');  preorderTraversal(root);  System.out.print('
In volgorde doorlopen: ');  inorderTraversal(root);  System.out.print('
Postorderdoorloop: ');  postorderTraversal(root);  System.out.print('
Niveauvolgorde doorlopen: ');  niveauvolgordeTraversal(root);  // Verwijder het knooppunt met data = 20 root = deletion(root, 20);  System.out.print('
In volgorde doorlopen na verwijdering: ');  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)>
C# 
using System; using System.Collections.Generic; // Node class to define the structure of the node public class Node {  public int data;  public Node left, right;  // Parameterized Constructor  public Node(int val)  {  data = val;  left = right = null;  } } public class Program {  // Function to insert nodes  public static Node Insert(Node root, int data)  {  // If tree is empty, new node becomes the root  if (root == null)  {  root = new Node(data);  return root;  }  // Queue to traverse the tree and find the position to insert the node  Queueq = nieuwe wachtrij();  q.Enqueue(root);  while (q.Count != 0) { Knooppunttemperatuur = q.Dequeue();  // Voeg een knooppunt in als het linkerkind van het bovenliggende knooppunt if (temp.left == null) {temp.left = new Node(data);  pauze;  } // Als het linkerkind niet null is, duw het dan naar de wachtrij. q.Enqueue(temp.left);  // Voeg een knooppunt in als het rechterkind van het bovenliggende knooppunt if (temp.right == null) {temp.right = new Node(data);  pauze;  } // Als het juiste kind niet null is, duw het dan naar de wachtrij anders q.Enqueue(temp.right);  } return root;  } /* functie om het opgegeven diepste knooppunt (d_node) in de binaire boom te verwijderen */ public static void DeleteDeepest(Node root, Node d_node) { Queueq = nieuwe wachtrij();  q.Enqueue(root);  // Voer niveauvolgorde uit tot het laatste knooppunt Knooppunttemperatuur;  terwijl (q.Count != 0) { temp = q.Dequeue();  if (temp == d_node) {temp = null;  d_knooppunt = nul;  opbrengst;  } if (temp.right!= null) { if (temp.right == d_node) { temp.right = null;  d_knooppunt = nul;  opbrengst;  } anders q.Enqueue(temp.right);  } if (temp.left!= null) { if (temp.left == d_node) { temp.left = null;  d_knooppunt = nul;  opbrengst;  } anders q.Enqueue(temp.left);  } } } /* functie om element in binaire boom te verwijderen */ public static Node Deletion(Node root, int key) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == sleutel) return null;  anders retourneer root;  }  Wachtrijq = nieuwe wachtrij();  q.Enqueue(root);  Knooppunttemperatuur = nieuw knooppunt (0);  Knooppunt sleutel_knooppunt = nul;  // Voer een niveauvolgorde uit om het diepste knooppunt (temp) en het knooppunt dat moet worden verwijderd (key_node) te vinden terwijl (q.Count != 0) { temp = q.Dequeue();  if (temp.data == sleutel) 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;  sleutel_knooppunt.data = x;  VerwijderDeepest(root, temp);  } return root;  } // Inorder tree traversal (Links - Root - Rechts) public static void InorderTraversal(Node root) { if (root == null) return;  InorderTraversal(root.left);  Console.Write(root.data + '');  InorderTraversal(root.right);  } // Tree traversal vooraf bestellen (Root - Links - Rechts) public static void PreorderTraversal (Node root) { if (root == null) return;  Console.Write(root.data + '');  PreorderTraversal(root.left);  PreorderTraversal(root.right);  } // Postorder tree traversal (Links - Rechts - Root) public static void PostorderTraversal(Node root) { if (root == null) return;  PostorderTraversal(root.left);  PostorderTraversal(root.right);  Console.Write(root.data + '');  } // Functie voor boomdoorgang op niveauvolgorde public static void LevelorderTraversal(Node root) { if (root == null) return;  // Wachtrij voor het doorlopen van niveauvolgorde. Wachtrijq = nieuwe wachtrij();  q.Enqueue(root);  while (q.Count != 0) { Knooppunttemperatuur = q.Dequeue();  Console.Write(temp.data + '');  // Duw het linker kind in de wachtrij if (temp.left != null) q.Enqueue(temp.left);  // Duw het rechter kind in de wachtrij if (temp.right != null) q.Enqueue(temp.right);  } } /* Stuurprogrammafunctie om het bovenstaande algoritme te controleren. */ public static void Main(string[] args) { Node root = null;  // Invoegen van knooppunten root = Insert(root, 10);  wortel = Invoegen(wortel, 20);  wortel = Invoegen(wortel, 30);  wortel = Invoegen(wortel, 40);  Console.Write('Voorbestelling doorlopen: ');  PreorderTraversal(root);  Console.Write('
In volgorde doorlopen: ');  InorderTraversal(root);  Console.Write('
Postorderdoorloop: ');  PostorderTraversal(root);  Console.Write('
Niveauvolgorde doorlopen: ');  NiveauvolgordeTraversal(root);  // Verwijder het knooppunt met data = 20 root = Deletion(root, 20);  Console.Write('
In volgorde doorlopen na verwijdering: ');  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);  while (!q.empty()) { Knooppunt* temp = q.front();  q.pop();  // Voeg een knooppunt in als het linkerkind van het bovenliggende knooppunt if (temp->left == NULL) { temp->left = new Node(data);  pauze;  } // Als het linkerkind niet null is, duw het dan naar de // wachtrij else q.push(temp->left);  // Voeg een knooppunt in als het juiste kind van het bovenliggende knooppunt if (temp->right == NULL) { temp->right = new Node(data);  pauze;  } // Als het juiste kind niet null is, duw het dan naar de // wachtrij else q.push(temp->right);  } return root; } /* functie om het opgegeven diepste knooppunt (d_node) in de binaire boom te verwijderen */ void deleteDeepest(Node* root, Node* d_node) { wachtrijQ;  q.push(root);  // Voer niveauvolgorde uit tot het laatste knooppunt Node* temp;  terwijl (!q.empty()) { temp = q.front();  q.pop();  if (temp == d_node) {temp = NULL;  verwijderen (d_node);  opbrengst;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  verwijderen (d_node);  opbrengst;  } anders q.push(temp->rechts);  } if (temp->left) { if (temp->left == d_node) { temp->left = NULL;  verwijderen (d_node);  opbrengst;  } anders q.push(temp->links);  } } } /* functie om element in binaire boom te verwijderen */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == sleutel) return NULL;  anders retourneert root;  }  wachtrijQ;  q.push(root);  Knooppunt* temperatuur;  Knooppunt* sleutel_knooppunt = NULL;  // Voer een niveauvolgorde uit om de diepste // node(temp) en node te verwijderen (key_node) while (!q.empty()) { temp = q.front();  q.pop();  if (temp->data == sleutel) key_node = temp;  if (temp->links) q.push(temp->links);  if (temp->goed) q.push(temp->goed);  } if (key_node != NULL) { int x = temp->data;  key_node->gegevens = x;  verwijderDeepest(root, temp);  } return root; } // Inorder tree traversal (Links - Root - Rechts) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(root->links);  uit<< root->gegevens<< ' ';  inorderTraversal(root->rechts); } // Tree traversal vooraf bestellen (Root - Links - Rechts) void preorderTraversal(Node* root) { if (!root) return;  uit<< root->gegevens<< ' ';  preorderTraversal(root->links);  preorderTraversal(root->right); } // Postorder tree traversal (Links - Rechts - Root) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(root->links);  postorderTraversal(root->right);  uit<< root->gegevens<< ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) {  if (root == NULL)  return;  // Queue for level order traversal  queueQ;  q.push(root);  while (!q.empty()) { Knooppunt* temp = q.front();  q.pop();  uit<< temp->gegevens<< ' ';  // Push left child in the queue  if (temp->links) q.push(temp->links);  // Duw het rechterkind in de wachtrij if (temp->right) q.push(temp->right);  } } /* Stuurprogrammafunctie om het bovenstaande algoritme te controleren. */ int main() { Knooppunt* root = NULL;  // Invoegen van knooppunten root = insert(root, 10);  wortel = invoegen(wortel, 20);  wortel = invoegen(wortel, 30);  wortel = invoegen(wortel, 40);  uit<< '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); }>
Uitvoer 
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>

Complexiteitsanalyse van binaire boombewerkingen

Activiteiten Tijdcomplexiteit

Ruimtecomplexiteit

volledige vorm van i d e
Plaatsing OP)

OP)

Traversal vooraf bestellen OP)

OP)

Inorder-traversal

OP)

OP)

Traversatie van postordersOP)

OP)

Traversatie van niveauordersOP)

OP)

Verwijdering

OP)

OP)

Zoeken

OP)

OP)

We kunnen gebruiken Morris Traversal om alle knooppunten van de binaire boom in O(1) tijd te doorkruisen.

Voordelen van binaire boom

Nadelen van binaire boom

Toepassingen van binaire boom

Veelgestelde vragen over binaire boom

1. Wat is een binaire boom?

Een binaire boom is een niet-lineaire datastructuur bestaande uit knooppunten, waarbij elk knooppunt maximaal twee kinderen heeft (het linkerkind en het rechterkind).

2. Wat zijn de soorten binaire bomen?

Binaire bomen kunnen worden ingedeeld in verschillende typen, waaronder volledige binaire bomen, complete binaire bomen, perfecte binaire bomen, gebalanceerde binaire bomen (zoals AVL-bomen en rood-zwarte bomen) en gedegenereerde (of pathologische) binaire bomen.

3. Wat is de hoogte van een binaire boom?

De hoogte van een binaire boom is de lengte van het langste pad van het wortelknooppunt naar een bladknooppunt. Het vertegenwoordigt het aantal randen in het langste pad van het hoofdknooppunt naar een bladknooppunt.

4. Wat is de diepte van een knooppunt in een binaire boom?

De diepte van een knooppunt in een binaire boom is de lengte van het pad van het hoofdknooppunt naar dat specifieke knooppunt. De diepte van het wortelknooppunt is 0.

5. Hoe voer je boomtraversal uit in een binaire boom?

Het doorkruisen van bomen in een binaire boom kan op verschillende manieren worden gedaan: doorkruisen in volgorde, doorkruisen vóór bestelling, doorkruisen na bestelling en doorkruisen op niveau (ook wel breedte-eerst doorkruisen genoemd).

6. Wat is een inorder-traversal in binaire boom?

Bij Inorder-traversal worden knooppunten recursief bezocht in deze volgorde: linkerkind, wortel, rechterkind. Deze doorgang resulteert erin dat knooppunten worden bezocht in een niet-afnemende volgorde in een binaire zoekboom.

7. Wat is een Preorder-traversal in Binary Tree?

Bij Preorder-traversal worden knooppunten recursief bezocht in deze volgorde: wortel, linkerkind, rechterkind. Deze doorgang resulteert erin dat het hoofdknooppunt het eerste knooppunt is dat wordt bezocht.

8. Wat is een postorder-traversal in binaire boom?

Bij Postorder-traversal worden knooppunten recursief bezocht in deze volgorde: linkerkind, rechterkind en wortel. Deze doorgang resulteert erin dat het hoofdknooppunt het laatste knooppunt is dat wordt bezocht.

verwijder het eerste teken excel

9. Wat is het verschil tussen een binaire boom en een binaire zoekboom?

Een binaire boom is een hiërarchische gegevensstructuur waarbij elk knooppunt maximaal twee kinderen heeft, terwijl een binaire zoekboom een ​​soort binaire boom is waarin het linkerkind van een knooppunt waarden bevat die kleiner zijn dan de waarde van het knooppunt, en het rechterkind waarden bevat. groter dan de waarde van het knooppunt.

10. Wat is een gebalanceerde binaire boom?

Een gebalanceerde binaire boom is een binaire boom waarin de hoogte van de linker en rechter subboom van elk knooppunt maximaal één verschilt. Gebalanceerde bomen helpen bij het handhaven van efficiënte bewerkingen zoals zoeken, invoegen en verwijderen met tijdscomplexiteiten die dicht bij O(log n) liggen.

Conclusie:

Boom is een hiërarchische gegevensstructuur. De belangrijkste toepassingen van bomen zijn onder meer het onderhouden van hiërarchische gegevens, het bieden van gematigde toegang en invoeg-/verwijderingsbewerkingen. Binaire bomen zijn speciale gevallen van bomen waarbij elk knooppunt maximaal twee kinderen heeft.

Gerelateerde artikelen:

  • Eigenschappen van binaire boom
  • Soorten binaire boom