logo

TechCodeview

Introduksjon til binært tre – veiledninger for datastruktur og algoritmer

Binært tre er en ikke-lineær datastruktur der hver node har maksimalt to barn. I denne artikkelen vil vi dekke alt det grunnleggende om Binary Tree, Operasjoner på Binary Tree, dens implementering, fordeler, ulemper som vil hjelpe deg med å løse alle problemene basert på Binary Tree.

Innholdsfortegnelse

Hva er binært tre?

Binært tre er en tredatastruktur (ikke-lineær) der hver node kan ha høyst to barn som omtales som venstre barn og rett barn .



Den øverste noden i et binært tre kalles rot , og de nederste nodene kalles blader . Et binært tre kan visualiseres som en hierarkisk struktur med roten øverst og bladene nederst.

Representasjon av binært tre

Hver node i et binært tre har tre deler:

  • Data
  • Peker til venstre barn
  • Peker til rett barn

Nedenfor er representasjonen av en node av binært tre på forskjellige 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;  } }>
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 
>

Typer av binære tre

Binært tre kan klassifiseres i flere typer basert på flere faktorer:

Last ned youtube vlc media player

Operasjoner på binært tre

1. Innsetting i binært tre

Vi kan sette inn en node hvor som helst i et binært tre ved å sette inn noden som venstre eller høyre underordnede av en hvilken som helst node eller ved å gjøre noden som rot av treet.

Algoritme for å sette inn en node i et binært tre:

  • Sjekk om det er en node i det binære treet som mangler venstre barn. Hvis en slik node eksisterer, sett inn den nye noden som venstre underordnet.
  • Sjekk om det er en node i det binære treet som mangler høyre underordnet. Hvis en slik node eksisterer, sett inn den nye noden som dens høyre underordnede.
  • Hvis vi ikke finner noen node med manglende venstre eller høyre barn, finn noden som har begge barna mangler og sett inn noden som venstre eller høyre barn.

2. Traversering av binært tre

Traversering av binært tre innebærer å besøke alle nodene til det binære treet. Tregjennomgangsalgoritmer kan deles inn i to kategorier:

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

Depth-First Search (DFS) algoritmer:

  • Forhåndsbestill gjennomgang (nåværende-venstre-høyre): Besøk gjeldende node før du besøker noen noder innenfor venstre eller høyre undertrær. Her er traverseringen rot – venstre barn – høyre barn. Det betyr at rotnoden krysses først, deretter venstre barn og til slutt høyre barn.
  • Inorder Traversal (venstre-strøm-høyre): Besøk gjeldende node etter å ha besøkt alle noder innenfor det venstre undertreet, men før du besøker en node innenfor det høyre undertreet. Her er traverseringen venstre barn – rot – høyre barn. Det betyr at det venstre barnet krysses først, deretter rotnoden og til slutt det høyre barnet.
  • Postordregjennomgang (venstre-høyre-aktuell): Besøk gjeldende node etter å ha besøkt alle nodene til venstre og høyre undertre. Her er traverseringen venstre barn – høyre barn – rot. Det betyr at venstre barn har krysset først, deretter høyre barn og til slutt rotnoden.

Breadth-First Search (BFS) algoritmer:

  • Nivåbestillingsgjennomgang: Besøk noder nivå-for-nivå og venstre-til-høyre-mote på samme nivå. Her er traverseringen nivåmessig. Det betyr at det mest venstre barnet har traversert først og deretter de andre barna på samme nivå fra venstre til høyre har traversert.

3. Sletting i binært tre

Vi kan slette hvilken som helst node i det binære treet og omorganisere nodene etter sletting for igjen å danne et gyldig binært tre.

Algoritme for å slette en node i et binært tre:

  • Start ved roten, finn den dypeste og lengst høyre noden i det binære treet og noden vi ønsker å slette.
  • Erstatt dataene til noden lengst til høyre med noden som skal slettes.
  • Slett så den dypeste noden lengst til høyre.

4. Søke i binært tre

