logo

TechCodeview

Introduktion till binärt träd – handledningar om datastruktur och algoritmer

Binärt träd är en icke-linjär datastruktur där varje nod har högst två barn. I den här artikeln kommer vi att täcka alla grunderna i Binary Tree, Operations on Binary Tree, dess implementering, fördelar, nackdelar som hjälper dig att lösa alla problem baserade på Binary Tree.

Innehållsförteckning



Vad är binärt träd?

Binärt träd är en träddatastruktur (icke-linjär) där varje nod kan ha högst två barn som kallas för vänster barn och den rätt barn .

Den översta noden i ett binärt träd kallas rot , och de lägsta noderna kallas löv . Ett binärt träd kan visualiseras som en hierarkisk struktur med roten överst och löven längst ner.

Representation av binärt träd

Varje nod i ett binärt träd har tre delar:



  • Data
  • Pekare till vänster barn
  • Pekare till rätt barn

Nedan är representationen av en nod av binärt träd på olika språk:

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;  } }>
Pytonorm 
# 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 
>

Typer av binära träd

Binära träd kan klassificeras i multipla typer baserat på flera faktorer:



Operationer på binärt träd

1. Infogning i binärt träd

Vi kan infoga en nod var som helst i ett binärt träd genom att infoga noden som vänster eller höger underordnad av någon nod eller genom att göra noden som roten till trädet.

Algoritm för att infoga en nod i ett binärt träd:

  • Kontrollera om det finns en nod i det binära trädet som saknar det vänstra barnet. Om en sådan nod finns, infoga den nya noden som dess vänstra underordnade.
  • Kontrollera om det finns en nod i det binära trädet som saknar rätt underordnat. Om en sådan nod finns, infoga den nya noden som dess högra underordnade.
  • Om vi ​​inte hittar någon nod med saknat vänster eller höger barn, leta reda på noden där båda barnen saknas och infoga noden som dess vänstra eller högra barn.

2. Traversering av binärt träd

Traversering av binärt träd innebär att man besöker alla noder i det binära trädet. Trädgenomgångsalgoritmer kan brett delas in i två kategorier:

  • Depth-First Search (DFS) Algoritmer
  • Bredth-First Search (BFS) Algoritmer

Depth-First Search (DFS) algoritmer:

  • Förbeställ genomgång (nuvarande-vänster-höger): Besök den aktuella noden innan du besöker några noder i det vänstra eller högra underträdet. Här är genomgången rot – vänster barn – höger barn. Det betyder att rotnoden korsas först, sedan dess vänstra barn och slutligen det högra barnet.
  • Inorder Traversal (vänster-ström-höger): Besök den aktuella noden efter att ha besökt alla noder i det vänstra underträdet men innan du besöker någon nod i det högra underträdet. Här är övergången vänster barn – rot – höger barn. Det betyder att det vänstra barnet korsas först, sedan dess rotnod och slutligen det högra barnet.
  • Postorderövergång (vänster-höger-aktuell): Besök den aktuella noden efter att ha besökt alla noder i vänster och höger underträd. Här är övergången vänster barn – höger barn – rot. Det betyder att det vänstra barnet har passerat först, sedan det högra barnet och slutligen dess rotnod.

Bredth-First Search (BFS) algoritmer:

  • Genomgång av nivåorder: Besök noder nivå för nivå och vänster till höger mode på samma nivå. Här är övergången nivåmässigt. Det betyder att det mest vänstra barnet har korsat först och sedan de andra barnen på samma nivå från vänster till höger har korsat.

3. Radering i binärt träd

Vi kan ta bort vilken nod som helst i det binära trädet och ordna om noderna efter raderingen för att återigen bilda ett giltigt binärt träd.

Algoritm för att ta bort en nod i ett binärt träd:

  • Börja vid roten, hitta den djupaste och längst till höger noden i det binära trädet och noden som vi vill ta bort.
  • Ersätt den djupaste nodens data längst till höger med noden som ska raderas.
  • Ta sedan bort den djupaste noden längst till höger.

