TechCodeview

Binarno stablo je nelinearna podatkovna struktura tipa stabla koja se uglavnom koristi za sortiranje i pretraživanje jer pohranjuje podatke u hijerarhijskom obliku. U ovom odjeljku ćemo naučiti implementacija strukture podataka binarnog stabla u Javi . Također, daje kratak opis strukture podataka binarnog stabla.

Binarno stablo

Stablo u kojem svaki čvor (roditelj) ima najviše dva čvora djeteta (lijevo i desno) naziva se binarnim stablom. Najviši čvor naziva se korijenski čvor. U binarnom stablu čvor sadrži podatke i pokazivač (adresu) lijevog i desnog podređenog čvora.

The visina binarnog stabla je broj bridova između korijena stabla i njegov najdalji (najdublji) list. Ako je drvo prazan , visina je 0 . Visina čvora je označena sa h .

Visina gornjeg binarnog stabla je 2.

Broj listova i čvorova možemo izračunati pomoću sljedeće formule.

• Maksimalan broj lisnih čvorova je binarno stablo: 2^h
• Maksimalan broj čvorova je binarno stablo: 2^h+1-1

Gdje je h visina binarnog stabla.

Primjer binarnog stabla

Vrste binarnog stabla

Postoje sljedeće vrste binarnog stabla u strukturi podataka:

1. Potpuno/striktno binarno stablo
2. Kompletno binarno stablo
3. Savršeno binarno stablo
4. Binarno stablo ravnoteže
5. Ukorijenjeno binarno stablo
6. Degenerirano/ patološko binarno stablo
7. Prošireno binarno stablo
8. Iskrivljeno binarno stablo
   1. Lijevo zakrivljeno binarno stablo
   2. Desno zakrivljeno binarno stablo
9. Nitno binarno stablo
   1. Jednonitno binarno stablo
   2. Dvostruko navojno binarno stablo

Implementacija binarnog stabla u Javi

Postoji mnogo načina implementacije binarnog stabla. U ovom ćemo odjeljku implementirati binarno stablo pomoću strukture podataka LinkedList. Uz to, također ćemo implementirati naloge obilaska, pretraživanje čvora i umetanje čvora u binarno stablo.

Implementacija binarnog stabla koristeći LinkedList

Algoritam

Definirajte klasu čvora koja sadrži tri atributa, naime: podatke lijevo i desno. Ovdje lijevo predstavlja lijevo dijete čvora, a desno predstavlja desno dijete čvora.

• Kada se stvori čvor, podaci će prijeći u podatkovni atribut čvora, a lijevo i desno bit će postavljeni na null.
• Definirajte drugu klasu koja ima korijen atributa.
• Root predstavlja korijenski čvor stabla i inicijalizira ga na nulu.

umetnuti()će dodati novi čvor stablu:
• Provjerava je li korijen null, što znači da je stablo prazno. Dodat će novi čvor kao root.
• Inače će dodati root u red čekanja.
• Varijabla čvor predstavlja trenutni čvor.
• Prvo se provjerava ima li čvor lijevog i desnog djeteta. Ako da, dodati će oba čvora u red čekanja.
• Ako lijevi podređeni čvor nije prisutan, dodat će novi čvor kao lijevi podređeni čvor.
• Ako je lijevi prisutan, tada će dodati novi čvor kao desno dijete.
u redu()prikazat će čvorove stabla redoslijedom.
• Prolazi kroz cijelo stablo, zatim ispisuje lijevi potomak nakon kojeg slijedi korijen i zatim desni potomak.

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

Izlaz:

 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 binarnog stabla

Na binarnom stablu mogu se izvesti sljedeće operacije:

kako izvršiti skriptu

• Umetanje
• Brisanje
• traži
• Traversal

Java program za umetanje čvora u binarno stablo

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

Izlaz:

 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 program za brisanje čvora u Javi

Algoritam

1. Počevši od korijena, pronađite najdublji i krajnji desni čvor u binarnom stablu i čvor koji želimo izbrisati.
2. Zamijenite podatke najdubljeg desnog čvora s čvorom koji želite izbrisati.
3. Zatim izbrišite najdublji krajnji desni čvor.

Razmotrite sljedeću sliku.

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

Izlaz:

uklanjanje zadnje predaje git

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

Java program za pretraživanje čvora u binarnom stablu

Algoritam