Vi kan søke etter et element i noden ved å bruke hvilken som helst av traverseringsteknikkene.

js settimeout

Algoritme for å søke i en node i et binært tre:

  • Start fra rotnoden.
  • Sjekk om gjeldende nodes verdi er lik målverdien.
  • Hvis den gjeldende nodens verdi er lik målverdien, er denne noden den nødvendige noden.
  • Ellers, hvis nodens verdi ikke er lik målverdien, start søket i venstre og høyre underordnede.
  • Hvis vi ikke finner noen node hvis verdi er lik målet, er verdien ikke til stede i treet.

Hjelpeoperasjoner på binært tre

Implementering av Binary Tree

Nedenfor er koden for innsetting, sletting og kryssing av det binære treet:

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->venstre = temp->høyre = NULL;  retur temp; } // Funksjon for å sette inn noder Node* insert(Node* rot, int data) { // Hvis treet er tomt, blir ny node roten if (root == NULL) { root = newNode(data);  returnere rot;  } // Kø for å krysse treet og finne posisjonen for å sette inn noden Node* køen[100];  int foran = 0, bak = 0;  kø[rear++] = rot;  while (front != rear) { Node* temp = queue[front++];  // Sett inn node som venstre underordnet til overordnet node if (temp->left == NULL) { temp->left = newNode(data);  gå i stykker;  } // Hvis venstre barn ikke er null, skyv det til køen else queue[rear++] = temp->left;  // Sett inn node som høyre underordnet til overordnet node if (temp->right == NULL) { temp->right = newNode(data);  gå i stykker;  } // Hvis det riktige barnet ikke er null, skyver det til køen else queue[rear++] = temp->right;  } returner rot; } /* Funksjon for å slette den gitte dypeste noden (d_node) i binærtreet */ void deletDeepest(Node* rot, Node* d_node) { Node* kø[100];  int foran = 0, bak = 0;  kø[rear++] = rot;  // Gjennomgå nivårekkefølge til siste node Node* temp;  while (foran != bak) { temp = kø[foran++];  if (temp == d_node) { temp = NULL;  gratis(d_node);  komme tilbake;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  gratis(d_node);  komme tilbake;  } annet kø[rear++] = temp->høyre;  } if (temp->venstre) { if (temp->venstre == d_node) { temp->venstre = NULL;  gratis(d_node);  komme tilbake;  } else queue[rear++] = temp->venstre;  } } } /* Funksjon for å slette element i binært tre */ Node* sletting(Node* rot, int nøkkel) { if (!root) return NULL;  if (rot->venstre == NULL && rot->høyre == NULL) { if (root->data == nøkkel) returner NULL;  ellers returner roten;  } Node* kø[100];  int foran = 0, bak = 0;  kø[rear++] = rot;  Node* temp;  Node* key_node = NULL;  // Gjennomgå nivårekkefølge for å finne dypeste node (temp) og node som skal slettes (key_node) mens (front != rear) { temp = queue[front++];  if (temp->data == nøkkel) key_node = temp;  if (temp->venstre) kø[rear++] = temp->venstre;  hvis (temp->høyre) kø[rear++] = temp->høyre;  } if (key_node != NULL) { int x = temp->data;  key_node->data = x;  deleDeepest(root, temp);  } returner rot; } // Inorder tree traversal (Venstre - Rot - Høyre) void inorderTraversal(Node* rot) { if (!root) return;  inorderTraversal(root->venstre);  printf('%d ', rot->data);  inorderTraversal(root->høyre); } // Forhåndsbestill tregjennomgang (Root - Venstre - Høyre) void preorderTraversal(Node* rot) { if (!root) return;  printf('%d ', rot->data);  preorderTraversal(root->venstre);  preorderTraversal(root->høyre); } // Postorder tre traversal (Venstre - Høyre - Rot) void postorderTraversal(Node* rot) { if (root == NULL) return;  postorderTraversal(root->venstre);  postorderTraversal(root->høyre);  printf('%d ', rot->data); } // Funksjon for gjennomgang av nivåordre-tre void levelorderTraversal(Node* rot) { if (root == NULL) return;  // Kø for gjennomgang av nivåordre Node* kø[100];  int foran = 0, bak = 0;  kø[rear++] = rot;  while (front != rear) { Node* temp = queue[front++];  printf('%d ', temp->data);  // Skyv venstre barn i køen hvis (temp->venstre) kø[rear++] = temp->venstre;  // Skyv høyre barn i køen hvis (temp->høyre) kø[rear++] = temp->høyre;  } } /* Driverfunksjon for å sjekke algoritmen ovenfor. */ int main() { Node* rot = NULL;  // Innsetting av noder rot = insert(root, 10);  root = insert(root, 20);  root = insert(root, 30);  root = insert(root, 40);  printf('Forhåndsbestill traversal: ');  preorderTraversal(root);  printf('
Rekkefølgegjennomgang: ');  inorderTraversal(root);  printf('
Postorder-gjennomgang: ');  postorderTraversal(root);  printf('
Nivårekkefølge: ');  nivåordreTraversal(root);  // Slett noden med data = 20 root = sletting(root, 20);  printf('
Bestillingsgjennomgang etter sletting: ');  inorderTraversal(root);  returner 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.tilbud(root);  while (!q.isEmpty()) { Node temp = q.poll();  // Sett inn node som venstre underordnet til overordnet node if (temp.left == null) { temp.left = new Node(data);  gå i stykker;  } // Hvis det venstre barnet ikke er null, skyver det til //-køen else q.offer(temp.left);  // Sett inn node som høyre underordnet til overordnet node if (temp.right == null) { temp.right = new Node(data);  gå i stykker;  } // Hvis det riktige barnet ikke er null, trykk det til //-køen else q.offer(temp.right);  } returner rot;  } /* funksjon for å slette den gitte dypeste noden (d_node) i binært tre */ public static void deletDeepest(Node rot, Node d_node) { Queueq = new LinkedList();  q.tilbud(root);  // Gjør nivåordregjennomgang til siste node Nodetemp;  while (!q.isEmpty()) { temp = q.poll();  if (temp == d_node) { temp = null;  d_node = null;  komme tilbake;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = null;  komme tilbake;  } annet q.offer(temp.right);  } if (temp.left != null) { if (temp.left == d_node) { temp.left = null;  d_node = null;  komme tilbake;  } annet q.tilbud(temp.venstre);  } } } /* funksjon for å slette element i binært tre */ offentlig statisk Nodesletting(Noderot, int nøkkel) { if (root == null) returner null;  if (root.left == null && root.right == null) { if (root.data == nøkkel) returner null;  ellers returner roten;  } Køq = new LinkedList();  q.tilbud(root);  Node temp = ny Node(0);  Node nøkkelnode = null;  // Gjennomgå nivårekkefølge for å finne dypeste // node(temp) og node som skal slettes (key_node) mens (!q.isEmpty()) { temp = q.poll();  if (temp.data == nøkkel) key_node = temp;  if (temp.venstre != null) q.offer(temp.venstre);  if (temp.right != null) q.offer(temp.right);  } if (key_node != null) { int x = temp.data;  key_node.data = x;  deleDeepest(root, temp);  } returner rot;  } // Inorder tree traversal (Venstre - Rot - Høyre) public static void inorderTraversal(Node rot) { if (root == null) return;  inorderTraversal(root.venstre);  System.out.print(root.data + ' ');  inorderTraversal(root.right);  } // Forhåndsbestill tregjennomgang (Root - Venstre - Høyre) public static void preorderTraversal(Noderot) { if (root == null) return;  System.out.print(root.data + ' ');  preorderTraversal(root.left);  preorderTraversal(root.right);  } // Postorder tree traversal (Venstre - Høyre - Root) public static void postorderTraversal(Noderot) { if (root == null) return;  postorderTraversal(root.venstre);  postorderTraversal(root.right);  System.out.print(root.data + ' ');  } // Funksjon for gjennomgang av nivåordre-tre public static void nivåordreTraversal(Noderot) { if (root == null) return;  // Kø for gjennomgang av nivåordre Køq = new LinkedList();  q.tilbud(root);  while (!q.isEmpty()) { Node temp = q.poll();  System.out.print(temp.data + ' ');  // Skyv venstre barn i køen if (temp.left != null) q.offer(temp.left);  // Skyv høyre barn i køen if (temp.right != null) q.offer(temp.right);  } } /* Driverfunksjon for å sjekke algoritmen ovenfor. */ public static void main(String[] args) { Noderot = null;  // Innsetting av noder rot = insert(root, 10);  root = insert(root, 20);  root = insert(root, 30);  root = insert(root, 40);  System.out.print('Forhåndsbestilling: ');  preorderTraversal(root);  System.out.print('
Bestillingsgjennomgang: ');  inorderTraversal(root);  System.out.print('
Postorder-gjennomgang: ');  postorderTraversal(root);  System.out.print('
Nivårekkefølge: ');  nivåordreTraversal(root);  // Slett noden med data = 20 root = sletting(root, 20);  System.out.print('
Bestillingsgjennomgang etter sletting: ');  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 = ny kø();  q.Enqueue(root);  while (q.Count != 0) { Node temp = q.Dequeue();  // Sett inn node som venstre underordnet til overordnet node if (temp.left == null) { temp.left = new Node(data);  gå i stykker;  } // Hvis det venstre barnet ikke er null, skyver det til køen ellers q.Enqueue(temp.left);  // Sett inn node som høyre underordnet til overordnet node if (temp.right == null) { temp.right = new Node(data);  gå i stykker;  } // Hvis det riktige barnet ikke er null, skyver det til køen ellers q.Enqueue(temp.right);  } returner rot;  } /* funksjon for å slette den gitte dypeste noden (d_node) i binært tre */ public static void DeleteDeepest(Node rot, Node d_node) { Queueq = ny kø();  q.Enqueue(root);  // Gjør nivåordregjennomgang til siste node Nodetemp;  while (q.Count != 0) { temp = q.Dequeue();  if (temp == d_node) { temp = null;  d_node = null;  komme tilbake;  } if (temp.right != null) { if (temp.right == d_node) { temp.right = null;  d_node = null;  komme tilbake;  } annet q.Enqueue(temp.right);  } if (temp.left != null) { if (temp.left == d_node) { temp.left = null;  d_node = null;  komme tilbake;  } annet q.Enqueue(temp.venstre);  } } } /* funksjon for å slette element i binært tre */ public static Node Deletion(Node root, int key) { if (root == null) return null;  if (root.left == null && root.right == null) { if (root.data == nøkkel) returner null;  ellers returner roten;  } Køq = ny kø();  q.Enqueue(root);  Node temp = ny Node(0);  Node nøkkelnode = null;  // Gjennomgå nivårekkefølge for å finne dypeste node (temp) og node som skal slettes (key_node) while (q.Count != 0) { temp = q.Dequeue();  if (temp.data == nøkkel) key_node = temp;  if (temp.left != null) q.Enqueue(temp.left);  if (temp.right != null) q.Enqueue(temp.right);  } if (key_node != null) { int x = temp.data;  key_node.data = x;  DeleteDeepest (root, temp);  } returner rot;  } // Inorder tree traversal (Venstre - Rot - Høyre) public static void InorderTraversal(Noderot) { if (root == null) return;  InorderTraversal(root.left);  Console.Write(root.data + ' ');  InorderTraversal(root.right);  } // Forhåndsbestill tregjennomgang (Root - Venstre - Høyre) public static void PreorderTraversal(Noderot) { if (root == null) return;  Console.Write(root.data + ' ');  PreorderTraversal(root.left);  PreorderTraversal(root.right);  } // Postorder-tretraversal (Venstre - Høyre - Root) public static void PostorderTraversal(Node-rot) { if (root == null) return;  PostorderTraversal(root.venstre);  PostorderTraversal(root.right);  Console.Write(root.data + ' ');  } // Funksjon for gjennomgang av nivåordre-tre public static void LevelorderTraversal(Noderot) { if (root == null) return;  // Kø for gjennomgang av nivåordre Køq = ny kø();  q.Enqueue(root);  while (q.Count != 0) { Node temp = q.Dequeue();  Console.Write(temp.data + ' ');  // Skyv venstre barn i køen if (temp.left != null) q.Enqueue(temp.left);  // Skyv høyre barn i køen if (temp.right != null) q.Enqueue(temp.right);  } } /* Driverfunksjon for å sjekke algoritmen ovenfor. */ public static void Main(string[] args) { Noderot = null;  // Innsetting av noder rot = Insert(root, 10);  root = Sett inn(rot, 20);  root = Sett inn(rot, 30);  root = Sett inn(rot, 40);  Console.Write('Forhåndsbestilling: ');  ForhåndsbestillingTraversal(root);  Console.Write('
Bestillingsgjennomgang: ');  InorderTraversal(root);  Console.Write('
Postorder-gjennomgang: ');  PostorderTraversal(root);  Console.Write('
Nivårekkefølge: ');  LevelorderTraversal(root);  // Slett noden med data = 20 root = Deletion(root, 20);  Console.Write('
Bestill gjennomgang etter sletting: ');  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();  // Sett inn node som venstre underordnet til overordnet node if (temp->left == NULL) { temp->left = new Node(data);  gå i stykker;  } // Hvis det venstre barnet ikke er null, skyver det til //-køen ellers q.push(temp->left);  // Sett inn node som høyre underordnet til overordnet node if (temp->right == NULL) { temp->right = new Node(data);  gå i stykker;  } // Hvis det riktige barnet ikke er null, skyver det til //-køen ellers q.push(temp->right);  } returner rot; } /* funksjon for å slette den gitte dypeste noden (d_node) i binærtreet */ void deletDeepest(Node* rot, Node* d_node) { queueq;  q.push(root);  // Gjennomgå nivårekkefølge til siste node Node* temp;  while (!q.empty()) { temp = q.front();  q.pop();  if (temp == d_node) { temp = NULL;  slette (d_node);  komme tilbake;  } if (temp->right) { if (temp->right == d_node) { temp->right = NULL;  slette (d_node);  komme tilbake;  } annet q.push(temp->høyre);  } if (temp->venstre) { if (temp->venstre == d_node) { temp->venstre = NULL;  slette (d_node);  komme tilbake;  } annet q.push(temp->venstre);  } } } /* funksjon for å slette element i binært tre */ Node* sletting(Node* rot, int nøkkel) { if (!root) return NULL;  if (rot->venstre == NULL && rot->høyre == NULL) { if (root->data == nøkkel) returner NULL;  ellers returner roten;  } køq;  q.push(root);  Node* temp;  Node* key_node = NULL;  // Gjennomgå nivårekkefølge for å finne dypeste // node(temp) og node som skal slettes (key_node) mens (!q.empty()) { temp = q.front();  q.pop();  if (temp->data == nøkkel) key_node = temp;  if (temp->venstre) q.push(temp->venstre);  if (temp->høyre) q.push(temp->høyre);  } if (key_node != NULL) { int x = temp->data;  key_node->data = x;  deleDeepest(root, temp);  } returner rot; } // Inorder tree traversal (Venstre - Rot - Høyre) void inorderTraversal(Node* rot) { if (!root) return;  inorderTraversal(root->venstre);  cout<< root->data<< ' ';  inorderTraversal(root->Ikke sant); } // Forhåndsbestill tregjennomgang (Root - Venstre - Høyre) void preorderTraversal(Node* rot) { if (!root) return;  cout<< root->data<< ' ';  preorderTraversal(root->venstre);  preorderTraversal(root->høyre); } // Postorder tre traversal (Venstre - Høyre - Rot) void postorderTraversal(Node* rot) { if (root == NULL) return;  postorderTraversal(root->venstre);  postorderTraversal(root->høyre);  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->venstre) q.push(temp->venstre);  // Skyv høyre barn i køen hvis (temp->høyre) q.push(temp->høyre);  } } /* Driverfunksjon for å sjekke algoritmen ovenfor. */ int main() { Node* rot = NULL;  // Innsetting av noder rot = 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); }>
Produksjon 
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>

