TechCodeview

Binärbaum ist eine nichtlineare Datenstruktur vom Baumtyp, die hauptsächlich zum Sortieren und Suchen verwendet wird, da sie Daten in hierarchischer Form speichert. In diesem Abschnitt lernen wir das Implementierung der binären Baumdatenstruktur in Java . Bietet außerdem eine kurze Beschreibung der binären Baumdatenstruktur.

Binärer Baum

Ein Baum, in dem jeder Knoten (übergeordneter Knoten) höchstens zwei untergeordnete Knoten (links und rechts) hat, wird Binärbaum genannt. Der oberste Knoten wird Wurzelknoten genannt. In einem Binärbaum enthält ein Knoten die Daten und den Zeiger (Adresse) des linken und rechten untergeordneten Knotens.

Der Höhe eines Binärbaums ist die Anzahl der Kanten zwischen der Wurzel des Baumes und sein am weitesten entferntes (tiefstes) Blatt. Wenn der Baum ist leer , die Höhe ist 0 . Die Höhe des Knotens wird mit bezeichnet H .

Die Höhe des obigen Binärbaums beträgt 2.

Mit der folgenden Formel können wir die Anzahl der Blätter und Knoten berechnen.

Ganzzahl-Doppel-Java

• Die maximale Anzahl von Blattknoten ist ein Binärbaum: 2^H
• Die maximale Anzahl von Knoten ist ein Binärbaum: 2^h+1-1

Wobei h die Höhe des Binärbaums ist.

Beispiel eines Binärbaums

Arten von Binärbäumen

Es gibt die folgenden Arten von Binärbäumen in der Datenstruktur:

1. Vollständiger/streng binärer Baum
2. Kompletter Binärbaum
3. Perfekter Binärbaum
4. Binärbaum ausgleichen
5. Verwurzelter Binärbaum
6. Degenerierter/pathologischer Binärbaum
7. Erweiterter Binärbaum
8. Verzerrter Binärbaum
   1. Linksschiefer Binärbaum
   2. Rechtsschiefer Binärbaum
9. Threaded-Binärbaum
   1. Single-Threaded-Binärbaum
   2. Doppelthread-Binärbaum

Binärbaum-Implementierung in Java

Es gibt viele Möglichkeiten, einen Binärbaum zu implementieren. In diesem Abschnitt implementieren wir einen Binärbaum mithilfe der LinkedList-Datenstruktur. Daneben werden wir auch die Durchlaufbefehle implementieren, einen Knoten durchsuchen und einen Knoten in einen Binärbaum einfügen.

Implementierung eines Binärbaums mithilfe von LinkedList

Algorithmus

Definieren Sie eine Knotenklasse, die drei Attribute enthält, nämlich: Daten links und rechts. Hier repräsentiert left das linke Kind des Knotens und right das rechte Kind des Knotens.

• Wenn ein Knoten erstellt wird, werden die Daten an das Datenattribut des Knotens übergeben und sowohl links als auch rechts werden auf Null gesetzt.
• Definieren Sie eine andere Klasse mit einem Attributstamm.
• Root stellt den Wurzelknoten des Baums dar und initialisiert ihn auf Null.

einfügen()fügt dem Baum einen neuen Knoten hinzu:
• Es prüft, ob die Wurzel null ist, was bedeutet, dass der Baum leer ist. Der neue Knoten wird als Root hinzugefügt.
• Andernfalls wird Root zur Warteschlange hinzugefügt.
• Der variable Knoten repräsentiert den aktuellen Knoten.
• Zunächst wird geprüft, ob ein Knoten ein linkes und ein rechtes Kind hat. Wenn ja, werden beide Knoten zur Warteschlange hinzugefügt.
• Wenn das linke Kind nicht vorhanden ist, wird der neue Knoten als linkes Kind hinzugefügt.
• Wenn der linke Knoten vorhanden ist, wird der neue Knoten als rechter untergeordneter Knoten hinzugefügt.
in Ordnung()zeigt die Knoten des Baums in der richtigen Reihenfolge an.
• Es durchläuft den gesamten Baum und gibt dann das linke Kind gefolgt von der Wurzel und dann das rechte Kind aus.

