TechCodeview

Binaire boom is een niet-lineaire gegevensstructuur van het boomtype die voornamelijk wordt gebruikt voor sorteren en zoeken, omdat ze gegevens in hiërarchische vorm opslaan. In dit gedeelte leren we de implementatie van binaire boomdatastructuur in Java . Biedt ook een korte beschrijving van de datastructuur van de binaire boom.

Binaire boom

Een boom waarin elk knooppunt (ouder) maximaal twee onderliggende knooppunten heeft (links en rechts), wordt een binaire boom genoemd. Het bovenste knooppunt wordt het hoofdknooppunt genoemd. In een binaire boom bevat een knooppunt de gegevens en de aanwijzer (adres) van het linker en rechter kindknooppunt.

De hoogte van een binaire boom is de aantal randen tussen de wortel van de boom en het verste (diepste) blad. Als de boom dat is leeg , de hoogte bedraagt 0 . De hoogte van het knooppunt wordt aangegeven met H .

De hoogte van de bovenstaande binaire boom is 2.

We kunnen het aantal bladeren en knooppunten berekenen met behulp van de volgende formule.

10 van een 100

• Het maximale aantal bladknooppunten is een binaire boom: 2^H
• Het maximale aantal knooppunten is een binaire boom: 2^u+1-1

Waarbij h de hoogte van de binaire boom is.

Voorbeeld van binaire boom

Soorten binaire boom

Er zijn de volgende soorten binaire bomen in de datastructuur:

1. Volledige/strikt binaire boom
2. Volledige binaire boom
3. Perfecte binaire boom
4. Balans binaire boom
5. Gewortelde binaire boom
6. Gedegenereerde/pathologische binaire boom
7. Uitgebreide binaire boom
8. Scheve binaire boom
   1. Linksscheve binaire boom
   2. Rechtsscheve binaire boom
9. Binaire boom met schroefdraad
   1. Binaire boom met enkele schroefdraad
   2. Dubbele schroefdraad binaire boom

Implementatie van binaire bomen in Java

Er zijn veel manieren om binaire boom te implementeren. In deze sectie zullen we een binaire boom implementeren met behulp van de LinkedList-gegevensstructuur. Daarnaast zullen we ook de verplaatsingsopdrachten implementeren, een knooppunt zoeken en een knooppunt in een binaire boom invoegen.

Hoe str naar int te converteren

Implementatie van binaire boom met behulp van LinkedList

Algoritme

Definieer een knooppuntklasse die drie attributen bevat, namelijk: gegevens links en rechts. Hier vertegenwoordigt links het linkerkind van het knooppunt en vertegenwoordigt rechts het rechterkind van het knooppunt.

• Wanneer een knooppunt wordt gemaakt, worden gegevens doorgegeven aan het gegevensattribuut van het knooppunt en worden zowel links als rechts op nul ingesteld.
• Definieer een andere klasse die een attribuutwortel heeft.
• Root vertegenwoordigt het hoofdknooppunt van de boom en initialiseert deze op nul.

invoegen()zal een nieuw knooppunt aan de boom toevoegen:
• Het controleert of de root nul is, wat betekent dat de boom leeg is. Het zal het nieuwe knooppunt als root toevoegen.
• Anders wordt root aan de wachtrij toegevoegd.
• Het variabele knooppunt vertegenwoordigt het huidige knooppunt.
• Eerst wordt gecontroleerd of een knooppunt een linker- en rechterkind heeft. Zo ja, dan worden beide knooppunten aan de wachtrij toegevoegd.
• Als het linkerkind niet aanwezig is, wordt het nieuwe knooppunt als het linkerkind toegevoegd.
• Als de linker aanwezig is, wordt het nieuwe knooppunt als het rechter kind toegevoegd.
in volgorde()zal de knooppunten van de boom op volgorde weergeven.
• Het doorkruist de hele boom en drukt vervolgens het linkerkind af, gevolgd door de root en vervolgens gevolgd door het rechterkind.

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)); } } 

Uitgang:

 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 

Binaire boombewerkingen

De volgende bewerkingen kunnen worden uitgevoerd op een binaire boom:

• Plaatsing
• Verwijdering
• Zoekopdracht
• Traversaal

Java-programma om een ​​knooppunt in de binaire boom in te voegen

BinaryTreeInsert.java

aws roodverschuiving

 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); } } } } 

Uitgang:

 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-programma om een ​​knooppunt in Java te verwijderen

Algoritme

1. Begin bij de wortel en zoek het diepste en meest rechtse knooppunt in de binaire boom en het knooppunt dat we willen verwijderen.
2. Vervang de gegevens van het meest rechtse knooppunt door het knooppunt dat moet worden verwijderd.
3. Verwijder vervolgens het diepste meest rechtse knooppunt.

Beschouw de volgende figuur.

VerwijderNode.java

np.uniek

 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); } } 

Uitgang:

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

Java-programma om een ​​knooppunt in de binaire boom te doorzoeken

Algoritme