Kompleksitetsanalyse av binære treoperasjoner

Drift Tidskompleksitet

Plass kompleksitet

eks av brukernavn
Innsetting PÅ)

PÅ)

Forhåndsbestill Traversal PÅ)

PÅ)

Inorder Traversal

PÅ)

PÅ)

PostordregjennomgangPÅ)

PÅ)

Nivå ordregjennomgangPÅ)

PÅ)

Sletting

PÅ)

PÅ)

Søker

PÅ)

strint til int

PÅ)

Vi kan bruke Morris Traversal å krysse alle nodene til det binære treet i O(1) tid.

Fordeler med Binary Tree

Ulemper med Binary Tree

Anvendelser av Binary Tree

Ofte stilte spørsmål om binært tre

1. Hva er et binært tre?

Et binært tre er en ikke-lineær datastruktur som består av noder, hvor hver node har maksimalt to barn (venstre barn og høyre barn).

2. Hva er typene binære trær?

Binære trær kan klassifiseres i forskjellige typer, inkludert fulle binære trær, komplette binære trær, perfekte binære trær, balanserte binære trær (som AVL-trær og rød-svarte trær) og degenererte (eller patologiske) binære trær.

3. Hva er høyden på et binært tre?

Høyden på et binært tre er lengden på den lengste banen fra rotnoden til en bladnoden. Den representerer antall kanter i den lengste banen fra rotnoden til en bladnoden.

