logo

TechCodeview

Úvod do binárního stromu – výukové programy pro datovou strukturu a algoritmus

Binární strom je nelineární datová struktura kde každý uzel má nejvýše dvě děti. V tomto článku pokryjeme všechny základy binárního stromu, operace s binárním stromem, jeho implementaci, výhody a nevýhody, které vám pomohou vyřešit všechny problémy založené na binárním stromu.

Obsah



Co je binární strom?

Binární strom je a stromová datová struktura (nelineární) ve kterém může mít každý uzel maximálně dvě děti které jsou označovány jako levé dítě a správné dítě .

Nejvyšší uzel v binárním stromě se nazývá vykořenit a jsou volány nejspodnější uzly listy . Binární strom lze zobrazit jako hierarchickou strukturu s kořenem nahoře a listy dole.

Reprezentace binárního stromu

Každý uzel v binárním stromu má tři části:



  • Data
  • Ukazatel na levé dítě
  • Ukazatel na správné dítě

Níže je znázorněna reprezentace uzlu binárního stromu v různých jazycích:

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; };>
Jáva 
// 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;  } }>
Krajta 
# 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 
>

Typy binárních stromů

Binární strom lze klasifikovat do několika typů na základě více faktorů:



Operace Na Binárním Stromu

1. Vložení do binárního stromu

Uzel můžeme vložit kamkoli do binárního stromu vložením uzlu jako levého nebo pravého potomka libovolného uzlu nebo tím, že uzel učiníme kořenem stromu.

Algoritmus pro vložení uzlu do binárního stromu:

  • Zkontrolujte, zda je v binárním stromu uzel, kterému chybí levé potomky. Pokud takový uzel existuje, vložte nový uzel jako jeho levého potomka.
  • Zkontrolujte, zda je v binárním stromu uzel, kterému chybí pravé potomstvo. Pokud takový uzel existuje, vložte nový uzel jako jeho pravý potomek.
  • Pokud nenajdeme žádný uzel s chybějícím levým nebo pravým potomkem, pak najděte uzel, ve kterém chybí oba potomci, a vložte uzel jako jeho levé nebo pravé potomky.

2. Procházení binárního stromu

Procházení binárního stromu zahrnuje návštěvu všech uzlů binárního stromu. Algoritmy procházení stromů lze obecně rozdělit do dvou kategorií:

  • Algoritmy hloubkového vyhledávání (DFS).
  • Algoritmy BFS (Breadth-First Search).

Algoritmy hloubkového vyhledávání (DFS):

  • Předobjednávka Traversal (aktuální-levá-pravá): Než navštívíte jakýkoli uzel v levém nebo pravém podstromu, navštivte aktuální uzel. Zde je přechod kořen – levé dítě – pravé dítě. To znamená, že nejprve projde kořenový uzel, poté jeho levý potomek a nakonec pravý potomek.
  • Průjezd v pořadí (levý-proud-pravý): Navštivte aktuální uzel po návštěvě všech uzlů v levém podstromu, ale před návštěvou jakéhokoli uzlu v pravém podstromu. Zde je přechodem levé dítě – kořen – pravé dítě. To znamená, že nejprve prochází levé dítě, potom jeho kořenový uzel a nakonec pravé dítě.
  • Postorder Traversal (levo-pravý-proud): Po návštěvě všech uzlů levého a pravého podstromu navštivte aktuální uzel. Zde je přechodem levé dítě – pravé dítě – kořen. To znamená, že nejprve prošlo levé dítě, poté pravé dítě a nakonec jeho kořenový uzel.

Algoritmy BFS (Breadth-First Search):

  • Procházení objednávky úrovně: Navštivte uzly úroveň po úrovni a způsobem zleva doprava na stejné úrovni. Zde je procházení rovinné. To znamená, že dítě, které je nejvíce vlevo, prošlo jako první a poté ostatní děti stejné úrovně zleva doprava prošly.

3. Vymazání v binárním stromu

Můžeme smazat libovolný uzel v binárním stromě a po smazání přeuspořádat uzly tak, aby opět tvořily platný binární strom.

Algoritmus pro odstranění uzlu v binárním stromu:

  • Začněte u kořene a najděte nejhlubší a nejpravější uzel v binárním stromě a uzel, který chceme odstranit.
  • Nahraďte data nejhlubšího pravého uzlu uzlem, který chcete odstranit.
  • Potom odstraňte nejhlubší uzel vpravo.

