Introduktion til binært træ – datastruktur og algoritmevejledninger
Binært træ er en ikke-lineær datastruktur hvor hver node højst har to børn. I denne artikel vil vi dække alt det grundlæggende i Binary Tree, Operations on Binary Tree, dets implementering, fordele, ulemper, som vil hjælpe dig med at løse alle problemer baseret på Binary Tree.
Indholdsfortegnelse
- Hvad er binært træ?
- Repræsentation af binært træ
- Typer af binære træer
- Operationer på binært træ
- Hjælpeoperationer på binært træ
- Implementering af Binary Tree
- Kompleksitetsanalyse af binære træoperationer
- Fordele ved Binary Tree
- Ulemper ved binært træ
- Anvendelser af binært træ
- Ofte stillede spørgsmål om binært træ
Hvad er binært træ?
Binært træ er et trædatastruktur (ikke-lineær) hvori hver node kan have højst to børn som omtales som efterladt barn og rigtige barn .
Den øverste knude i et binært træ kaldes rod , og de nederste noder kaldes blade . Et binært træ kan visualiseres som en hierarkisk struktur med roden øverst og bladene nederst.
Repræsentation af binært træ
Hver node i et binært træ har tre dele:
- Data
- Pointer til venstre barn
- Pointer til det rigtige barn
Nedenfor er repræsentationen af en knude af binært træ på forskellige sprog:
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 af binære træer
Binært træ kan klassificeres i multiple typer baseret på flere faktorer:
- På grundlag af antal børn
- Fuldt binært træ
- Degenereret binært træ
- Skæve binære træer
- På grundlag af færdiggørelse af niveauer
- Komplet binært træ
- Perfekt binært træ
- Balanceret binært træ
- På grundlag af nodeværdier:
- Binært søgetræ
- AVL træ
- Rødt sort træ
- B Træ
- B+ træ
- Segmenttræ
Operationer på binært træ
1. Indsættelse i binært træ
Vi kan indsætte en node hvor som helst i et binært træ ved at indsætte noden som venstre eller højre underordnede af en hvilken som helst node eller ved at lave noden som rod af træet.
Algoritme til at indsætte en node i et binært træ:
- Tjek om der er en node i det binære træ, som mangler venstre barn. Hvis der findes en sådan node, skal du indsætte den nye node som dens venstre underordnede.
- Tjek, om der er en node i det binære træ, som mangler højre underordnet. Hvis der findes en sådan node, indsæt den nye node som dens højre underordnede.
- Hvis vi ikke finder nogen node med manglende venstre eller højre barn, så find den node, hvor begge børn mangler, og indsæt noden som dens venstre eller højre barn.
2. Gennemgang af binært træ
Gennemgang af binært træ involverer at besøge alle noderne i det binære træ. Trægennemløbsalgoritmer kan klassificeres bredt i to kategorier:
- Depth-First Search (DFS) Algoritmer
- Breadth-First Search (BFS) Algoritmer
Depth-First Search (DFS) algoritmer:
- Forudbestil gennemkørsel (aktuelt-venstre-højre): Besøg den aktuelle node, før du besøger nogen noder inde i venstre eller højre undertræ. Her er gennemløbet rod – venstre barn – højre barn. Det betyder, at rodknuden først krydses, derefter dets venstre barn og til sidst det højre barn.
- Inorder Traversal (venstre-aktuel-højre): Besøg den aktuelle node efter at have besøgt alle noder inde i det venstre undertræ, men før du besøger en hvilken som helst node i det højre undertræ. Her er gennemløbet venstre barn – rod – højre barn. Det betyder, at det venstre barn krydses først, derefter dets rodknude og til sidst det højre barn.
- Postordregennemgang (venstre-højre-aktuel): Besøg den aktuelle node efter at have besøgt alle noderne i venstre og højre undertræ. Her er gennemløbet venstre barn – højre barn – rod. Det betyder, at det venstre barn først har krydset det højre barn og til sidst dets rodknude.
Breadth-First Search (BFS) algoritmer:
- Niveauordregennemgang: Besøg noder niveau-for-niveau og venstre-til-højre mode på samme niveau. Her er gennemløbet niveaumæssigt. Det betyder, at det mest venstre barn har traverseret først, og derefter har de andre børn på samme niveau fra venstre mod højre krydset.
3. Sletning i binært træ
Vi kan slette enhver node i det binære træ og omarrangere noderne efter sletning for igen at danne et gyldigt binært træ.
Algoritme til at slette en node i et binært træ:
- Start ved roden, find den dybeste og længst til højre knude i det binære træ og den knude, som vi vil slette.
- Erstat den dybeste nodes data med den node, der skal slettes.
- Slet derefter den dybeste knude længst til højre.
4. Søgning i binært træ
Vi kan søge efter et element i knudepunktet ved at bruge en hvilken som helst af gennemløbsteknikkerne.
Algoritme til at søge i en node i et binært træ:
- Start fra rodnoden.
- Tjek, om den aktuelle nodes værdi er lig med målværdien.
- Hvis den aktuelle nodes værdi er lig med målværdien, er denne node den påkrævede node.
- Ellers, hvis nodens værdi ikke er lig med målværdien, skal du starte søgningen i venstre og højre underordnede.
- Hvis vi ikke finder nogen node, hvis værdi er lig med målet, er værdien ikke til stede i træet.
Hjælpeoperationer på binært træ
- At finde højden på træet
- Find niveauet af en node i et binært træ
- At finde størrelsen på hele træet
Implementering af Binary Tree
Nedenfor er koden til indsættelse, sletning og gennemløb af det binære træ:
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øjre = NULL; retur temp; } // Funktion til at indsætte noder Node* insert(Node* root, int data) { // Hvis træet er tomt, bliver ny node roden if (root == NULL) { root = newNode(data); returnere rod; } // Kø for at krydse træet og finde positionen for at indsætte noden Node* køen[100]; int front = 0, bag = 0; kø[rear++] = rod; while (front != bag) { Node* temp = queue[front++]; // Indsæt node som det venstre underordnede af overordnede node if (temp->left == NULL) { temp->left = newNode(data); pause; } // Hvis det venstre underordnede barn ikke er null, skub det til køen else queue[rear++] = temp->left; // Indsæt node som det rigtige underordnede af overordnede node if (temp->right == NULL) { temp->right = newNode(data); pause; } // Hvis det rigtige barn ikke er null, skub det til køen else queue[rear++] = temp->right; } returnere rod; } /* Funktion til at slette den givne dybeste node (d_node) i binært træ */ void deletDeepest(Node* root, Node* d_node) { Node* kø[100]; int front = 0, bag = 0; kø[rear++] = rod; // Gør niveauordregennemgang indtil sidste node Node* temp; while (front != bagside) { temp = kø[front++]; if (temp == d_node) { temp = NULL; fri(d_node); Vend tilbage; } if (temp->right) { if (temp->right == d_node) { temp->right = NULL; fri(d_node); Vend tilbage; } andet kø[rear++] = temp->højre; } if (temp->venstre) { if (temp->venstre == d_node) { temp->venstre = NULL; fri(d_node); Vend tilbage; } else kø[rear++] = temp->venstre; } } } /* Funktion til at slette element i binært træ */ Node* deletion(Node* root, int key) { if (!root) return NULL; if (rod->venstre == NULL && root->højre == NULL) { if (rod->data == nøgle) returner NULL; ellers returnere rod; } Node* kø[100]; int front = 0, bag = 0; kø[rear++] = rod; Node* temp; Node* key_node = NULL; // Gennemgå niveaurækkefølge for at finde den dybeste node (temp) og node, der skal slettes (key_node), mens (front != rear) { temp = queue[front++]; hvis (temp->data == nøgle) key_node = temp; hvis (temp->venstre) kø[rear++] = temp->venstre; if (temp->right) queue[rear++] = temp->right; } if (key_node != NULL) { int x = temp->data; key_node->data = x; deleDeepest (rod, temp); } returnere rod; } // Inorder tree traversal (Venstre - Root - Right) void inorderTraversal(Node* root) { if (!root) return; inorderTraversal(rod->venstre); printf('%d ', root->data); inorderTraversal(rod->højre); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return; printf('%d ', root->data); preorderTraversal(rod->venstre); preorderTraversal(rod->højre); } // Postorder tree traversal (Venstre - Højre - Root) void postorderTraversal(Node* root) { if (root == NULL) return; postorderTraversal(rod->venstre); postorderTraversal(rod->højre); printf('%d ', root->data); } // Funktion for Level order tree traversal void levelorderTraversal(Node* root) { if (root == NULL) return; // Kø for gennemgang af niveauordre Node* kø[100]; int front = 0, bagside = 0; kø[rear++] = rod; while (front != bag) { Node* temp = queue[front++]; printf('%d ', temp->data); // Skub venstre barn i køen hvis (temp->venstre) kø[rear++] = temp->venstre; // Skub højre barn i køen hvis (temp->right) queue[rear++] = temp->right; } } /* Driverfunktion til at kontrollere ovenstående algoritme. */ int main() { Node* root = NULL; // Indsættelse af noder root = insert(root, 10); root = indsæt(rod, 20); root = indsæt(rod, 30); root = indsæt(rod, 40); printf('Forudbestil gennemgang: '); forudbestillingTraversal(rod); printf('
Ordergennemgang: '); inorderTraversal(rod); printf('
Postordergennemgang: '); postorderTraversal(rod); printf('
Gennemgang af niveaurækkefølge: '); niveauordreTraversal(rod); // Slet noden med data = 20 root = deletion(root, 20); printf('
Bestil gennemgang efter sletning: '); inorderTraversal(rod); retur 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 Queue q = new LinkedList(); q.offer(rod); while (!q.isEmpty()) { Node temp = q.poll(); // Indsæt node som det venstre underordnede af overordnede node if (temp.left == null) { temp.left = new Node(data); pause; } // Hvis det venstre underordnede barn ikke er null, skub det til //-køen else q.offer(temp.left); // Indsæt node som det rigtige underordnede af overordnede node if (temp.right == null) { temp.right = new Node(data); pause; } // Hvis det rigtige barn ikke er null, skub det til //-køen else q.offer(temp.right); } returnere rod; } /* funktion til at slette den givne dybeste node (d_node) i binært træ */ public static void deletDeepest(Node root, Node d_node) { Queue q = new LinkedList(); q.offer(rod); // Gør niveauordregennemgang indtil sidste node Node temp; while (!q.isEmpty()) { temp = q.poll(); if (temp == d_node) { temp = null; d_node = null; Vend tilbage; } if (temp.right != null) { if (temp.right == d_node) { temp.right = null; d_node = null; Vend tilbage; } andet q.offer(temp.right); } if (temp.left != null) { if (temp.left == d_node) { temp.left = null; d_node = null; Vend tilbage; } andet q.offer(temp.venstre); } } } /* funktion til at slette element i binært træ */ public static Node sletning(Node rod, int nøgle) { if (root == null) return null; if (root.left == null && root.right == null) { if (root.data == nøgle) returner null; ellers returnere rod; } Kø q = new LinkedList(); q.offer(rod); Node temp = ny Node(0); Node key_node = null; // Gør niveaurækkefølgegennemgang for at finde den dybeste // node(temp) og node, der skal slettes (key_node) while (!q.isEmpty()) { temp = q.poll(); hvis (temp.data == nøgle) 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 (rod, temp); } returnere rod; } // Inorder tree traversal (Venstre - Root - Right) public static void inorderTraversal(Node root) { if (root == null) return; inorderTraversal(root.left); System.out.print(root.data + ' '); inorderTraversal(root.right); } // Preorder tree traversal (Root - Left - Right) public static void preorderTraversal(Node root) { if (root == null) return; System.out.print(root.data + ' '); preorderTraversal(root.left); preorderTraversal(root.right); } // Postorder tree traversal (Venstre - Højre - Root) public static void postorderTraversal(Node root) { if (root == null) return; postorderTraversal(root.left); postorderTraversal(root.right); System.out.print(root.data + ' '); } // Funktion for Level order tree traversal public static void levelorderTraversal(Node root) { if (root == null) return; // Kø for gennemgang af niveauordre Kø q = new LinkedList(); q.offer(rod); while (!q.isEmpty()) { Node temp = q.poll(); System.out.print(temp.data + ' '); // Skub venstre barn i køen if (temp.left != null) q.offer(temp.left); // Skub højre barn i køen if (temp.right != null) q.offer(temp.right); } } /* Driverfunktion til at kontrollere ovenstående algoritme. */ public static void main(String[] args) { Node root = null; // Indsættelse af noder root = insert(root, 10); root = indsæt(rod, 20); root = indsæt(rod, 30); root = indsæt(rod, 40); System.out.print('Forudbestil gennemgang: '); forudbestillingTraversal(rod); System.out.print('
Ordregennemgang: '); inorderTraversal(rod); System.out.print('
Postordergennemgang: '); postorderTraversal(rod); System.out.print('
Gennemgang af niveaurækkefølge: '); niveauordreTraversal(rod); // Slet noden med data = 20 root = deletion(root, 20); System.out.print('
Bestil gennemgang efter sletning: '); inorderTraversal(rod); } } 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 Queue q = ny kø (); q.Enqueue(rod); while (q.Count != 0) { Node temp = q.Dequeue(); // Indsæt node som det venstre underordnede af overordnede node if (temp.left == null) { temp.left = new Node(data); pause; } // Hvis det venstre underordnede barn ikke er null, skal du skubbe det til køen ellers q.Enqueue(temp.left); // Indsæt node som det rigtige underordnede af overordnede node if (temp.right == null) { temp.right = new Node(data); pause; } // Hvis det rigtige barn ikke er null, skal du skubbe det til køen ellers q.Enqueue(temp.right); } returnere rod; } /* funktion til at slette den givne dybeste node (d_node) i binært træ */ public static void DeleteDeepest(Node root, Node d_node) { Queue q = ny kø (); q.Enqueue(rod); // Gør niveauordregennemgang indtil sidste node Node temp; while (q.Count != 0) { temp = q.Dequeue(); if (temp == d_node) { temp = null; d_node = null; Vend tilbage; } if (temp.right != null) { if (temp.right == d_node) { temp.right = null; d_node = null; Vend tilbage; } andet q.Enqueue(temp.right); } if (temp.left != null) { if (temp.left == d_node) { temp.left = null; d_node = null; Vend tilbage; } andet q.Enqueue(temp.venstre); } } } /* funktion til at slette element i binært træ */ public static Node Deletion(Node root, int key) { if (root == null) return null; if (root.left == null && root.right == null) { if (root.data == nøgle) returner null; ellers returnere rod; } Kø q = ny kø (); q.Enqueue(rod); Node temp = ny Node(0); Node key_node = null; // Gør niveaurækkefølgegennemgang for at finde den dybeste node (temp) og node, der skal slettes (key_node) while (q.Count != 0) { temp = q.Dequeue(); hvis (temp.data == nøgle) 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 (rod, temp); } returnere rod; } // Inorder tree traversal (Venstre - Root - Right) public static void InorderTraversal(Node root) { if (root == null) return; InorderTraversal(root.left); Console.Write(root.data + ' '); InorderTraversal(root.right); } // Preorder tree traversal (Root - Left - Right) public static void PreorderTraversal(Node root) { if (root == null) return; Console.Write(root.data + ' '); PreorderTraversal(root.left); PreorderTraversal(root.right); } // Postorder tree traversal (Venstre - Højre - Root) public static void PostorderTraversal(Node root) { if (root == null) return; PostorderTraversal(root.left); PostorderTraversal(root.right); Console.Write(root.data + ' '); } // Funktion for niveauordenstrægennemgang public static void LevelorderTraversal(Noderod) { if (rod == null) return; // Kø for gennemgang af niveauordre Kø q = ny kø (); q.Enqueue(rod); while (q.Count != 0) { Node temp = q.Dequeue(); Console.Write(temp.data + ' '); // Skub venstre barn i køen if (temp.left != null) q.Enqueue(temp.left); // Skub højre barn i køen if (temp.right != null) q.Enqueue(temp.right); } } /* Driverfunktion til at kontrollere ovenstående algoritme. */ public static void Main(string[] args) { Node root = null; // Indsættelse af noder root = Indsæt(rod, 10); root = Indsæt(rod, 20); root = Indsæt(rod, 30); root = Indsæt(rod, 40); Console.Write('Forudbestil traversal: '); ForudbestilTraversal(rod); Console.Write('
I ordregennemgang: '); InorderTraversal(rod); Console.Write('
Postorder-gennemgang: '); PostorderTraversal(rod); Console.Write('
Gennemgang af niveaurækkefølge: '); LevelorderTraversal(rod); // Slet noden med data = 20 root = Deletion(root, 20); Console.Write('
Bestil gennemgang efter sletning: '); InorderTraversal(rod); } } 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 queue q; q.push(rod); while (!q.empty()) { Node* temp = q.front(); q.pop(); // Indsæt node som venstre underordnede af den overordnede node if (temp->left == NULL) { temp->left = new Node(data); pause; } // Hvis det venstre barn ikke er null, skub det til //-køen ellers q.push(temp->left); // Indsæt node som det rigtige underordnede af overordnede node if (temp->right == NULL) { temp->right = new Node(data); pause; } // Hvis det rigtige barn ikke er null, skub det til //-køen ellers q.push(temp->right); } returnere rod; } /* funktion til at slette den givne dybeste node (d_node) i binært træ */ void deletDeepest(Node* root, Node* d_node) { kø q; q.push(rod); // Gør niveauordregennemgang indtil sidste node Node* temp; while (!q.empty()) { temp = q.front(); q.pop(); if (temp == d_node) { temp = NULL; slet (d_node); Vend tilbage; } if (temp->right) { if (temp->right == d_node) { temp->right = NULL; slet (d_node); Vend tilbage; } andet q.push(temp->højre); } if (temp->venstre) { if (temp->venstre == d_node) { temp->venstre = NULL; slet (d_node); Vend tilbage; } andet q.push(temp->venstre); } } } /* funktion til at slette element i binært træ */ Node* deletion(Node* root, int key) { if (!root) return NULL; if (rod->venstre == NULL && root->højre == NULL) { if (rod->data == nøgle) returner NULL; ellers returnere rod; } kø q; q.push(rod); Node* temp; Node* key_node = NULL; // Gør niveaurækkefølgegennemgang for at finde den dybeste // node(temp) og node, der skal slettes (key_node) mens (!q.empty()) { temp = q.front(); q.pop(); hvis (temp->data == nøgle) key_node = temp; if (temp->venstre) q.push(temp->venstre); if (temp->right) q.push(temp->right); } if (key_node != NULL) { int x = temp->data; key_node->data = x; deleDeepest (rod, temp); } returnere rod; } // Inorder tree traversal (Venstre - Root - Right) void inorderTraversal(Node* root) { if (!root) return; inorderTraversal(rod->venstre); cout < < root->data < < ' '; inorderTraversal(root->højre); } // Preorder tree traversal (Root - Left - Right) void preorderTraversal(Node* root) { if (!root) return; cout < < root->data < < ' '; preorderTraversal(root->venstre); preorderTraversal(rod->højre); } // Postorder tree traversal (Venstre - Højre - Root) void postorderTraversal(Node* root) { if (root == NULL) return; postorderTraversal(rod->venstre); postorderTraversal(rod->højre); cout < < root->data < < ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) { if (root == NULL) return; // Queue for level order traversal queue q; q.push(rod); 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); // Skub højre barn i køen hvis (temp->right) q.push(temp->right); } } /* Driverfunktion til at kontrollere ovenstående algoritme. */ int main() { Node* root = NULL; // Indsættelse af noder root = insert(root, 10); root = indsæt(rod, 20); root = indsæt(rod, 30); root = indsæt(rod, 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
Kompleksitetsanalyse af binære træoperationer
| Operationer | Tidskompleksitet | Rumkompleksitet |
|---|---|---|
| Indskud | PÅ) | PÅ) |
| Forudbestil gennemkørsel | PÅ) | PÅ) |
| Inorder Traversal | PÅ) | PÅ) |
| Postordregennemgang | PÅ) | PÅ) |
| Level Order Traversal | PÅ) | PÅ) |
| Sletning | PÅ) | PÅ) |
| Søger | PÅ) | PÅ) |
Vi kan bruge Morris Traversal at krydse alle noderne i det binære træ i O(1) tid.
Fordele ved Binary Tree
- Effektiv søgning: Binære træer er effektive, når der søges efter et specifikt element, da hver node højst har to underordnede noder, hvilket giver mulighed for Hukommelseseffektiv: Binære træer kræver mindre hukommelse sammenlignet med andre trædatastrukturer, derfor er de hukommelseseffektive.
- Binære træer er relativt nemme at implementere og forstå, da hver node højst har to børn, venstre barn og højre barn.
Ulemper ved binært træ
- Begrænset struktur: Binære træer er begrænset til to underordnede noder pr. node, hvilket kan begrænse deres anvendelighed i visse applikationer. For eksempel, hvis et træ kræver mere end to underordnede noder pr. node, kan en anden træstruktur være mere egnet.
- Ubalancerede træer: Ubalancerede binære træer, hvor det ene undertræ er væsentligt større end det andet, kan føre til ineffektive søgeoperationer. Dette kan forekomme, hvis træet ikke er korrekt afbalanceret, eller hvis data indsættes i en ikke-tilfældig rækkefølge.
- Plads ineffektivitet: Binære træer kan være pladsineffektive sammenlignet med andre datastrukturer. Dette skyldes, at hver node kræver to underordnede pointere, hvilket kan være en betydelig mængde hukommelsesomkostninger for store træer.
- Langsom ydeevne i worst-case scenarier: I det værste tilfælde kan et binært træ blive degenereret eller skævt, hvilket betyder, at hver node kun har ét barn. I dette tilfælde kan søgeoperationer degradere til O(n) tidskompleksitet, hvor n er antallet af noder i træet.
Anvendelser af binært træ
- Binary Tree kan bruges til repræsentere hierarkiske data .
- Huffman Coding træer bruges i datakomprimeringsalgoritmer .
- Prioritetskø er en anden anvendelse af binært træ, der bruges til at søge maksimum eller minimum i O(1) tidskompleksitet.
- Nyttigt til at indeksere segmenteret i databasen er nyttigt til lagring af cache i systemet,
- Binære træer kan bruges til at implementere beslutningstræer, en type maskinlæringsalgoritme, der bruges til klassificering og regressionsanalyse.
Ofte stillede spørgsmål om binært træ
1. Hvad er et binært træ?
Et binært træ er en ikke-lineær datastruktur bestående af noder, hvor hver node højst har to børn (venstre barn og højre barn).
2. Hvad er typerne af binære træer?
Binære træer kan klassificeres i forskellige typer, herunder fulde binære træer, komplette binære træer, perfekte binære træer, balancerede binære træer (såsom AVL-træer og rød-sorte træer) og degenererede (eller patologiske) binære træer.
3. Hvad er højden af et binært træ?
Højden af et binært træ er længden af den længste vej fra rodknuden til en bladknude. Det repræsenterer antallet af kanter i den længste vej fra rodknuden til en bladknude.
4. Hvad er dybden af en node i et binært træ?
Dybden af en knude i et binært træ er længden af stien fra rodknuden til den pågældende knude. Dybden af rodknuden er 0.
5. Hvordan udfører man trægennemgang i et binært træ?
Trægennemgang i et binært træ kan udføres på forskellige måder: I-order traversal, Pre-order traversal, Post-order traversal og Level-order traversal (også kendt som bredde-først traversal).
6. Hvad er en Inorder-gennemgang i binært træ?
I Inorder traversal besøges noder rekursivt i denne rækkefølge: venstre barn, rod, højre barn. Denne gennemkøring resulterer i, at noder besøges i ikke-faldende rækkefølge i et binært søgetræ.
7. Hvad er en Preorder-gennemgang i binært træ?
I Preorder traversal besøges noder rekursivt i denne rækkefølge: rod, venstre barn, højre barn. Denne gennemgang resulterer i, at rodknude er den første knude, der skal besøges.
8. Hvad er en Postorder-gennemgang i binært træ?
I Postorder-traversal besøges noder rekursivt i denne rækkefølge: venstre barn, højre barn og rod. Denne gennemgang resulterer i, at rodknude er den sidste knude, der skal besøges.
9. Hvad er forskellen mellem et binært træ og et binært søgetræ?
Et binært træ er en hierarkisk datastruktur, hvor hver node højst har to børn, hvorimod et binært søgetræ er en type binært træ, hvor det venstre underordnede af en knude indeholder værdier, der er mindre end nodens værdi, og det højre underordnede indeholder værdier større end nodens værdi.
10. Hvad er et balanceret binært træ?
Et balanceret binært træ er et binært træ, hvor højden af venstre og højre undertræ i hver knude højst er forskellig med én. Balancerede træer hjælper med at opretholde effektive operationer såsom søgning, indsættelse og sletning med tidskompleksiteter tæt på O(log n).
Konklusion:
Træ er en hierarkisk datastruktur. De vigtigste anvendelser af træer omfatter vedligeholdelse af hierarkiske data, giver moderat adgang og indsæt/slet-operationer. Binære træer er særlige tilfælde af træer, hvor hver knude højst har to børn.
Relaterede artikler:
- Egenskaber af binært træ
- Typer af binære træer