4. Hva er dybden til en node i et binært tre?

Dybden til en node i et binært tre er lengden på banen fra rotnoden til den aktuelle noden. Dybden til rotnoden er 0.

5. Hvordan utfører du tretraversering i et binært tre?

Tre-traversering i et binært tre kan gjøres på forskjellige måter: I-order-traversal, Pre-order-traversal, Post-order-traversal og Level-order-traversal (også kjent som bredde-først-traversal).

numpy mener

6. Hva er en Inorder-traversal i binært tre?

I Inorder-traversal besøkes noder rekursivt i denne rekkefølgen: venstre barn, rot, høyre barn. Denne gjennomgangen resulterer i at noder blir besøkt i ikke-avtagende rekkefølge i et binært søketre.

7. Hva er en forhåndsbestillingsgjennomgang i binært tre?

I Preorder-traversal besøkes noder rekursivt i denne rekkefølgen: rot, venstre barn, høyre barn. Denne gjennomgangen resulterer i at rotnoden er den første noden som blir besøkt.

8. Hva er en Postorder-traversal i binært tre?

I Postorder-traversering besøkes noder rekursivt i denne rekkefølgen: venstre barn, høyre barn og rot. Denne gjennomgangen resulterer i at rotnoden er den siste noden som skal besøkes.

9. Hva er forskjellen mellom et binært tre og et binært søketre?

Et binært tre er en hierarkisk datastruktur der hver node har maksimalt to barn, mens et binært søketre er en type binært tre der det venstre barnet til en node inneholder verdier som er mindre enn nodens verdi, og det høyre barnet inneholder verdier større enn nodens verdi.

10. Hva er et balansert binært tre?

Et balansert binært tre er et binært tre der høyden på venstre og høyre undertrær til hver node avviker med høyst én. Balanserte trær bidrar til å opprettholde effektive operasjoner som søking, innsetting og sletting med tidskompleksitet nær O(log n).

Konklusjon:

Tre er en hierarkisk datastruktur. Hovedbruken av trær inkluderer å opprettholde hierarkiske data, gi moderat tilgang og sette inn/slette operasjoner. Binære trær er spesielle tilfeller av tre der hver node har maksimalt to barn.

Relaterte artikler:

  • Egenskaper til binært tre
  • Typer av binære tre