4. Vyhledávání v binárním stromu

Prvek v uzlu můžeme vyhledat pomocí libovolné techniky procházení.

Algoritmus pro vyhledávání uzlu v binárním stromu:

  • Začněte od kořenového uzlu.
  • Zkontrolujte, zda se hodnota aktuálního uzlu rovná cílové hodnotě.
  • Pokud je hodnota aktuálního uzlu rovna cílové hodnotě, pak je tento uzel požadovaným uzlem.
  • V opačném případě, pokud se hodnota uzlu nerovná cílové hodnotě, spusťte vyhledávání v levém a pravém potomku.
  • Pokud nenajdeme žádný uzel, jehož hodnota je rovna cílové, pak hodnota není ve stromu přítomna.

Pomocné Operace Na Binárním Stromu

Implementace binárního stromu

Níže je uveden kód pro vkládání, mazání a procházení binárního stromu:

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->data = val;  temp->left = temp->right = NULL;  návratová teplota; } // Funkce pro vložení uzlů Node* insert(Node* root, int data) { // Pokud je strom prázdný, nový uzel se stane kořenem if (root == NULL) { root = newNode(data);  vrátit kořen;  } // Fronta pro procházení stromu a nalezení pozice pro vložení uzlu Node* queue[100];  vnitřní přední = 0, zadní = 0;  fronta[zadni++] = root;  while (přední != zadní) { Node* temp = fronta[front++];  // Vloží uzel jako levého potomka nadřazeného uzlu if (temp->left == NULL) { temp->left = newNode(data);  přestávka;  } // Pokud levý potomek není null, pošle ho do fronty else queue[rear++] = temp->left;  // Vložit uzel jako pravého potomka nadřazeného uzlu if (temp->right == NULL) { temp->right = newNode(data);  přestávka;  } // Pokud pravý potomek není null, pošle ho do fronty else queue[rear++] = temp->right;  } return root; } /* Funkce pro smazání daného nejhlubšího uzlu (d_uzel) v binárním stromě */ void deletDeepest(Node* root, Node* d_node) { Node* queue[100];  vnitřní přední = 0, zadní = 0;  fronta[zadni++] = root;  // Provede procházení pořadí úrovní až do posledního uzlu Node* temp;  while (přední != zadní) { temp = fronta[front++];  if (temp == d_uzel) { temp = NULL;  free(d_uzel);  vrátit se;  } if (temp->vpravo) { if (temp->vpravo == d_uzel) { temp->vpravo = NULL;  free(d_uzel);  vrátit se;  } else queue[zadni++] = temp->vpravo;  } if (temp->left) { if (temp->left == d_uzel) { temp->left = NULL;  free(d_uzel);  vrátit se;  } else queue[zadní++] = temp->left;  } } } /* Funkce pro odstranění prvku v binárním stromu */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL;  jinak vrátit kořen;  } Uzel* fronta[100];  vnitřní přední = 0, zadní = 0;  fronta[zadni++] = root;  Node* temp;  Uzel* klíč_uzel = NULL;  // Proveďte procházení pořadím úrovní, abyste našli nejhlubší uzel (temp) a uzel, který má být smazán (key_node) while (front != zadní) { temp = queue[front++];  if (temp->data == klíč) key_node = temp;  if (temp->left) queue[zadní++] = temp->left;  if (temp->right) queue[zadní++] = temp->right;  } if (klíč_uzel != NULL) { int x = temp->data;  klíč_uzel->data = x;  deletDeepest(kořen, teplota);  } return root; } // Procházení stromem pořadí (Left - Root - Right) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(root->left);  printf('%d ', root->data);  inorderTraversal(root->right); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return;  printf('%d ', root->data);  preorderTraversal(root->left);  preorderTraversal(root->right); } // Procházení stromem postorderu (Left - Right - Root) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(root->left);  postorderTraversal(root->right);  printf('%d ', root->data); } // Funkce pro procházení stromu pořadí úrovní void levelorderTraversal(Uzel* root) { if (kořen == NULL) return;  // Fronta pro průchod pořadím úrovně Uzel* fronta[100];  vnitřní přední = 0, zadní = 0;  fronta[zadni++] = root;  while (přední != zadní) { Node* temp = fronta[front++];  printf('%d ', temp->data);  // Push levého potomka ve frontě if (temp->left) queue[rear++] = temp->left;  // Push right child ve frontě if (temp->right) queue[rear++] = temp->right;  } } /* Funkce ovladače pro kontrolu výše uvedeného algoritmu. */ int main() { Uzel* root = NULL;  // Vložení uzlů root = insert(root, 10);  root = insert(kořen, 20);  root = insert(kořen, 30);  root = insert(kořen, 40);  printf('Přechod předobjednávky: ');  preorderTraversal(root);  printf('
Pořadí procházení: ');  inorderTraversal(kořen);  printf('
Postorder traversal: ');  postorderTraversal(root);  printf('
Přechod pořadím úrovně: ');  levelorderTraversal(kořen);  // Smaže uzel s daty = 20 root = deletion(root, 20);  printf('
Pořadí procházení po smazání: ');  inorderTraversal(kořen);  návrat 0; }>
Jáva 
import java.util.LinkedList; import java.util.Queue; // Node class to define the structure of the node class Node {  int data;  Node left, right;  // Parameterized Constructor  Node(int val) {  data = val;  left = right = null;  } } public class BinaryTree {  // Function to insert nodes  public static Node insert(Node root, int data) {  // If tree is empty, new node becomes the root  if (root == null) {  root = new Node(data);  return root;  }  // Queue to traverse the tree and find the position to  // insert the node  Queueq = new LinkedList();  q.offer(kořen);  while (!q.isEmpty()) { Node temp = q.poll();  // Vložit uzel jako levého potomka nadřazeného uzlu if (temp.left == null) { temp.left = new Node(data);  přestávka;  } // Pokud levý potomek není null, pošle ho do // fronty else q.offer(temp.left);  // Vložit uzel jako pravého potomka nadřazeného uzlu if (temp.right == null) { temp.right = new Node(data);  přestávka;  } // Pokud správný potomek není null, pošle ho do // fronty else q.offer(temp.right);  } return root;  } /* funkce pro odstranění daného nejhlubšího uzlu (d_uzel) v binárním stromu */ public static void deletDeepest(kořen uzlu, uzel d_uzel) { Queueq = new LinkedList();  q.offer(kořen);  // Provede procházení pořadí úrovní až do posledního uzlu Teplota uzlu;  while (!q.isEmpty()) { temp = q.poll();  if (temp == d_uzel) { temp = null;  d_uzel = null;  vrátit se;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_uzel = null;  vrátit se;  } else q.offer(temp.right);  } if (temp.left != null) { if (temp.left == d_uzel) { temp.left = null;  d_uzel = null;  vrátit se;  } else q.offer(temp.left);  } } } /* funkce pro odstranění prvku v binárním stromu */ public static Odstranění uzlu (kořen uzlu, klíč int) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == klíč) return null;  jinak vrátit kořen;  } Frontaq = new LinkedList();  q.offer(kořen);  Teplota uzlu = new Node(0);  Uzel klíč_uzel = null;  // Proveďte procházení pořadím úrovní za účelem nalezení nejhlubšího // node(temp) a uzlu, který má být smazán (key_node) while (!q.isEmpty()) { temp = q.poll();  if (temp.data == klíč) key_node = temp;  if (temp.left != null) q.offer(temp.left);  if (temp.right != null) q.offer(temp.right);  } if (uzel_klíče != null) { int x = temp.data;  key_node.data = x;  deletDeepest(kořen, temp);  } return root;  } // Procházení stromem pořadí (Left - Root - Right) 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);  } // Procházení stromu postorderu (Left - Right - Root) public static void postorderTraversal(Node root) { if (root == null) return;  postorderTraversal(root.left);  postorderTraversal(root.right);  System.out.print(root.data + ' ');  } // Funkce pro procházení stromu pořadí úrovní public static void levelorderTraversal(kořen uzlu) { if (kořen == null) return;  // Fronta pro průchod pořadím úrovně Frontaq = new LinkedList();  q.offer(kořen);  while (!q.isEmpty()) { Node temp = q.poll();  System.out.print(temp.data + ' ');  // Posune levého potomka ve frontě if (temp.left != null) q.offer(temp.left);  // Vložit pravého potomka do fronty if (temp.right != null) q.offer(temp.right);  } } /* Funkce ovladače pro kontrolu výše uvedeného algoritmu. */ public static void main(String[] args) { Kořen uzlu = null;  // Vložení uzlů root = insert(root, 10);  root = insert(kořen, 20);  root = insert(kořen, 30);  root = insert(kořen, 40);  System.out.print('Přechod předobjednávky: ');  preorderTraversal(root);  System.out.print('
Pořadí procházení: ');  inorderTraversal(kořen);  System.out.print('
Postorder traversal: ');  postorderTraversal(root);  System.out.print('
Přechod objednávky úrovně: ');  levelorderTraversal(kořen);  // Smaže uzel s daty = 20 root = deletion(root, 20);  System.out.print('
Pořadí procházení po smazání: ');  inorderTraversal(kořen);  } }>
Krajta 
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 = nová fronta();  q.Enqueue(kořen);  while (q.Count != 0) { Teplota uzlu = q.Dequeue();  // Vložit uzel jako levého potomka nadřazeného uzlu if (temp.left == null) { temp.left = new Node(data);  přestávka;  } // Pokud levý potomek není null, pošle ho do fronty else q.Enqueue(temp.left);  // Vložit uzel jako pravého potomka nadřazeného uzlu if (temp.right == null) { temp.right = new Node(data);  přestávka;  } // Pokud správný potomek není null, pošle ho do fronty else q.Enqueue(temp.right);  } return root;  } /* funkce pro odstranění daného nejhlubšího uzlu (d_node) v binárním stromu */ public static void DeleteDeepest(Node root, Node d_node) { Queueq = nová fronta();  q.Enqueue(kořen);  // Provede procházení pořadí úrovní až do posledního uzlu Teplota uzlu;  while (q.Count != 0) { temp = q.Dequeue();  if (temp == d_uzel) { temp = null;  d_uzel = null;  vrátit se;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_uzel = null;  vrátit se;  } else q.Enqueue(temp.right);  } if (temp.left != null) { if (temp.left == d_uzel) { temp.left = null;  d_uzel = null;  vrátit se;  } else q.Enqueue(temp.left);  } } } /* funkce pro odstranění prvku v binárním stromu */ public static Odstranění uzlu (kořen uzlu, klíč int) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == klíč) return null;  jinak vrátit kořen;  } Frontaq = nová fronta();  q.Enqueue(kořen);  Teplota uzlu = new Node(0);  Uzel klíč_uzel = null;  // Proveďte procházení pořadím úrovní pro nalezení nejhlubšího uzlu (temp) a uzlu, který má být smazán (key_node) while (q.Count != 0) { temp = q.Dequeue();  if (temp.data == klíč) key_node = temp;  if (temp.left != null) q.Enqueue(temp.left);  if (temp.right != null) q.Enqueue(temp.right);  } if (uzel_klíče != null) { int x = temp.data;  key_node.data = x;  DeleteDeepest(root, temp);  } return root;  } // Procházení stromem pořadí (Left - Root - Right) public static void InorderTraversal(Node root) { if (root == null) return;  InorderTraversal(root.left);  Console.Write(root.data + ' ');  InorderTraversal(root.right);  } // Procházení stromu předobjednávky (kořen - vlevo - vpravo) public static void PreorderTraversal(kořen uzlu) { if (kořen == null) return;  Console.Write(root.data + ' ');  PreorderTraversal(root.left);  PreorderTraversal(root.right);  } // Procházení stromem Postorderu (Left - Right - Root) public static void PostorderTraversal(Node root) { if (root == null) return;  PostorderTraversal(root.left);  PostorderTraversal(root.right);  Console.Write(root.data + ' ');  } // Funkce pro procházení stromu pořadí úrovní public static void LevelorderTraversal(kořen uzlu) { if (kořen == null) return;  // Fronta pro průchod pořadím úrovně Frontaq = nová fronta();  q.Enqueue(kořen);  while (q.Count != 0) { Teplota uzlu = q.Dequeue();  Console.Write(temp.data + ' ');  // Vloží levého potomka do fronty if (temp.left != null) q.Enqueue(temp.left);  // Vložení pravého potomka do fronty if (temp.right != null) q.Enqueue(temp.right);  } } /* Funkce ovladače pro kontrolu výše uvedeného algoritmu. */ public static void Main(string[] args) { Kořen uzlu = null;  // Vložení uzlů root = Insert(root, 10);  root = Insert(kořen, 20);  root = Insert(kořen, 30);  root = Insert(kořen, 40);  Console.Write('Přechod předobjednávky: ');  PreorderTraversal(root);  Console.Write('
Pořadí procházení: ');  InorderTraversal(root);  Console.Write('
Postorder traversal: ');  PostorderTraversal(root);  Console.Write('
Přechod objednávky úrovně: ');  LevelorderTraversal(kořen);  // Smaže uzel s daty = 20 root = Deletion(root, 20);  Console.Write('
Pořadí procházení po smazání: ');  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(kořen);  while (!q.empty()) { Node* temp = q.front();  q.pop();  // Vložit uzel jako levého potomka nadřazeného uzlu if (temp->left == NULL) { temp->left = new Node(data);  přestávka;  } // Pokud levý potomek není null, pošle ho do // fronty else q.push(temp->left);  // Vložit uzel jako pravého potomka nadřazeného uzlu if (temp->right == NULL) { temp->right = new Node(data);  přestávka;  } // Pokud správný potomek není null, pošle ho do // fronty else q.push(temp->right);  } return root; } /* funkce pro odstranění daného nejhlubšího uzlu (d_uzel) v binárním stromu */ void deletDeepest(Node* root, Node* d_node) { queueq;  q.push(kořen);  // Provede procházení pořadí úrovní až do posledního uzlu Node* temp;  while (!q.empty()) { temp = q.front();  q.pop();  if (temp == d_uzel) { temp = NULL;  delete (d_uzel);  vrátit se;  } if (temp->vpravo) { if (temp->vpravo == d_uzel) { temp->vpravo = NULL;  delete (d_uzel);  vrátit se;  } else q.push(temp->right);  } if (temp->left) { if (temp->left == d_uzel) { temp->left = NULL;  delete (d_uzel);  vrátit se;  } else q.push(temp->left);  } } } /* funkce pro smazání prvku v binárním stromu */ Node* deletion(Node* root, int key) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL;  jinak vrátit kořen;  } frontaq;  q.push(kořen);  Node* temp;  Uzel* key_node = NULL;  // Proveďte procházení pořadím úrovní, abyste našli nejhlubší // node(temp) a uzel, který má být smazán (key_node) while (!q.empty()) { temp = q.front();  q.pop();  if (temp->data == klíč) key_node = temp;  if (temp->left) q.push(temp->left);  if (temp->right) q.push(temp->right);  } if (klíčový_uzel != NULL) { int x = temp->data;  klíč_uzel->data = x;  deletDeepest(kořen, temp);  } return root; } // Procházení stromem pořadí (Left - Root - Right) void inorderTraversal(Node* root) { if (!root) return;  inorderTraversal(root->left);  cout<< root->data<< ' ';  inorderTraversal(root->že jo); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return;  cout<< root->data<< ' ';  preorderTraversal(root->vlevo, odjet);  preorderTraversal(root->right); } // Procházení stromem postorderu (Left - Right - Root) void postorderTraversal(Node* root) { if (root == NULL) return;  postorderTraversal(root->left);  postorderTraversal(root->right);  cout<< root->data<< ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) {  if (root == NULL)  return;  // Queue for level order traversal  queueq;  q.push(kořen);  while (!q.empty()) { Node* temp = q.front();  q.pop();  cout<< temp->data<< ' ';  // Push left child in the queue  if (temp->vlevo) q.push(temp->left);  // Push right child ve frontě if (temp->right) q.push(temp->right);  } } /* Funkce ovladače pro kontrolu výše uvedeného algoritmu. */ int main() { Uzel* root = NULL;  // Vložení uzlů root = insert(root, 10);  root = insert(kořen, 20);  root = insert(kořen, 30);  root = insert(kořen, 40);  cout<< 'Preorder traversal: ';  preorderTraversal(root);  cout << '
Inorder traversal: ';  inorderTraversal(root);  cout << '
Postorder traversal: ';  postorderTraversal(root);  cout << '
Level order traversal: ';  levelorderTraversal(root);  // Delete the node with data = 20  root = deletion(root, 20);  cout << '
Inorder traversal after deletion: ';  inorderTraversal(root); }>
Výstup 
Preorder traversal: 10 20 40 30 Inorder traversal: 40 20 10 30 Postorder traversal: 40 20 30 10 Level order traversal: 10 20 30 40 Inorder traversal after deletion: 40 10 30>

Analýza složitosti operací binárních stromů

Operace Časová složitost

Vesmírná složitost

Vložení NA)