4. Söka i binärt träd

Vi kan söka efter ett element i noden genom att använda någon av övergångsteknikerna.

Algoritm för att söka efter en nod i ett binärt träd:

  • Börja från rotnoden.
  • Kontrollera om den aktuella nodens värde är lika med målvärdet.
  • Om den aktuella nodens värde är lika med målvärdet, är denna nod den nödvändiga noden.
  • Annars, om nodens värde inte är lika med målvärdet, starta sökningen i vänster och höger barn.
  • Om vi ​​inte hittar någon nod vars värde är lika med målet, så finns inte värdet i trädet.

Hjälpoperationer på binärt träd

Implementering av Binary Tree

Nedan finns koden för infogning, radering och genomgång av det binära trädet:

java urval sortera
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->vänster = temp->höger = NULL;  returtemp; } // Funktion för att infoga noder Node* insert(Node* rot, int data) { // Om trädet är tomt, blir ny nod roten if (root == NULL) { root = newNode(data);  returnera rot;  } // Kö för att korsa trädet och hitta positionen för att infoga noden Node*-kön[100];  int fram = 0, bak = 0;  kö[rear++] = rot;  while (front != rear) { Node* temp = queue[front++];  // Infoga nod som vänstra underordnade av föräldernoden if (temp->left == NULL) { temp->left = newNode(data);  ha sönder;  } // Om det vänstra barnet inte är null, skjut det till kön else queue[rear++] = temp->left;  // Infoga nod som höger underordnad till föräldernod if (temp->right == NULL) { temp->right = newNode(data);  ha sönder;  } // Om rätt barn inte är null, skjut det till kön else queue[rear++] = temp->right;  } returnera rot; } /* Funktion för att ta bort den givna djupaste noden (d_node) i binärt träd */ void deletDeepest(Node* rot, Node* d_node) { Node* kö[100];  int fram = 0, bak = 0;  kö[rear++] = rot;  // Gör nivåordningsövergång till sista nod Nod* temp;  while (fram != bak) { temp = kö[fram++];  if (temp == d_node) { temp = NULL;  free(d_node);  lämna tillbaka;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  free(d_node);  lämna tillbaka;  } else queue[rear++] = temp->höger;  } if (temp->left) { if (temp->left == d_node) { temp->left = NULL;  free(d_node);  lämna tillbaka;  } else queue[rear++] = temp->vänster;  } } } /* Funktion för att ta bort element i binärt träd */ Node* deletion(Node* rot, int nyckel) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == nyckel) return NULL;  annars returnerar roten;  } Nod* kö[100];  int fram = 0, bak = 0;  kö[rear++] = rot;  Nod* temp;  Nod* key_node = NULL;  // Gå igenom nivåordning för att hitta den djupaste noden (temp) och noden som ska raderas (key_node) medan (front != rear) { temp = queue[front++];  if (temp->data == nyckel) key_node = temp;  om (temp->vänster) kö[rear++] = temp->vänster;  if (temp->höger) kö[rear++] = temp->höger;  } if (nyckelnod != NULL) { int x = temp->data;  key_node->data = x;  deleteDeepest(root, temp);  } returnera rot; } // Inorder tree traversal (Vänster - Rot - Höger) void inorderTraversal(Node* rot) { if (!root) return;  inorderTraversal(root->vänster);  printf('%d ', root->data);  inorderTraversal(root->höger); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* rot) { if (!root) return;  printf('%d ', root->data);  preorderTraversal(root->vänster);  preorderTraversal(root->höger); } // Postorder tree traversal (Vänster - Höger - Rot) void postorderTraversal(Node* rot) { if (root == NULL) return;  postorderTraversal(root->vänster);  postorderTraversal(root->höger);  printf('%d ', root->data); } // Funktion för genomgång av nivåordningsträd void levelorderTraversal(Nod* rot) { if (root == NULL) return;  // Kö för genomgång av nivåordning Nod* kö[100];  int fram = 0, bak = 0;  kö[rear++] = rot;  while (front != rear) { Node* temp = queue[front++];  printf('%d ', temp->data);  // Tryck vänster underordnad i kön om (temp->vänster) kö[rear++] = temp->vänster;  // Tryck höger barn i kön om (temp->höger) kö[rear++] = temp->höger;  } } /* Drivrutinsfunktion för att kontrollera ovanstående algoritm. */ int main() { Node* rot = NULL;  // Infogning av noder root = insert(root, 10);  root = insert(root, 20);  root = insert(root, 30);  root = insert(root, 40);  printf('Förbeställning genomgång: ');  preorderTraversal(root);  printf('
Beställningsövergång: ');  inorderTraversal(root);  printf('
Postordertraversal: ');  postorderTraversal(root);  printf('
Nivåordningsövergång: ');  levelorderTraversal(root);  // Ta bort noden med data = 20 root = deletion(root, 20);  printf('
Beställningsövergång efter radering: ');  inorderTraversal(root);  returnera 0; }>
Java 
import java.util.LinkedList; import java.util.Queue; // Node class to define the structure of the node class Node {  int data;  Node left, right;  // Parameterized Constructor  Node(int val) {  data = val;  left = right = null;  } } public class BinaryTree {  // Function to insert nodes  public static Node insert(Node root, int data) {  // If tree is empty, new node becomes the root  if (root == null) {  root = new Node(data);  return root;  }  // Queue to traverse the tree and find the position to  // insert the node  Queueq = new LinkedList();  q.offer(root);  while (!q.isEmpty()) { Node temp = q.poll();  // Infoga nod som den vänstra underordnade av föräldernoden if (temp.left == null) { temp.left = new Node(data);  ha sönder;  } // Om det vänstra barnet inte är null, tryck det till //-kön else q.offer(temp.left);  // Infoga nod som höger underordnad till föräldernod if (temp.right == null) { temp.right = new Node(data);  ha sönder;  } // Om det rätta barnet inte är null, tryck det till //-kön else q.offer(temp.right);  } returnera rot;  } /* funktion för att ta bort den givna djupaste noden (d_node) i binärt träd */ public static void deletDeepest(Nodrot, Nod d_node) { Queueq = new LinkedList();  q.offer(root);  // Gör nivåordningsövergång till sista nod Nodtemp;  while (!q.isEmpty()) { temp = q.poll();  if (temp == d_node) { temp = null;  d_node = null;  lämna tillbaka;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = null;  lämna tillbaka;  } annat q.offer(temp.right);  } if (temp.left != null) { if (temp.left == d_node) { temp.left = null;  d_node = null;  lämna tillbaka;  } annat q.offer(temp.left);  } } } /* funktion för att ta bort element i binärt träd */ public static Nod deletion(Nod rot, int nyckel) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == nyckel) returnera null;  annars returnerar roten;  } Köq = new LinkedList();  q.offer(root);  Nod temp = new Node(0);  Nod nyckelnod = null;  // Gör genomgång av nivåordning för att hitta den djupaste // nod(temp) och nod som ska raderas (key_node) medan (!q.isEmpty()) { temp = q.poll();  if (temp.data == nyckel) key_node = temp;  if (temp.left != null) q.offer(temp.left);  if (temp.right != null) q.offer(temp.right);  } if (nyckelnod != null) { int x = temp.data;  key_node.data = x;  deleteDeepest(root, temp);  } returnera rot;  } // Inorder tree traversal (Vänster - Rot - Höger) public static void inorderTraversal(Nodrot) { 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(Nodrot) { if (root == null) return;  System.out.print(root.data + ' ');  preorderTraversal(root.left);  preorderTraversal(root.right);  } // Postorder tree traversal (vänster - höger - rot) public static void postorderTraversal(Node root) { if (root == null) return;  postorderTraversal(root.left);  postorderTraversal(root.right);  System.out.print(root.data + ' ');  } // Funktion för genomgång av nivåordningsträd public static void levelorderTraversal(Nodrot) { if (root == null) return;  // Kö för genomgång av nivåorder Köq = new LinkedList();  q.offer(root);  while (!q.isEmpty()) { Node temp = q.poll();  System.out.print(temp.data + ' ');  // Tryck vänster underordnad i kön if (temp.left != null) q.offer(temp.left);  // Tryck höger barn i kön if (temp.right != null) q.offer(temp.right);  } } /* Drivrutinsfunktion för att kontrollera ovanstående algoritm. */ public static void main(String[] args) { Nodrot = null;  // Infogning av noder root = insert(root, 10);  root = insert(root, 20);  root = insert(root, 30);  root = insert(root, 40);  System.out.print('Förbeställning genomgång: ');  preorderTraversal(root);  System.out.print('
Beställningsövergång: ');  inorderTraversal(root);  System.out.print('
Postordertraversal: ');  postorderTraversal(root);  System.out.print('
Nivåordningsövergång: ');  levelorderTraversal(root);  // Ta bort noden med data = 20 root = deletion(root, 20);  System.out.print('
Beställningsövergång efter radering: ');  inorderTraversal(root);  } }>
Pytonorm 
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 = ny kö();  q.Enqueue(root);  while (q.Count != 0) { Node temp = q.Dequeue();  // Infoga nod som den vänstra underordnade av föräldernoden if (temp.left == null) { temp.left = new Node(data);  ha sönder;  } // Om det vänstra barnet inte är null, skjut det till kön annars q.Enqueue(temp.left);  // Infoga nod som höger underordnad till föräldernod if (temp.right == null) { temp.right = new Node(data);  ha sönder;  } // Om rätt barn inte är null, skjut det till kön annars q.Enqueue(temp.right);  } returnera rot;  } /* funktion för att ta bort den givna djupaste noden (d_node) i binärt träd */ public static void DeleteDeepest(Nodrot, Nod d_node) { Queueq = ny kö();  q.Enqueue(root);  // Gör nivåordningsövergång till sista nod Nodtemp;  while (q.Count != 0) { temp = q.Dequeue();  if (temp == d_node) { temp = null;  d_node = null;  lämna tillbaka;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = null;  lämna tillbaka;  } annat q.Enqueue(temp.right);  } if (temp.left != null) { if (temp.left == d_node) { temp.left = null;  d_node = null;  lämna tillbaka;  } annat q.Enqueue(temp.left);  } } } /* funktion för att ta bort element i binärt träd */ public static Node Deletion(Nodrot, int nyckel) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == nyckel) returnera null;  annars returnerar roten;  } Köq = ny kö();  q.Enqueue(root);  Nod temp = new Node(0);  Nod nyckelnod = null;  // Gör nivåordningsövergång för att hitta den djupaste noden (temp) och noden som ska raderas (key_node) while (q.Count != 0) { temp = q.Dequeue();  if (temp.data == nyckel) key_node = temp;  if (temp.left != null) q.Enqueue(temp.left);  if (temp.right != null) q.Enqueue(temp.right);  } if (nyckelnod != null) { int x = temp.data;  key_node.data = x;  DeleteDeepest(root, temp);  } returnera rot;  } // Inorder tree traversal (Vänster - Rot - Höger) public static void InorderTraversal(Nodrot) { if (root == null) return;  InorderTraversal(root.left);  Console.Write(root.data + ' ');  InorderTraversal(root.right);  } // Preorder tree traversal (Root - Left - Right) public static void PreorderTraversal(Nodrot) { if (root == null) return;  Console.Write(root.data + ' ');  PreorderTraversal(root.left);  PreorderTraversal(root.right);  } // Postorder tree traversal (Vänster - Höger - Root) public static void PostorderTraversal(Node root) { if (root == null) return;  PostorderTraversal(root.left);  PostorderTraversal(root.right);  Console.Write(root.data + ' ');  } // Funktion för genomgång av nivåordningsträd public static void LevelorderTraversal(Nodrot) { if (root == null) return;  // Kö för genomgång av nivåorder Köq = ny kö();  q.Enqueue(root);  while (q.Count != 0) { Node temp = q.Dequeue();  Console.Write(temp.data + ' ');  // Tryck vänster underordnad i kön if (temp.left != null) q.Enqueue(temp.left);  // Tryck höger barn i kön if (temp.right != null) q.Enqueue(temp.right);  } } /* Drivrutinsfunktion för att kontrollera ovanstående algoritm. */ public static void Main(string[] args) { Nodrot = null;  // Infogning av noder rot = Insert(root, 10);  root = Insert(root, 20);  root = Insert(root, 30);  root = Insert(root, 40);  Console.Write('Förbeställning traversal: ');  PreorderTraversal(root);  Console.Write('
Beställningsövergång: ');  InorderTraversal(root);  Console.Write('
Postorder-traversal: ');  PostorderTraversal(root);  Console.Write('
Nivåordningsövergång: ');  LevelorderTraversal(root);  // Ta bort noden med data = 20 root = Deletion(root, 20);  Console.Write('
Beställ genomgång efter radering: ');  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()) { Node* temp = q.front();  q.pop();  // Infoga nod som vänstra underordnade av föräldernoden if (temp->left == NULL) { temp->left = new Node(data);  ha sönder;  } // Om det vänstra barnet inte är null, tryck det till //-kön annars q.push(temp->left);  // Infoga nod som höger underordnad av föräldernod if (temp->right == NULL) { temp->right = new Node(data);  ha sönder;  } // Om det rätta barnet inte är null, tryck det till //-kön annars q.push(temp->right);  } returnera rot; } /* funktion för att ta bort den givna djupaste noden (d_node) i binärt träd */ void deletDeepest(Node* rot, Node* d_node) { köq;  q.push(root);  // Gör nivåordningsövergång till sista nod Nod* temp;  while (!q.empty()) { temp = q.front();  q.pop();  if (temp == d_node) { temp = NULL;  ta bort (d_node);  lämna tillbaka;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  ta bort (d_node);  lämna tillbaka;  } annat q.push(temp->höger);  } if (temp->left) { if (temp->left == d_node) { temp->left = NULL;  ta bort (d_node);  lämna tillbaka;  } annat q.push(temp->vänster);  } } } /* funktion för att ta bort element i binärt träd */ Node* deletion(Node* rot, int nyckel) { if (!root) return NULL;  if (root->left == NULL && root->right == NULL) { if (root->data == nyckel) return NULL;  annars returnerar roten;  } köq;  q.push(root);  Nod* temp;  Node* key_node = NULL;  // Gör genomgång av nivåordning för att hitta den djupaste // nod(temp) och nod som ska raderas (key_node) medan (!q.empty()) { temp = q.front();  q.pop();  if (temp->data == nyckel) key_node = temp;  if (temp->vänster) q.push(temp->vänster);  if (temp->höger) q.push(temp->höger);  } if (nyckelnod != NULL) { int x = temp->data;  key_node->data = x;  deleteDeepest(root, temp);  } returnera rot; } // Inorder tree traversal (Vänster - Rot - Höger) void inorderTraversal(Node* rot) { if (!root) return;  inorderTraversal(root->vänster);  cout<< root->data<< ' ';  inorderTraversal(root->höger); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* rot) { if (!root) return;  cout<< root->data<< ' ';  preorderTraversal(root->vänster);  preorderTraversal(root->right); } // Postorder tree traversal (Vänster - Höger - Rot) void postorderTraversal(Node* rot) { if (root == NULL) return;  postorderTraversal(root->vänster);  postorderTraversal(root->höger);  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(root);  while (!q.empty()) { Node* temp = q.front();  q.pop();  cout<< temp->data<< ' ';  // Push left child in the queue  if (temp->vänster) q.push(temp->vänster);  // Tryck höger barn i kön if (temp->right) q.push(temp->right);  } } /* Drivrutinsfunktion för att kontrollera ovanstående algoritm. */ int main() { Node* rot = NULL;  // Infogning av noder root = insert(root, 10);  root = insert(root, 20);  root = insert(root, 30);  root = insert(root, 40);  cout<< 'Preorder traversal: ';  preorderTraversal(root);  cout << '
Inorder traversal: ';  inorderTraversal(root);  cout << '
Postorder traversal: ';  postorderTraversal(root);  cout << '
Level order traversal: ';  levelorderTraversal(root);  // Delete the node with data = 20  root = deletion(root, 20);  cout << '
Inorder traversal after deletion: ';  inorderTraversal(root); }>
Produktion 
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>

Komplexitetsanalys av binära trädoperationer

Operationer Tidskomplexitet

Rymdkomplexitet

Införande PÅ)

