TechCodeview

Binarno drevo je drevesna nelinearna podatkovna struktura, ki se večinoma uporablja za razvrščanje in iskanje, ker hrani podatke v hierarhični obliki. V tem razdelku se bomo naučili implementacija binarne drevesne podatkovne strukture v Javi . Ponuja tudi kratek opis podatkovne strukture binarnega drevesa.

Binarno drevo

Drevo, v katerem ima vsako vozlišče (starš) največ dva podrejena vozlišča (levo in desno), imenujemo binarno drevo. Najvišje vozlišče se imenuje korensko vozlišče. V binarnem drevesu vozlišče vsebuje podatke in kazalec (naslov) levega in desnega podrejenega vozlišča.

The višina binarnega drevesa je število robov med korenino drevesa in njen najbolj oddaljen (najgloblji) list. Če je drevo prazno , višina je 0 . Višina vozlišča je označena z h .

Višina zgornjega binarnega drevesa je 2.

Število listov in vozlišč lahko izračunamo z naslednjo formulo.

• Največje število listnih vozlišč je binarno drevo: 2^h
• Največje število vozlišč je binarno drevo: 2^h+1-1

Kjer je h višina binarnega drevesa.

kaj je svn checkout

Primer binarnega drevesa

Vrste binarnega drevesa

V strukturi podatkov obstajajo naslednje vrste binarnega drevesa:

1. Polno/strogo binarno drevo
2. Popolno binarno drevo
3. Popolno binarno drevo
4. Binarno drevo ravnovesja
5. Ukoreninjeno binarno drevo
6. Degenerirano/patološko binarno drevo
7. Razširjeno binarno drevo
8. Poševno binarno drevo
   1. Levo poševno binarno drevo
   2. Desno poševno binarno drevo
9. Navojno binarno drevo
   1. Binarno drevo z eno nitjo
   2. Dvonitno binarno drevo

Implementacija binarnega drevesa v Javi

Obstaja veliko načinov za implementacijo binarnega drevesa. V tem razdelku bomo implementirali binarno drevo z uporabo podatkovne strukture LinkedList. Skupaj z njim bomo implementirali tudi naloge prečkanja, iskanje vozlišča in vstavljanje vozlišča v binarno drevo.

Implementacija binarnega drevesa z uporabo LinkedList

Algoritem

Definirajte razred Node, ki vsebuje tri atribute, in sicer: podatke levo in desno. Tu levo predstavlja levega podrejenega vozlišča, desno pa desnega podrejenega vozlišča.

• Ko je vozlišče ustvarjeno, bodo podatki prešli v podatkovni atribut vozlišča, levo in desno pa bosta nastavljeni na nič.
• Definirajte drug razred, ki ima koren atributa.
• Root predstavlja korensko vozlišče drevesa in ga inicializira na nič.

vstavi()bo v drevo dodal novo vozlišče:
• Preveri, ali je koren nič, kar pomeni, da je drevo prazno. Novo vozlišče bo dodalo kot korensko.
• V nasprotnem primeru bo dodal root v čakalno vrsto.
• Spremenljivka vozlišče predstavlja trenutno vozlišče.
• Najprej preveri, ali ima vozlišče levega in desnega otroka. Če da, bo obe vozlišči dodal v čakalno vrsto.
• Če levi podrejeni element ni prisoten, bo dodal novo vozlišče kot levi podrejeni element.
• Če je levo prisotno, bo dodalo novo vozlišče kot desnega podrejenega.
po vrstnem redu()bo vozlišča drevesa prikazal po vrstnem redu.
• Prečka celotno drevo in nato natisne levi otrok, ki mu sledi koren, nato pa desni otrok.

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

Izhod:

 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 

Operacije binarnega drevesa

V binarnem drevesu je mogoče izvesti naslednje operacije:

• Vstavljanje
• Izbris
• Iskanje
• Prehod

Program Java za vstavljanje vozlišča v binarno drevo

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

Izhod:

 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 

Program Java za brisanje vozlišča v Javi

Algoritem

1. Začnite pri korenu in poiščite najgloblje in skrajno desno vozlišče v binarnem drevesu in vozlišče, ki ga želimo izbrisati.
2. Zamenjajte podatke najglobljega skrajno desnega vozlišča z vozliščem, ki ga želite izbrisati.
3. Nato izbrišite najgloblje skrajno desno vozlišče.

Razmislite o naslednji sliki.

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

Izhod:

java metode

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

Program Java za iskanje vozlišča v binarnem drevesu

Algoritem

• Definirajte razred Node, ki ima tri atribute, in sicer: podatke levo in desno. Tu levo predstavlja levega podrejenega vozlišča, desno pa desnega podrejenega vozlišča.
• Ko je vozlišče ustvarjeno, bodo podatki prešli v podatkovni atribut vozlišča, levo in desno pa bosta nastavljeni na nič.
• Definirajte drug razred, ki ima dva atributa root in flag.
  1. Koren predstavlja korensko vozlišče drevesa in ga inicializira na nič.
  2. Zastavica bo uporabljena za preverjanje, ali je dano vozlišče prisotno v drevesu ali ne. Sprva bo nastavljen na false.