NA)

Předobjednávka Traversal NA)

NA)

jak převést řetězec na celé číslo java

Inorder Traversal

NA)

NA)

Přechod poštovní poukázkouNA)

NA)

Level Order TraversalNA)

NA)

Vymazání

NA)

NA)

Hledání

NA)

NA)

Můžeme použít Morris Traversal procházet všechny uzly binárního stromu v O(1) čase.

Výhody binárního stromu

Nevýhody binárního stromu

Aplikace binárního stromu

Často kladené otázky o binárním stromu

1. Co je to binární strom?

Binární strom je nelineární datová struktura sestávající z uzlů, kde každý uzel má nejvýše dva potomky (levý potomek a pravý potomek).

2. Jaké jsou typy binárních stromů?

Binární stromy lze klasifikovat do různých typů, včetně úplných binárních stromů, úplných binárních stromů, dokonalých binárních stromů, vyvážených binárních stromů (jako jsou stromy AVL a Red-Black stromy) a degenerovaných (nebo patologických) binárních stromů.

3. Jakou výšku má binární strom?

Výška binárního stromu je délka nejdelší cesty od kořenového uzlu k listovému uzlu. Představuje počet hran na nejdelší cestě od kořenového uzlu k listovému uzlu.

4. Jaká je hloubka uzlu v binárním stromě?