BinarySearchTree.java

 public class BinarySearchTree { //Represent the node of binary tree public static class Node{ int data; Node left; Node right; public Node(int data){ //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinarySearchTree(){ root = null; } //factorial() will calculate the factorial of given number public int factorial(int num) { int fact = 1; if(num == 0) return 1; else { while(num > 1) { fact = fact * num; num--; } return fact; } } //numOfBST() will calculate the total number of possible BST by calculating Catalan Number for given key public int numOfBST(int key) { int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key)); return catalanNumber; } public static void main(String[] args) { BinarySearchTree bt = new BinarySearchTree(); //Display total number of possible binary search tree with key 5 System.out.println('Total number of possible Binary Search Trees with given key: ' + bt.numOfBST(5)); } } 

Ausgabe:

 Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7 

Binärbaumoperationen

Die folgenden Operationen können an einem Binärbaum ausgeführt werden:

• Einfügen
• Streichung
• Suchen
• Durchquerung

Java-Programm zum Einfügen eines Knotens in den Binärbaum

BinaryTreeInsert.java

 public class BinaryTreeInsert { public static void main(String[] args) { new BinaryTreeInsert().run(); } static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } public void run() { Node rootnode = new Node(25); System.out.println('Building tree with root value ' + rootnode.value); System.out.println('================================='); insert(rootnode, 11); insert(rootnode, 15); insert(rootnode, 16); insert(rootnode, 23); insert(rootnode, 79); } public void insert(Node node, int value) { if (value node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println(' Inserted ' + value + ' to right of Node ' + node.value); node.right = new Node(value); } } } } 

Ausgabe:

 Building tree with root value 25 ================================= Inserted 11 to left of Node 25 Inserted 15 to right of Node 11 Inserted 16 to right of Node 15 Inserted 23 to right of Node 16 Inserted 79 to right of Node 25 

Java-Programm zum Löschen eines Knotens in Java

Algorithmus

1. 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.
2. Ersetzen Sie die Daten des tiefsten Knotens ganz rechts durch den Knoten, der gelöscht werden soll.
3. Dann löschen Sie den tiefsten Knoten ganz rechts.

Betrachten Sie die folgende Abbildung.

DeleteNode.java