• Definieer de knooppuntklasse die drie attributen heeft, namelijk: gegevens links en rechts. Hier vertegenwoordigt links het linkerkind van het knooppunt en vertegenwoordigt rechts het rechterkind van het knooppunt.
• Wanneer een knooppunt wordt gemaakt, worden gegevens doorgegeven aan het gegevensattribuut van het knooppunt en worden zowel links als rechts op nul ingesteld.
• Definieer een andere klasse die twee attributen root en flag heeft.
  1. Root vertegenwoordigt het hoofdknooppunt van de boom en initialiseert dit op nul.
  2. De vlag wordt gebruikt om te controleren of het gegeven knooppunt in de boom aanwezig is of niet. In eerste instantie zal deze op false staan.

zoekknooppunt()zal zoeken naar een bepaald knooppunt in de binaire boom:
• Het controleert of de root nul is, wat betekent dat de boom leeg is.
• Als de boom niet leeg is, worden de gegevens van de temperatuur vergeleken met de waarde. Als ze gelijk zijn, wordt de vlag op waar gezet en geretourneerd.
• Doorloop de linker subboom door searchNode() recursief aan te roepen en controleer of de waarde aanwezig is in de linker subboom.
• Doorloop de rechter subboom door searchNode() recursief aan te roepen en controleer of de waarde aanwezig is in de rechter subboom.

ZoekBinaryTree.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.'); } } 

Uitgang:

 Element is present in the binary tree. 

Traversal van binaire bomen

Opmerking: Behalve de bovengenoemde drie verplaatsingen is er nog een andere verplaatsingsvolgorde, die grensovergang wordt genoemd.

Java-programma voor het doorkruisen van inorder-, pre-order- en 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(); } } 

Uitgang:

 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 

Naast de bovenstaande bewerkingen kunnen we ook bewerkingen uitvoeren zoals groot knooppunt, kleinste knooppunt en de som van alle knooppunten.

Java-programma om het grootste knooppunt in de binaire boom te vinden

GrootsteNode.java

 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)); } } 

Uitgang:

Java-arraylist sorteren

 Largest element in the binary tree: 99 

Java-programma om het kleinste knooppunt in de binaire boom te vinden

Algoritme

1. Definieer de knooppuntklasse die drie attributen heeft, namelijk: data, links en rechts. Hier vertegenwoordigt links het linkerkind van het knooppunt en vertegenwoordigt rechts het rechterkind van het knooppunt.
2. Wanneer een knooppunt wordt gemaakt, worden gegevens doorgegeven aan het gegevensattribuut van het knooppunt en worden zowel links als rechts op nul ingesteld.
3. Definieer een andere klasse die een attribuutwortel heeft.
   Wortelvertegenwoordigen het hoofdknooppunt van de boom en initialiseren deze op nul.

kleinsteElement()zal het kleinste knooppunt in de binaire boom ontdekken:
1. Er wordt gecontroleerd of wortel is nul , wat betekent dat de boom leeg is.
2. Als de boom niet leeg is, definieer dan een variabele min die de gegevens van de temperatuur opslaat.
3. Ontdek het minimale knooppunt in de linker subboom door kleinsteElement() recursief aan te roepen. Sla die waarde op in leftMin. Vergelijk de waarde van min met leftMin en sla het minimum van twee op tot min.
4. Ontdek het minimale knooppunt in de rechter subboom door kleinsteElement() recursief aan te roepen. Sla die waarde op in rightMin. Vergelijk de waarde van min met rightMin en sla het maximum van twee op tot min.
5. Uiteindelijk zal min het kleinste knooppunt in de binaire boom bevatten.

KleinsteNode.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)); } } 

Uitgang:

 Smallest element in the binary tree: 1 

Java-programma om de maximale breedte van een binaire boom te vinden

Algoritme

1. Definieer de knooppuntklasse die drie attributen heeft, namelijk: gegevens links en rechts. Hier vertegenwoordigt links het linkerkind van het knooppunt en vertegenwoordigt rechts het rechterkind van het knooppunt.
2. Wanneer een knooppunt wordt gemaakt, worden gegevens doorgegeven aan het gegevensattribuut van het knooppunt en worden zowel links als rechts op nul ingesteld.
3. Definieer een andere klasse die een attribuutwortel heeft.
   Wortelvertegenwoordigt het hoofdknooppunt van de boom en initialiseert deze op nul.

1. Variabele maxWidth slaat het maximale aantal knooppunten op dat op elk niveau aanwezig is.
2. De wachtrij wordt gebruikt om de binaire boom op niveau te doorlopen.
3. Het controleert of de root nul is, wat betekent dat de boom leeg is.
4. Als dit niet het geval is, voegt u het hoofdknooppunt toe aan de wachtrij. Variabele knooppuntenInLevel houdt het aantal knooppunten in elk niveau bij.
5. Als knooppuntenInLevel > 0, verwijdert u het knooppunt vooraan in de wachtrij en voegt u het linker- en rechterkind toe aan de wachtrij. Voor de eerste iteratie wordt knooppunt 1 verwijderd en worden de onderliggende knooppunten 2 en 3 aan de wachtrij toegevoegd. In de tweede iteratie wordt knooppunt 2 verwijderd, worden de kinderen 4 en 5 aan de wachtrij toegevoegd, enzovoort.
6. MaxWidth slaat max(maxWidth, knooppuntenInLevel) op. Dus op elk gegeven moment vertegenwoordigt dit het maximale aantal knooppunten.
7. Dit gaat door totdat alle niveaus van de boom zijn doorlopen.

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()); } } 

Uitgang:

 Maximum width of the binary tree: 4