Hloubka uzlu v binárním stromu je délka cesty od kořenového uzlu k tomuto konkrétnímu uzlu. Hloubka kořenového uzlu je 0.

5. Jak provádíte procházení stromu v binárním stromu?

Procházení stromem v binárním stromě lze provést různými způsoby: Procházení v pořadí, Procházení před objednávkou, Procházení po objednávce a Procházení podle úrovně (také známé jako procházení do šířky).

6. Co je to Inorder traversal v Binary Tree?

V Inorder traversal jsou uzly rekurzivně navštěvovány v tomto pořadí: levý potomek, kořen, pravý potomek. Toto procházení má za následek navštívení uzlů v neklesajícím pořadí v binárním vyhledávacím stromu.

7. Co je to procházení předobjednávky v binárním stromu?

V Preorder traversal jsou uzly rekurzivně navštěvovány v tomto pořadí: kořen, levý potomek, pravý potomek. Toto procházení vede k tomu, že kořenový uzel je prvním navštíveným uzlem.

8. Co je to Postorder traversal v Binary Tree?

V Postorder traversal jsou uzly rekurzivně navštěvovány v tomto pořadí: levé dítě, pravé dítě a kořen. Toto procházení vede k tomu, že kořenový uzel je posledním navštíveným uzlem.

9. Jaký je rozdíl mezi binárním stromem a binárním vyhledávacím stromem?

Binární strom je hierarchická datová struktura, kde každý uzel má nejvýše dva potomky, zatímco binární vyhledávací strom je typ binárního stromu, ve kterém levý potomek uzlu obsahuje hodnoty menší než hodnota uzlu a pravý potomek obsahuje hodnoty. větší než hodnota uzlu.

10. Co je to vyvážený binární strom?

Vyvážený binární strom je binární strom, ve kterém se výška levého a pravého podstromu každého uzlu liší nejvýše o jednu. Vyvážené stromy pomáhají udržovat efektivní operace, jako je vyhledávání, vkládání a mazání, s časovou složitostí blízkou O(log n).

sql klauzule

Závěr:

Strom je hierarchická datová struktura. Mezi hlavní využití stromů patří udržování hierarchických dat, poskytování středního přístupu a operací vkládání/mazání. Binární stromy jsou speciální případy stromu, kde každý uzel má nejvýše dva potomky.

Související články:

  • Vlastnosti binárního stromu
  • Typy binárních stromů