searchNode()bo poiskal določeno vozlišče v binarnem drevesu:
• Preveri, ali je koren nič, kar pomeni, da je drevo prazno.
• Če drevo ni prazno, bo primerjalo začasne podatke z vrednostjo. Če sta enaka, bo zastavico nastavil na true in vrnil.
• Prečkajte levo poddrevo z rekurzivnim klicem searchNode() in preverite, ali je vrednost prisotna v levem poddrevu.
• Prečkajte desno poddrevo tako, da rekurzivno pokličete searchNode() in preverite, ali je vrednost prisotna v desnem poddrevu.

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

Izhod:

 Element is present in the binary tree. 

Prehod binarnega drevesa

Opomba: Razen zgornjih treh prehodov obstaja še en vrstni red prehodov, ki se imenuje prehod meje.

Program Java za prehod po vrstnem redu, prednaročilu in po naročilu

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

Izhod:

 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 

Poleg zgornjih operacij lahko izvajamo tudi operacije, kot so veliko vozlišče, najmanjše vozlišče in vsota vseh vozlišč.

Program Java za iskanje največjega vozlišča v binarnem drevesu

Največje vozlišče.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)); } } 

Izhod:

 Largest element in the binary tree: 99 

Program Java za iskanje najmanjšega vozlišča v binarnem drevesu

Algoritem

1. Definirajte razred Node, ki ima tri atribute, in sicer: podatke, levo in desno. Tu levo predstavlja levega podrejenega vozlišča, desno pa desnega podrejenega vozlišča.
2. Ko je vozlišče ustvarjeno, bodo podatki prešli v podatkovni atribut vozlišča, levo in desno pa bosta nastavljeni na nič.
3. Definirajte drug razred, ki ima koren atributa.
   Rootpredstavljajo korensko vozlišče drevesa in ga inicializirajo na nič.

najmanjšiElement()bo našel najmanjše vozlišče v binarnem drevesu:
1. Preverja, ali koren je nič , kar pomeni, da je drevo prazno.
2. Če drevo ni prazno, definirajte spremenljivko min, ki bo shranila začasne podatke.
3. Poiščite minimalno vozlišče v levem poddrevesu tako, da rekurzivno pokličete smallestElement(). To vrednost shranite v levo Min. Primerjajte vrednost min z leftMin in shranite najmanj dve do min.
4. Poiščite najmanjše vozlišče v desnem poddrevesu tako, da rekurzivno pokličete smallestElement(). To vrednost shranite v desno Min. Primerjajte vrednost min z desno Min in shranite največ dve do min.
5. Na koncu bo min vseboval najmanjše vozlišče v binarnem drevesu.

Najmanjše vozlišče.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)); } } 

Izhod:

 Smallest element in the binary tree: 1 

Program Java za iskanje največje širine binarnega drevesa

Algoritem

1. Definirajte razred Node, ki ima tri atribute, in sicer: podatke levo in desno. Tu levo predstavlja levega podrejenega vozlišča, desno pa desnega podrejenega vozlišča.
2. Ko je vozlišče ustvarjeno, bodo podatki prešli v podatkovni atribut vozlišča, levo in desno pa bosta nastavljeni na nič.
3. Definirajte drug razred, ki ima koren atributa.
   Rootpredstavlja korensko vozlišče drevesa in ga inicializira na nič.

1. Spremenljivka maxWidth bo shranila največje število vozlišč, prisotnih na kateri koli ravni.
2. Čakalna vrsta se uporablja za prečkanje binarnega drevesa po nivojih.
3. Preveri, ali je koren nič, kar pomeni, da je drevo prazno.
4. Če ni, dodajte korensko vozlišče v čakalno vrsto. Spremenljivka nodesInLevel spremlja število vozlišč na vsaki ravni.
5. Če je nodesInLevel > 0, odstranite vozlišče s sprednje strani čakalne vrste in dodajte njegov levi in ​​desni podrejeni element v čakalno vrsto. Pri prvi ponovitvi bo vozlišče 1 odstranjeno, njegovi podrejeni vozlišči 2 in 3 pa bosta dodani v čakalno vrsto. V drugi ponovitvi bo vozlišče 2 odstranjeno, njegova otroka 4 in 5 bosta dodana v čakalno vrsto in tako naprej.
6. MaxWidth bo shranil max(maxWidth, nodesInLevel). Torej bo v danem trenutku predstavljal največje število vozlišč.
7. To se bo nadaljevalo, dokler ne prečkate vseh ravni drevesa.

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

Izhod:

 Maximum width of the binary tree: 4