Binärer Baum ist ein nichtlineare Datenstruktur wobei jeder Knoten höchstens zwei Kinder hat. In diesem Artikel behandeln wir alle Grundlagen des Binärbaums, Operationen auf dem Binärbaum, seine Implementierung sowie Vor- und Nachteile, die Ihnen bei der Lösung aller auf dem Binärbaum basierenden Probleme helfen werden.
Inhaltsverzeichnis
- Was ist ein Binärbaum?
- Darstellung des Binärbaums
- Arten von Binärbäumen
- Operationen am Binärbaum
- Hilfsoperationen am Binärbaum
- Implementierung des Binärbaums
- Komplexitätsanalyse binärer Baumoperationen
- Vorteile des Binärbaums
- Nachteile des Binärbaums
- Anwendungen des Binärbaums
- Häufig gestellte Fragen zum Binärbaum
Was ist ein Binärbaum?
Binärbaum ist ein Baumdatenstruktur (nichtlinear) in dem jeder Knoten haben kann höchstens zwei Kinder die als bezeichnet werden linkes Kind und das richtiges Kind .
Der oberste Knoten in einem Binärbaum wird als bezeichnet Wurzel , und die untersten Knoten werden aufgerufen Blätter . Ein Binärbaum kann als hierarchische Struktur mit der Wurzel oben und den Blättern unten dargestellt werden.
Darstellung des Binärbaums
Jeder Knoten in einem Binärbaum besteht aus drei Teilen:
- Daten
- Zeiger auf das linke untergeordnete Element
- Zeiger auf das richtige Kind
Nachfolgend finden Sie die Darstellung eines Knotens eines Binärbaums in verschiedenen Sprachen:
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 >
Arten von Binärbäumen
Binärbäume können basierend auf mehreren Faktoren in mehrere Typen eingeteilt werden:
- Auf der Grundlage der Anzahl der Kinder
- Vollständiger Binärbaum
- Entarteter Binärbaum
- Verzerrte Binärbäume
- Auf der Grundlage des Abschlusses von Levels
- Kompletter Binärbaum
- Perfekter Binärbaum
- Ausgewogener Binärbaum
- Auf Basis der Knotenwerte:
- Binärer Suchbaum
- AVL-Baum
- Roter schwarzer Baum
- B Baum
- B+ Baum
- Segmentbaum
Operationen am Binärbaum
1. Einfügen in den Binärbaum
Wir können einen Knoten an einer beliebigen Stelle in einem Binärbaum einfügen, indem wir den Knoten als linkes oder rechtes Kind eines beliebigen Knotens einfügen oder indem wir den Knoten zur Wurzel des Baums machen.
Algorithmus zum Einfügen eines Knotens in einen Binärbaum:
- Überprüfen Sie, ob es einen Knoten im Binärbaum gibt, bei dem das linke untergeordnete Element fehlt. Wenn ein solcher Knoten vorhanden ist, fügen Sie den neuen Knoten als dessen linken untergeordneten Knoten ein.
- Überprüfen Sie, ob es im Binärbaum einen Knoten gibt, bei dem das rechte Kind fehlt. Wenn ein solcher Knoten vorhanden ist, fügen Sie den neuen Knoten als rechtes Kind ein.
- Wenn wir keinen Knoten finden, bei dem das linke oder rechte Kind fehlt, suchen wir den Knoten, bei dem beide Kinder fehlen, und fügen den Knoten als dessen linkes oder rechtes Kind ein.
2. Durchquerung des Binärbaums
Beim Durchlaufen des Binärbaums werden alle Knoten des Binärbaums besucht. Tree Traversal-Algorithmen können grob in zwei Kategorien eingeteilt werden:
- Algorithmen der Tiefensuche (DFS).
- Algorithmen der Breitensuche (BFS).
DFS-Algorithmen (Depth-First Search):
- Vorbestellungsdurchquerung (aktuell-links-rechts): Besuchen Sie den aktuellen Knoten, bevor Sie Knoten innerhalb der linken oder rechten Teilbäume besuchen. Hier ist die Durchquerung Wurzel – linkes Kind – rechtes Kind. Das bedeutet, dass zuerst der Wurzelknoten durchlaufen wird, dann sein linkes Kind und schließlich das rechte Kind.
- Inorder Traversal (links-aktuell-rechts): Besuchen Sie den aktuellen Knoten, nachdem Sie alle Knoten im linken Teilbaum besucht haben, aber bevor Sie einen Knoten im rechten Teilbaum besucht haben. Hier erfolgt die Durchquerung linkes Kind – Wurzel – rechtes Kind. Das bedeutet, dass zuerst das linke Kind durchlaufen wird, dann sein Wurzelknoten und schließlich das rechte Kind.
- Postorder Traversal (links-rechts-strom): Besuchen Sie den aktuellen Knoten, nachdem Sie alle Knoten des linken und rechten Teilbaums besucht haben. Hier erfolgt die Durchquerung linkes Kind – rechtes Kind – Wurzel. Das bedeutet, dass das linke Kind zuerst, dann das rechte Kind und schließlich seinen Wurzelknoten durchlaufen hat.
Algorithmen der Breitensuche (BFS):
- Durchquerung der Level-Reihenfolge: Besuchen Sie Knoten Ebene für Ebene und von links nach rechts auf derselben Ebene. Hier erfolgt die Durchquerung stufenweise. Dies bedeutet, dass das am weitesten links stehende Kind zuerst die Ebene durchlaufen hat und dann die anderen Kinder derselben Ebene von links nach rechts die Ebene durchlaufen haben.
3. Löschen im Binärbaum
Wir können jeden Knoten im Binärbaum löschen und die Knoten nach dem Löschen neu anordnen, um wieder einen gültigen Binärbaum zu bilden.
Algorithmus zum Löschen eines Knotens in einem Binärbaum:
- Suchen Sie ausgehend von der Wurzel den tiefsten und am weitesten rechts stehenden Knoten im Binärbaum und den Knoten, den wir löschen möchten.
- Ersetzen Sie die Daten des tiefsten Knotens ganz rechts durch den Knoten, der gelöscht werden soll.
- Dann löschen Sie den tiefsten Knoten ganz rechts.
4. Suche im Binärbaum
Wir können nach einem Element im Knoten suchen, indem wir eine der Traversierungstechniken verwenden.
Algorithmus zum Durchsuchen eines Knotens in einem Binärbaum:
- Beginnen Sie am Wurzelknoten.
- Überprüfen Sie, ob der Wert des aktuellen Knotens dem Zielwert entspricht.
- Wenn der Wert des aktuellen Knotens dem Zielwert entspricht, ist dieser Knoten der erforderliche Knoten.
- Andernfalls, wenn der Wert des Knotens nicht mit dem Zielwert übereinstimmt, starten Sie die Suche im linken und rechten untergeordneten Knoten.
- Wenn wir keinen Knoten finden, dessen Wert dem Ziel entspricht, ist der Wert nicht im Baum vorhanden.
Hilfsoperationen am Binärbaum
- Ermitteln der Höhe des Baumes
- Finden Sie die Ebene eines Knotens in einem Binärbaum
- Ermitteln der Größe des gesamten Baumes
Implementierung des Binärbaums
Nachfolgend finden Sie den Code zum Einfügen, Löschen und Durchlaufen des Binärbaums:
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->Daten = Wert; temp->left = temp->right = NULL; Rücklauftemperatur; } // Funktion zum Einfügen von Knoten Node* insert(Node* root, int data) { // Wenn der Baum leer ist, wird der neue Knoten zur Wurzel if (root == NULL) { root = newNode(data); root zurückgeben; } // Warteschlange zum Durchlaufen des Baums und Finden der Position zum Einfügen des Knotens Node* queue[100]; int vorne = 0, hinten = 0; queue[hinten++] = root; while (front != Rear) { Node* temp = queue[front++]; // Knoten als linkes untergeordnetes Element des übergeordneten Knotens einfügen if (temp->left == NULL) { temp->left = newNode(data); brechen; } // Wenn das linke Kind nicht null ist, schiebe es in die Warteschlange, sonst queue[rear++] = temp->left; // Knoten als rechtes untergeordnetes Element des übergeordneten Knotens einfügen if (temp->right == NULL) { temp->right = newNode(data); brechen; } // Wenn das rechte Kind nicht null ist, schiebe es in die Warteschlange, sonst queue[rear++] = temp->right; } return root; } /* Funktion zum Löschen des angegebenen tiefsten Knotens (d_node) im Binärbaum */ void deletDeepest(Node* root, Node* d_node) { Node* queue[100]; int vorne = 0, hinten = 0; queue[hinten++] = root; // Ebenenreihenfolge bis zum letzten Knoten durchlaufen Node* temp; while (vorne != hinten) { temp = queue[front++]; if (temp == d_node) { temp = NULL; free(d_node); zurückkehren; } if (temp->right) { if (temp->right == d_node) { temp->right = NULL; free(d_node); zurückkehren; } else queue[rear++] = temp->right; } if (temp->left) { if (temp->left == d_node) { temp->left = NULL; free(d_node); zurückkehren; } else queue[rear++] = temp->left; } } } /* Funktion zum Löschen eines Elements im Binärbaum */ Node* deletion(Node* root, int key) { if (!root) return NULL; if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL; sonst return root; } Node* queue[100]; int vorne = 0, hinten = 0; queue[hinten++] = root; Knoten*-Temp; Node* key_node = NULL; // Ebenenreihenfolge durchlaufen, um den tiefsten Knoten (temp) und den zu löschenden Knoten (key_node) zu finden, während (front != hinten) { temp = queue[front++]; if (temp->data == key) key_node = temp; if (temp->left) queue[rear++] = temp->left; if (temp->right) queue[rear++] = temp->right; } if (key_node != NULL) { int x = temp->data; key_node->data = x; deletDeepest(root, temp); } return root; } // Durchquerung des Inorder-Baums (Links – Wurzel – Rechts) void inorderTraversal(Node* root) { if (!root) return; inorderTraversal(root->left); printf('%d ', root->data); inorderTraversal(root->right); } // Baumdurchquerung vorbestellen (Root – Left – Right) void preorderTraversal(Node* root) { if (!root) return; printf('%d ', root->data); preorderTraversal(root->left); preorderTraversal(root->right); } // Durchquerung des Postorder-Baums (Links – Rechts – Wurzel) void postorderTraversal(Node* root) { if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf('%d ', root->data); } // Funktion für Level Order Tree Traversal void levelorderTraversal(Node* root) { if (root == NULL) return; // Warteschlange für Level-Reihenfolge-Durchquerung Node* queue[100]; int vorne = 0, hinten = 0; queue[hinten++] = root; while (front != Rear) { Node* temp = queue[front++]; printf('%d ', temp->data); // Linkes Kind in die Warteschlange schieben if (temp->left) queue[rear++] = temp->left; // Rechtes Kind in die Warteschlange schieben if (temp->right) queue[rear++] = temp->right; } } /* Treiberfunktion zur Überprüfung des obigen Algorithmus. */ int main() { Node* root = NULL; // Einfügen von Knoten root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); printf('Vorbestellungsdurchquerung: '); preorderTraversal(root); printf('
Inorder traversal: '); inorderTraversal(root); printf('
Postorder Traversal: '); postorderTraversal(root); printf('
Durchquerung der Ebenenreihenfolge: '); levelorderTraversal(root); // Den Knoten mit data = 20 löschen root = deletion(root, 20); printf('
Inorder Traversal nach dem Löschen: '); inorderTraversal(root); 0 zurückgeben; }> 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(); // Knoten als linkes untergeordnetes Element des übergeordneten Knotens einfügen if (temp.left == null) { temp.left = new Node(data); brechen; } // Wenn das linke untergeordnete Element nicht null ist, schiebe es in die // Warteschlange, sonst q.offer(temp.left); // Knoten als rechtes untergeordnetes Element des übergeordneten Knotens einfügen if (temp.right == null) { temp.right = new Node(data); brechen; } // Wenn das rechte Kind nicht null ist, schiebe es in die Warteschlange // sonst q.offer(temp.right); } return root; } /* Funktion zum Löschen des angegebenen tiefsten Knotens (d_node) im Binärbaum */ public static void deletDeepest(Node root, Node d_node) { Queueq = new LinkedList(); q.offer(root); // Ebenenreihenfolge bis zum letzten Knoten durchlaufen Node temp; while (!q.isEmpty()) { temp = q.poll(); if (temp == d_node) { temp = null; d_node = null; zurückkehren; } if (temp.right != null) { if (temp.right == d_node) { temp.right = null; d_node = null; zurückkehren; } else q.offer(temp.right); } if (temp.left != null) { if (temp.left == d_node) { temp.left = null; d_node = null; zurückkehren; } else q.offer(temp.left); } } } /* Funktion zum Löschen eines Elements im Binärbaum */ public static Node deletion(Node root, int key) { if (root == null) return null; if (root.left == null && root.right == null) { if (root.data == key) return null; sonst return root; } Warteschlangeq = new LinkedList(); q.offer(root); Knotentemperatur = neuer Knoten(0); Knoten key_node = null; // Ebenenreihenfolge durchlaufen, um den tiefsten // Knoten (temp) und den zu löschenden Knoten (key_node) zu finden, während (!q.isEmpty()) { temp = q.poll(); if (temp.data == key) key_node = temp; if (temp.left != null) q.offer(temp.left); if (temp.right != null) q.offer(temp.right); } if (key_node != null) { int x = temp.data; key_node.data = x; deletDeepest(root, temp); } return root; } // Durchquerung des Inorder-Baums (Links – Wurzel – Rechts) public static void inorderTraversal(Node root) { if (root == null) return; inorderTraversal(root.left); System.out.print(root.data + ' '); inorderTraversal(root.right); } // Baumdurchquerung vorbestellen (Root – Left – Right) public static void preorderTraversal(Node root) { if (root == null) return; System.out.print(root.data + ' '); preorderTraversal(root.left); preorderTraversal(root.right); } // Durchquerung des Postorder-Baums (Links – Rechts – Wurzel) public static void postorderTraversal(Node root) { if (root == null) return; postorderTraversal(root.left); postorderTraversal(root.right); System.out.print(root.data + ' '); } // Funktion für die Durchquerung des Level-Order-Baums public static void levelorderTraversal(Node root) { if (root == null) return; // Warteschlange für Level-Reihenfolge-Durchquerung. Warteschlangeq = new LinkedList(); q.offer(root); while (!q.isEmpty()) { Node temp = q.poll(); System.out.print(temp.data + ' '); // Linkes Kind in die Warteschlange schieben if (temp.left != null) q.offer(temp.left); // Rechtes Kind in die Warteschlange schieben if (temp.right != null) q.offer(temp.right); } } /* Treiberfunktion zur Überprüfung des obigen Algorithmus. */ public static void main(String[] args) { Node root = null; // Einfügen von Knoten root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); System.out.print('Preorder traversal: '); preorderTraversal(root); System.out.print('
Inorder traversal: '); inorderTraversal(root); System.out.print('
Postorder traversal: '); postorderTraversal(root); System.out.print('
Level order traversal: '); levelorderTraversal(root); // Den Knoten löschen mit data = 20 root = deletion(root, 20); System.out.print('
Inorder Traversal nach dem Löschen: '); 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 = neue Warteschlange(); q.Enqueue(root); while (q.Count != 0) { Node temp = q.Dequeue(); // Knoten als linkes untergeordnetes Element des übergeordneten Knotens einfügen if (temp.left == null) { temp.left = new Node(data); brechen; } // Wenn das linke Kind nicht null ist, schiebe es in die Warteschlange, sonst q.Enqueue(temp.left); // Knoten als rechtes untergeordnetes Element des übergeordneten Knotens einfügen if (temp.right == null) { temp.right = new Node(data); brechen; } // Wenn das rechte Kind nicht null ist, schiebe es in die Warteschlange, sonst q.Enqueue(temp.right); } return root; } /* Funktion zum Löschen des angegebenen tiefsten Knotens (d_node) im Binärbaum */ public static void DeleteDeepest(Node root, Node d_node) { Queueq = neue Warteschlange(); q.Enqueue(root); // Ebenenreihenfolge bis zum letzten Knoten durchlaufen Node temp; while (q.Count != 0) { temp = q.Dequeue(); if (temp == d_node) { temp = null; d_node = null; zurückkehren; } if (temp.right != null) { if (temp.right == d_node) { temp.right = null; d_node = null; zurückkehren; } else q.Enqueue(temp.right); } if (temp.left != null) { if (temp.left == d_node) { temp.left = null; d_node = null; zurückkehren; } else q.Enqueue(temp.left); } } } /* Funktion zum Löschen eines Elements im Binärbaum */ public static Node Deletion(Node root, int key) { if (root == null) return null; if (root.left == null && root.right == null) { if (root.data == key) return null; sonst return root; } Warteschlangeq = neue Warteschlange(); q.Enqueue(root); Knotentemperatur = neuer Knoten(0); Knoten key_node = null; // Ebenenreihenfolge durchlaufen, um den tiefsten Knoten (temp) und den zu löschenden Knoten (key_node) zu finden, während (q.Count != 0) { temp = q.Dequeue(); if (temp.data == key) 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); } return root; } // Durchquerung des Inorder-Baums (Links – Wurzel – Rechts) public static void InorderTraversal(Node root) { if (root == null) return; InorderTraversal(root.left); Console.Write(root.data + ' '); InorderTraversal(root.right); } // Baumdurchquerung vorbestellen (Root – Links – Rechts) public static void PreorderTraversal(Node root) { if (root == null) return; Console.Write(root.data + ' '); PreorderTraversal(root.left); PreorderTraversal(root.right); } // Durchquerung des Postorder-Baums (Links – Rechts – Wurzel) public static void PostorderTraversal(Node root) { if (root == null) return; PostorderTraversal(root.left); PostorderTraversal(root.right); Console.Write(root.data + ' '); } // Funktion für die Durchquerung des Level-Order-Baums public static void LevelorderTraversal(Node root) { if (root == null) return; // Warteschlange für Level-Reihenfolge-Durchquerung. Warteschlangeq = neue Warteschlange(); q.Enqueue(root); while (q.Count != 0) { Node temp = q.Dequeue(); Console.Write(temp.data + ' '); // Linkes Kind in die Warteschlange schieben if (temp.left != null) q.Enqueue(temp.left); // Rechtes Kind in die Warteschlange schieben if (temp.right != null) q.Enqueue(temp.right); } } /* Treiberfunktion zur Überprüfung des obigen Algorithmus. */ public static void Main(string[] args) { Node root = null; // Einfügen von Knoten root = Insert(root, 10); root = Insert(root, 20); root = Insert(root, 30); root = Insert(root, 40); Console.Write('Vorbestellungsdurchquerung: '); PreorderTraversal(root); Console.Write('
Inorder traversal: '); InorderTraversal(root); Console.Write('
Postorder Traversal: '); PostorderTraversal(root); Console.Write('
Durchquerung der Ebenenreihenfolge: '); LevelorderTraversal(root); // Den Knoten mit data = 20 löschen root = Deletion(root, 20); Console.Write('
Inorder Traversal nach dem Löschen: '); 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(); // Knoten als linkes untergeordnetes Element des übergeordneten Knotens einfügen if (temp->left == NULL) { temp->left = new Node(data); brechen; } // Wenn das linke untergeordnete Element nicht null ist, schiebe es in die // Warteschlange, sonst q.push(temp->left); // Knoten als rechtes untergeordnetes Element des übergeordneten Knotens einfügen if (temp->right == NULL) { temp->right = new Node(data); brechen; } // Wenn das rechte Kind nicht null ist, schiebe es in die Warteschlange // sonst q.push(temp->right); } return root; } /* Funktion zum Löschen des angegebenen tiefsten Knotens (d_node) im Binärbaum */ void deletDeepest(Node* root, Node* d_node) { queueQ; q.push(root); // Ebenenreihenfolge bis zum letzten Knoten durchlaufen Node* temp; while (!q.empty()) { temp = q.front(); q.pop(); if (temp == d_node) { temp = NULL; löschen (d_node); zurückkehren; } if (temp->right) { if (temp->right == d_node) { temp->right = NULL; löschen (d_node); zurückkehren; } else q.push(temp->right); } if (temp->left) { if (temp->left == d_node) { temp->left = NULL; löschen (d_node); zurückkehren; } else q.push(temp->left); } } } /* Funktion zum Löschen eines Elements im Binärbaum */ Node* deletion(Node* root, int key) { if (!root) return NULL; if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL; sonst return root; } WarteschlangeQ; q.push(root); Knoten*-Temp; Node* key_node = NULL; // Ebenenreihenfolge durchlaufen, um den tiefsten // Knoten (temp) und den zu löschenden Knoten (key_node) zu finden, während (!q.empty()) { temp = q.front(); q.pop(); 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) { int x = temp->data; key_node->data = x; deletDeepest(root, temp); } return root; } // Durchquerung des Inorder-Baums (Links – Wurzel – Rechts) void inorderTraversal(Node* root) { if (!root) return; inorderTraversal(root->left); cout<< root->Daten<< ' '; inorderTraversal(root->Rechts); } // Baumdurchquerung vorbestellen (Root – Left – Right) void preorderTraversal(Node* root) { if (!root) return; cout<< root->Daten<< ' '; preorderTraversal(root->links); preorderTraversal(root->right); } // Durchquerung des Postorder-Baums (Links – Rechts – Wurzel) void postorderTraversal(Node* root) { if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); cout<< root->Daten<< ' '; } // 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->Daten<< ' '; // Push left child in the queue if (temp->left) q.push(temp->left); // Rechtes Kind in die Warteschlange schieben if (temp->right) q.push(temp->right); } } /* Treiberfunktion zur Überprüfung des obigen Algorithmus. */ int main() { Node* root = NULL; // Einfügen von Knoten 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); }> Ausgabe
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>
Komplexitätsanalyse binärer Baumoperationen
| Operationen | Zeitkomplexität | Weltraumkomplexität |
|---|---|---|
| Einfügen | AN) | AN) |
| Traversal vorbestellen | AN) | AN) |
Inorder-Durchquerung | AN) | AN) |
| Durchquerung von Postanweisungen | AN) | AN) |
| Level-Order-Traversal | AN) | AN) |
Streichung | AN) | AN) |
Suchen | AN) | AN) |
Wir können benutzen Morris-Durchquerung um alle Knoten des Binärbaums in O(1)-Zeit zu durchlaufen.
Vorteile des Binärbaums
- Effiziente Suche: Binärbäume sind bei der Suche nach einem bestimmten Element effizient, da jeder Knoten höchstens zwei untergeordnete Knoten hat Speichereffizient: Binärbäume benötigen im Vergleich zu anderen Baumdatenstrukturen weniger Speicher und sind daher speichereffizient.
- Binärbäume sind relativ einfach zu implementieren und zu verstehen, da jeder Knoten höchstens zwei untergeordnete Knoten hat, einen linken und einen rechten untergeordneten Knoten.
Nachteile des Binärbaums
- Begrenzte Struktur: Binärbäume sind auf zwei untergeordnete Knoten pro Knoten beschränkt, was ihren Nutzen in bestimmten Anwendungen einschränken kann. Wenn ein Baum beispielsweise mehr als zwei untergeordnete Knoten pro Knoten erfordert, ist möglicherweise eine andere Baumstruktur geeigneter.
- Unausgeglichene Bäume: Unausgeglichene Binärbäume, bei denen ein Teilbaum deutlich größer ist als der andere, können zu ineffizienten Suchvorgängen führen. Dies kann auftreten, wenn der Baum nicht richtig ausbalanciert ist oder wenn Daten in einer nicht zufälligen Reihenfolge eingefügt werden.
- Platzineffizienz: Binärbäume können im Vergleich zu anderen Datenstrukturen platzsparend sein. Dies liegt daran, dass jeder Knoten zwei untergeordnete Zeiger erfordert, was bei großen Bäumen einen erheblichen Speicheraufwand bedeuten kann.
- Langsame Leistung im schlimmsten Fall: Im schlimmsten Fall kann ein Binärbaum degenerieren oder schief werden, was bedeutet, dass jeder Knoten nur noch ein Kind hat. In diesem Fall können sich Suchoperationen auf eine Zeitkomplexität von O(n) verschlechtern, wobei n die Anzahl der Knoten im Baum ist.
Anwendungen des Binärbaums
- Binärbaum kann dazu verwendet werden stellen hierarchische Daten dar .
- Huffman-Codierungsbäume werden verwendet in Datenkomprimierungsalgorithmen .
- Prioritätswarteschlange ist eine weitere Anwendung des Binärbaums, die zur Suche nach dem Maximum oder Minimum der O(1)-Zeitkomplexität verwendet wird.
- Nützlich für die segmentierte Indizierung in der Datenbank und nützlich für die Speicherung des Caches im System.
- Binärbäume können zur Implementierung von Entscheidungsbäumen verwendet werden, einer Art maschinellem Lernalgorithmus, der zur Klassifizierung und Regressionsanalyse verwendet wird.
Häufig gestellte Fragen zum Binärbaum
1. Was ist ein Binärbaum?
Ein Binärbaum ist eine nichtlineare Datenstruktur, die aus Knoten besteht, wobei jeder Knoten höchstens zwei Kinder hat (linkes Kind und rechtes Kind).
2. Welche Arten von Binärbäumen gibt es?
Binärbäume können in verschiedene Typen eingeteilt werden, darunter vollständige Binärbäume, vollständige Binärbäume, perfekte Binärbäume, ausgeglichene Binärbäume (wie AVL-Bäume und Rot-Schwarz-Bäume) und degenerierte (oder pathologische) Binärbäume.
3. Wie hoch ist ein Binärbaum?
Die Höhe eines Binärbaums ist die Länge des längsten Pfades vom Wurzelknoten zu einem Blattknoten. Sie stellt die Anzahl der Kanten auf dem längsten Pfad vom Wurzelknoten zu einem Blattknoten dar.
4. Wie tief ist ein Knoten in einem Binärbaum?
Die Tiefe eines Knotens in einem Binärbaum ist die Länge des Pfads vom Wurzelknoten zu diesem bestimmten Knoten. Die Tiefe des Wurzelknotens beträgt 0.
5. Wie führt man eine Baumdurchquerung in einem Binärbaum durch?
Die Baumdurchquerung in einem Binärbaum kann auf verschiedene Arten erfolgen: Durchquerung in der Reihenfolge, Durchquerung vor der Bestellung, Durchquerung nach der Reihenfolge und Durchquerung der Ebenenordnung (auch bekannt als Durchquerung in der Breite zuerst).
6. Was ist eine Inorder-Traversierung im Binärbaum?
Beim Inorder-Traversal werden Knoten rekursiv in dieser Reihenfolge besucht: linkes Kind, Wurzel, rechtes Kind. Diese Durchquerung führt dazu, dass Knoten in einem binären Suchbaum in nicht abnehmender Reihenfolge besucht werden.
7. Was ist ein Preorder-Traversal im Binary Tree?
Beim Preorder-Traversal werden Knoten rekursiv in dieser Reihenfolge besucht: Wurzel, linkes Kind, rechtes Kind. Diese Durchquerung führt dazu, dass der Wurzelknoten der erste Knoten ist, der besucht wird.
8. Was ist ein Postorder-Traversal im Binary Tree?
Beim Postorder-Traversal werden Knoten rekursiv in dieser Reihenfolge besucht: linkes Kind, rechtes Kind und Wurzel. Diese Durchquerung führt dazu, dass der Wurzelknoten der letzte Knoten ist, der besucht wird.
9. Was ist der Unterschied zwischen einem Binärbaum und einem Binärsuchbaum?
Ein binärer Baum ist eine hierarchische Datenstruktur, bei der jeder Knoten höchstens zwei untergeordnete Knoten hat, während ein binärer Suchbaum eine Art binärer Baum ist, bei dem das linke untergeordnete Element eines Knotens Werte enthält, die kleiner als der Wert des Knotens sind, und das rechte untergeordnete Element Werte enthält größer als der Wert des Knotens.
Analysieren Sie den String in int
10. Was ist ein ausgeglichener Binärbaum?
Ein ausgeglichener Binärbaum ist ein Binärbaum, bei dem sich die Höhe des linken und rechten Teilbaums jedes Knotens um höchstens eins unterscheidet. Ausgewogene Bäume tragen dazu bei, effiziente Vorgänge wie Suchen, Einfügen und Löschen mit einer Zeitkomplexität nahe O(log n) aufrechtzuerhalten.
Abschluss:
Baum ist eine hierarchische Datenstruktur. Zu den Hauptanwendungen von Bäumen gehören die Verwaltung hierarchischer Daten, die Bereitstellung moderaten Zugriffs und Einfüge-/Löschvorgänge. Binärbäume sind Sonderfälle von Bäumen, bei denen jeder Knoten höchstens zwei Kinder hat.
In Verbindung stehende Artikel:
- Eigenschaften des Binärbaums
- Arten von Binärbäumen