Konvertieren Sie die Zeichenfolge in JSON Java

 import java.util.LinkedList; import java.util.Queue; public class DeleteNode { // A binary tree node has key, pointer to // left child and a pointer to right child static class Node { int key; Node left, right; // Constructor Node(int key) { this.key = key; left = null; right = null; } } static Node root; static Node temp = root; // Inorder traversal of a binary tree static void inorder(Node temp) { if (temp == null) return; inorder(temp.left); System.out.print(temp.key + ' '); inorder(temp.right); } // Function to delete deepest // element in binary tree static void deleteDeepest(Node root, Node delNode) { Queue q = new LinkedList(); q.add(root); Node temp = null; // Do level order traversal until last node while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp == delNode) { temp = null; return; } if (temp.right!=null) { if (temp.right == delNode) { temp.right = null; return; } else q.add(temp.right); } if (temp.left != null) { if (temp.left == delNode) { temp.left = null; return; } else q.add(temp.left); } } } // Function to delete given element // in binary tree static void delete(Node root, int key) { if (root == null) return; if (root.left == null && root.right == null) { if (root.key == key) { root=null; return; } else return; } Queue q = new LinkedList(); q.add(root); Node temp = null, keyNode = null; // Do level order traversal until // we find key and last node. while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp.key == key) keyNode = temp; if (temp.left != null) q.add(temp.left); if (temp.right != null) q.add(temp.right); } if (keyNode != null) { int x = temp.key; deleteDeepest(root, temp); keyNode.key = x; } } // Driver code public static void main(String args[]) { root = new Node(10); root.left = new Node(11); root.left.left = new Node(7); root.left.right = new Node(12); root.right = new Node(9); root.right.left = new Node(15); root.right.right = new Node(8); System.out.print('Inorder traversal before deletion: '); inorder(root); //node to delete int key = 7; delete(root, key); System.out.print('
Inorder traversal after deletion: '); inorder(root); } } 

Ausgabe:

 Inorder traversal before deletion: 7 11 12 10 15 9 8 Inorder traversal after deletion: 8 11 12 10 15 9 

Java-Programm zum Durchsuchen eines Knotens im Binärbaum

Algorithmus

• Definieren Sie eine Knotenklasse, die über drei Attribute verfügt, nämlich: Daten links und rechts. Hier repräsentiert left das linke Kind des Knotens und right das rechte Kind des Knotens.
• Wenn ein Knoten erstellt wird, werden die Daten an das Datenattribut des Knotens übergeben und sowohl links als auch rechts werden auf Null gesetzt.
• Definieren Sie eine andere Klasse, die über zwei Attribute „root“ und „flag“ verfügt.
  1. Root stellt den Wurzelknoten des Baums dar und initialisiert ihn auf Null.
  2. Das Flag wird verwendet, um zu überprüfen, ob der angegebene Knoten im Baum vorhanden ist oder nicht. Zunächst wird es auf „false“ gesetzt.

searchNode()sucht nach einem bestimmten Knoten im Binärbaum:
• Es prüft, ob die Wurzel null ist, was bedeutet, dass der Baum leer ist.
• Wenn der Baum nicht leer ist, werden die Daten von temp mit dem Wert verglichen. Wenn sie gleich sind, wird das Flag auf „true“ gesetzt und zurückgegeben.
• Durchqueren Sie den linken Teilbaum, indem Sie searchNode() rekursiv aufrufen, und prüfen Sie, ob der Wert im linken Teilbaum vorhanden ist.
• Durchqueren Sie den rechten Teilbaum, indem Sie searchNode() rekursiv aufrufen, und prüfen Sie, ob der Wert im rechten Teilbaum vorhanden ist.

SearchBinaryTree.java

 public class SearchBinaryTree { //Represent a node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public static boolean flag = false; public SearchBinaryTree() { root = null; } //searchNode() will search for the particular node in the binary tree public void searchNode(Node temp, int value) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); } else { //If value is found in the given binary tree then, set the flag to true if(temp.data == value) { flag = true; return; } //Search in left subtree if(flag == false && temp.left != null) { searchNode(temp.left, value); } //Search in right subtree if(flag == false && temp.right != null) { searchNode(temp.right, value); } } } public static void main(String[] args) { SearchBinaryTree bt = new SearchBinaryTree(); //Add nodes to the binary tree bt.root = new Node(11); bt.root.left = new Node(8); bt.root.right = new Node(12); bt.root.left.left = new Node(78); bt.root.right.left = new Node(23); bt.root.right.right = new Node(36); //Search for node 5 in the binary tree bt.searchNode(bt.root, 23); if(flag) System.out.println('Element is present in the binary tree.'); else System.out.println('Element is not present in the binary tree.'); } } 

Ausgabe:

 Element is present in the binary tree. 

Durchquerung des Binärbaums

Hinweis: Außer den oben genannten drei Durchquerungen gibt es eine weitere Durchquerungsreihenfolge, die als Grenzdurchquerung bezeichnet wird.

Java-Programm zum Durchlaufen von Inorder-, Preorder- und Postorder-Traversal

BinaryTree.java

 public class BinaryTree { // first node private Node root; BinaryTree() { root = null; } // Class representing tree nodes static class Node { int value; Node left; Node right; Node(int value) { this.value = value; left = null; right = null; } public void displayData() { System.out.print(value + ' '); } } public void insert(int i) { root = insert(root, i); } //Inserting node - recursive method public Node insert(Node node, int value) { if(node == null){ return new Node(value); } // Move to the left if passed value is // less than the current node if(value node.value) { node.right = insert(node.right, value); } return node; } // Search node in binary search tree public Node find(int searchedValue) { Node current = root; while(current.value != searchedValue) { if(searchedValue = current = current.right; if(current == null) { return null; } } return current; } // For traversing in order public void inOrder(Node node) { if(node != null) { inOrder(node.left); node.displayData(); inOrder(node.right); } } // Preorder traversal public void preOrder(Node node) { if(node != null){ node.displayData(); preOrder(node.left); preOrder(node.right); } } // Postorder traversal public void postOrder(Node node) { if(node != null) { postOrder(node.left); postOrder(node.right); node.displayData(); } } public static void main(String[] args) { BinaryTree bst = new BinaryTree(); bst.insert(34); bst.insert(56); bst.insert(12); bst.insert(89); bst.insert(67); bst.insert(90); System.out.println('Inorder traversal of binary tree'); bst.inOrder(bst.root); System.out.println(); System.out.println('Preorder traversal of binary tree'); bst.preOrder(bst.root); System.out.println(); System.out.println('Postorder traversal of binary tree'); bst.postOrder(bst.root); System.out.println(); } } 

Ausgabe:

 Inorder traversal of binary tree 12 34 56 67 89 90 Preorder traversal of binary tree 34 12 56 89 67 90 Postorder traversal of binary tree 12 67 90 89 56 34 

Neben den oben genannten Operationen können wir auch Operationen wie großer Knoten, kleinster Knoten und Summe aller Knoten ausführen.

Java-Programm zum Finden des größten Knotens im Binärbaum

LargestNode.java

Aufteilen von Zeichenfolgen in C++

 public class LargestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public LargestNode() { root = null; } //largestElement() will find out the largest node in the binary tree public int largestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); return 0; } else { int leftMax, rightMax; //Max will store temp's data int max = temp.data; //It will find largest element in left subtree if(temp.left != null){ leftMax = largestElement(temp.left); //Compare max with leftMax and store greater value into max max = Math.max(max, leftMax); } //It will find largest element in right subtree if(temp.right != null){ rightMax = largestElement(temp.right); //Compare max with rightMax and store greater value into max max = Math.max(max, rightMax); } return max; } } public static void main(String[] args) { LargestNode bt = new LargestNode(); //Add nodes to the binary tree bt.root = new Node(90); bt.root.left = new Node(99); bt.root.right = new Node(23); bt.root.left.left = new Node(96); bt.root.right.left = new Node(45); bt.root.right.right = new Node(6); bt.root.right.left = new Node(13); bt.root.right.right = new Node(77); //Display largest node in the binary tree System.out.println('Largest element in the binary tree: ' + bt.largestElement(bt.root)); } } 

Ausgabe:

 Largest element in the binary tree: 99 

Java-Programm zum Finden des kleinsten Knotens im Binärbaum

Algorithmus

1. Definieren Sie eine Knotenklasse mit drei Attributen: Daten, links und rechts. Hier repräsentiert left das linke Kind des Knotens und right das rechte Kind des Knotens.
2. Wenn ein Knoten erstellt wird, werden die Daten an das Datenattribut des Knotens übergeben und sowohl links als auch rechts werden auf Null gesetzt.
3. Definieren Sie eine andere Klasse, die über ein Attribut root verfügt.
   Wurzelstellt den Wurzelknoten des Baums dar und initialisiert ihn auf Null.

kleinstesElement()ermittelt den kleinsten Knoten im Binärbaum:
1. Es prüft, ob root ist null , was bedeutet, dass der Baum leer ist.
2. Wenn der Baum nicht leer ist, definieren Sie eine Variable min, die die Daten von temp speichert.
3. Ermitteln Sie den minimalen Knoten im linken Teilbaum, indem Sie smallElement() rekursiv aufrufen. Speichern Sie diesen Wert in leftMin. Vergleichen Sie den Wert von min mit leftMin und speichern Sie das Minimum von zwei bis min.
4. Ermitteln Sie den minimalen Knoten im rechten Teilbaum, indem Sie smallElement() rekursiv aufrufen. Speichern Sie diesen Wert in rightMin. Vergleichen Sie den Wert von min mit rightMin und speichern Sie das Maximum von zwei bis min.
5. Am Ende enthält min den kleinsten Knoten im Binärbaum.

SmallestNode.java

 public class SmallestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public SmallestNode() { root = null; } //smallestElement() will find out the smallest node in the binary tree public int smallestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); return 0; } else { int leftMin, rightMin; //Min will store temp's data int min = temp.data; //It will find smallest element in left subtree if(temp.left != null) { leftMin = smallestElement(temp.left); //If min is greater than leftMin then store the value of leftMin into min min = Math.min(min, leftMin); } //It will find smallest element in right subtree if(temp.right != null) { rightMin = smallestElement(temp.right); //If min is greater than rightMin then store the value of rightMin into min min = Math.min(min, rightMin); } return min; } } public static void main(String[] args) { SmallestNode bt = new SmallestNode(); //Add nodes to the binary tree bt.root = new Node(9); bt.root.left = new Node(5); bt.root.right = new Node(7); bt.root.left.left = new Node(1); bt.root.right.left = new Node(2); bt.root.right.right = new Node(8); bt.root.right.left = new Node(4); bt.root.right.right = new Node(3); //Display smallest node in the binary tree System.out.println('Smallest element in the binary tree: ' + bt.smallestElement(bt.root)); } } 

Ausgabe:

 Smallest element in the binary tree: 1 

Java-Programm zum Ermitteln der maximalen Breite eines Binärbaums

Algorithmus

1. Definieren Sie eine Knotenklasse, die über drei Attribute verfügt, nämlich: Daten links und rechts. Hier repräsentiert left das linke Kind des Knotens und right das rechte Kind des Knotens.
2. Wenn ein Knoten erstellt wird, werden die Daten an das Datenattribut des Knotens übergeben und sowohl links als auch rechts werden auf Null gesetzt.
3. Definieren Sie eine andere Klasse, die über ein Attribut root verfügt.
   Wurzelstellt den Wurzelknoten des Baums dar und initialisiert ihn auf Null.

1. Die Variable maxWidth speichert die maximale Anzahl an Knoten, die auf jeder Ebene vorhanden sind.
2. Die Warteschlange wird zum Durchlaufen des Binärbaums auf Ebenen verwendet.
3. Es prüft, ob die Wurzel null ist, was bedeutet, dass der Baum leer ist.
4. Wenn nicht, fügen Sie den Root-Knoten zur Warteschlange hinzu. Die Variable nodesInLevel verfolgt die Anzahl der Knoten in jeder Ebene.
5. Wenn nodesInLevel > 0, entfernen Sie den Knoten vom Anfang der Warteschlange und fügen Sie seinen linken und rechten untergeordneten Knoten der Warteschlange hinzu. Bei der ersten Iteration wird Knoten 1 entfernt und seine untergeordneten Knoten 2 und 3 werden zur Warteschlange hinzugefügt. In der zweiten Iteration wird Knoten 2 entfernt, seine untergeordneten Knoten 4 und 5 werden zur Warteschlange hinzugefügt und so weiter.
6. MaxWidth speichert max(maxWidth, nodesInLevel). Es stellt also zu jedem Zeitpunkt die maximale Anzahl an Knoten dar.
7. Dies wird so lange fortgesetzt, bis alle Ebenen des Baums durchlaufen sind.

BinaryTree.java

 import java.util.LinkedList; import java.util.Queue; public class BinaryTree { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinaryTree() { root = null; } //findMaximumWidth() will find out the maximum width of the given binary tree public int findMaximumWidth() { int maxWidth = 0; //Variable nodesInLevel keep tracks of number of nodes in each level int nodesInLevel = 0; //queue will be used to keep track of nodes of tree level-wise Queue queue = new LinkedList(); //Check if root is null, then width will be 0 if(root == null) { System.out.println('Tree is empty'); return 0; } else { //Add root node to queue as it represents the first level queue.add(root); while(queue.size() != 0) { //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue nodesInLevel = queue.size(); //maxWidth will hold maximum width. //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel maxWidth = Math.max(maxWidth, nodesInLevel); //If variable nodesInLevel contains more than one node //then, for each node, we'll add left and right child of the node to the queue while(nodesInLevel > 0) { Node current = queue.remove(); if(current.left != null) queue.add(current.left); if(current.right != null) queue.add(current.right); nodesInLevel--; } } } return maxWidth; } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); //Add nodes to the binary tree bt.root = new Node(1); bt.root.left = new Node(2); bt.root.right = new Node(3); bt.root.left.left = new Node(4); bt.root.left.right = new Node(5); bt.root.right.left = new Node(6); bt.root.right.right = new Node(7); bt.root.left.left.left = new Node(8); //Display the maximum width of given tree System.out.println('Maximum width of the binary tree: ' + bt.findMaximumWidth()); } } 

Ausgabe:

 Maximum width of the binary tree: 4