PÅ)

Förbeställ Traversal PÅ)

PÅ)

Inorder Traversal

PÅ)

PÅ)

Postorder TraversalPÅ)

PÅ)

Nivå Order TraversalPÅ)

PÅ)

Radering

PÅ)

PÅ)

Sökande

PÅ)

PÅ)

Vi kan använda Morris Traversal att korsa alla noder i det binära trädet i O(1) tid.

Fördelar med Binary Tree

Nackdelar med Binary Tree

Tillämpningar av Binary Tree

Vanliga frågor om binärt träd

1. Vad är ett binärt träd?

Ett binärt träd är en icke-linjär datastruktur som består av noder, där varje nod har högst två barn (vänster barn och höger barn).

2. Vilka typer av binära träd finns det?

Binära träd kan klassificeras i olika typer, inklusive fullständiga binära träd, kompletta binära träd, perfekta binära träd, balanserade binära träd (som AVL-träd och rödsvarta träd) och degenererade (eller patologiska) binära träd.

3. Vad är höjden på ett binärt träd?

Höjden på ett binärt träd är längden på den längsta vägen från rotnoden till en lövnod. Det representerar antalet kanter i den längsta vägen från rotnoden till en lövnod.

4. Vad är djupet på en nod i ett binärt träd?

Djupet på en nod i ett binärt träd är längden på vägen från rotnoden till den specifika noden. Rotnodens djup är 0.