• Definirajte klasu čvora koja ima tri atributa: podatke lijevo i desno. Ovdje lijevo predstavlja lijevo dijete čvora, a desno predstavlja desno dijete čvora.
• Kada se stvori čvor, podaci će prijeći u podatkovni atribut čvora, a lijevo i desno bit će postavljeni na null.
• Definirajte drugu klasu koja ima dva atributa korijen i zastavu.
  1. Korijen predstavlja korijenski čvor stabla i inicijalizira ga na nulu.
  2. Zastavica će se koristiti za provjeru je li dani čvor prisutan u stablu ili ne. U početku će biti postavljeno na false.

searchNode()tražit će određeni čvor u binarnom stablu:
• Provjerava je li korijen null, što znači da je stablo prazno.
• Ako stablo nije prazno, usporedit će temp podatke s vrijednošću. Ako su jednaki, postavit će zastavu na true i vratiti se.
• Pređite lijevo podstablo rekurzivnim pozivom searchNode() i provjerite postoji li vrijednost u lijevom podstablu.
• Pređite desnim podstablom rekurzivnim pozivom searchNode() i provjerite postoji li vrijednost u desnom podstablu.

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

Izlaz:

 Element is present in the binary tree. 

Prolazak binarnog stabla

Napomena: Osim gornja tri obilaska, postoji još jedan redoslijed obilaženja koji se naziva granični obilazak.

Java program za obilazak po redoslijedu, prednarudžbi i postnarudžbi

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

Izlaz:

 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 

Osim gore navedenih operacija, također možemo izvoditi operacije kao što su veliki čvor, najmanji čvor i zbroj svih čvorova.

Java program za pronalaženje najvećeg čvora u binarnom stablu

NajvećiČvor.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)); } } 

Izlaz:

 Largest element in the binary tree: 99 

Java program za pronalaženje najmanjeg čvora u binarnom stablu

Algoritam

1. Definirajte klasu čvora koja ima tri atributa i to: podaci, lijevi i desni. Ovdje lijevo predstavlja lijevo dijete čvora, a desno predstavlja desno dijete čvora.
2. Kada se stvori čvor, podaci će prijeći u podatkovni atribut čvora, a i lijevo i desno bit će postavljeni na null.
3. Definirajte drugu klasu koja ima korijen atributa.
   Korijenpredstavljaju korijenski čvor stabla i inicijaliziraju ga na nulu.

najmanjiElement()pronaći će najmanji čvor u binarnom stablu:
1. Provjerava da li korijen je nula , što znači da je drvo prazno.
2. Ako stablo nije prazno, definirajte varijablu min koja će pohraniti temp podatke.
3. Pronađite minimalni čvor u lijevom podstablu rekurzivnim pozivanjem smallestElement(). Pohranite tu vrijednost u leftMin. Usporedite vrijednost min s leftMin i pohranite minimum od dva do min.
4. Pronađite minimalni čvor u desnom podstablu rekurzivnim pozivanjem smallestElement(). Pohranite tu vrijednost u rightMin. Usporedite vrijednost min s rightMin i pohranite najviše od dva do min.
5. Na kraju, min će držati najmanji čvor u binarnom stablu.

NajmanjiČvor.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)); } } 

Izlaz:

 Smallest element in the binary tree: 1 

Java program za pronalaženje maksimalne širine binarnog stabla

Algoritam

1. Definirajte klasu čvora koja ima tri atributa: podatke lijevo i desno. Ovdje lijevo predstavlja lijevo dijete čvora, a desno predstavlja desno dijete čvora.
2. Kada se stvori čvor, podaci će prijeći u podatkovni atribut čvora, a lijevo i desno bit će postavljeni na null.
3. Definirajte drugu klasu koja ima korijen atributa.
   Korijenpredstavlja korijenski čvor stabla i inicijalizira ga na nulu.

1. Varijabla maxWidth će pohraniti najveći broj čvorova prisutnih na bilo kojoj razini.
2. Red se koristi za obilazak binarnog stabla na razini.
3. Provjerava je li korijen null, što znači da je stablo prazno.
4. Ako nije, dodajte korijenski čvor u red čekanja. Varijabla nodesInLevel prati broj čvorova na svakoj razini.
5. Ako je nodesInLevel > 0, uklonite čvor s početka reda i dodajte njegov lijevi i desni potomak u red. Za prvu iteraciju, čvor 1 bit će uklonjen, a njegovi podređeni čvorovi 2 i 3 bit će dodani u red čekanja. U drugoj iteraciji, čvor 2 će biti uklonjen, njegova djeca 4 i 5 će biti dodana u red i tako dalje.
6. MaxWidth će pohraniti max(maxWidth, nodesInLevel). Dakle, u bilo kojem vremenskom trenutku predstavljat će maksimalan broj čvorova.
7. To će se nastaviti dok se ne prijeđu sve razine stabla.

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

Izlaz:

 Maximum width of the binary tree: 4