5. Hur utför man trädpassering i ett binärt träd?

Trädtraversering i ett binärt träd kan göras på olika sätt: I-order-traversal, Pre-order-traversal, Post-order-traversal och Level-order-traversal (även känd som bredd-först-traversal).

6. Vad är en Inorder-traversal i binärt träd?

I Inorder-traversal besöks noder rekursivt i denna ordning: vänster barn, rot, höger barn. Denna genomgång resulterar i att noder besöks i icke-minskande ordning i ett binärt sökträd.

7. Vad är en förbeställnings-traversal i binärt träd?

I Preorder-traversal besöks noder rekursivt i denna ordning: rot, vänster barn, höger barn. Denna genomgång resulterar i att rotnoden är den första noden som besöks.

solig deol

8. Vad är en Postorder-traversal i binärt träd?

I Postorder-traversal besöks noder rekursivt i denna ordning: vänster barn, höger barn och rot. Denna genomgång resulterar i att rotnoden är den sista noden som besöks.

9. Vad är skillnaden mellan ett binärt träd och ett binärt sökträd?

Ett binärt träd är en hierarkisk datastruktur där varje nod har högst två barn, medan ett binärt sökträd är en typ av binärt träd där det vänstra barnet i en nod innehåller värden som är mindre än nodens värde, och det högra barnet innehåller värden större än nodens värde.

10. Vad är ett balanserat binärt träd?

Ett balanserat binärt träd är ett binärt träd där höjden på de vänstra och högra underträden för varje nod skiljer sig med högst en. Balanserade träd hjälper till att upprätthålla effektiva operationer som sökning, infogning och radering med tidskomplexitet nära O(log n).

Slutsats:

Träd är en hierarkisk datastruktur. De huvudsakliga användningsområdena för träd inkluderar att underhålla hierarkiska data, ge måttlig åtkomst och infoga/ta bort operationer. Binära träd är specialfall av träd där varje nod har högst två barn.

Relaterade artiklar:

  • Egenskaper för binärt träd
  • Typer av binära träd