TechCodeview

Бинарно дрво је нелинеарна структура података типа стабла која се углавном користи за сортирање и претраживање јер чува податке у хијерархијском облику. У овом одељку ћемо научити имплементација структуре података бинарног стабла у Јави . Такође, пружа кратак опис структуре података бинарног стабла.

Бинарно дрво

Стабло у коме сваки чвор (родитељ) има највише два подређена чвора (леви и десни) назива се бинарно стабло. Највиши чвор се назива коренски чвор. У бинарном стаблу чвор садржи податке и показивач (адресу) левог и десног подређеног чвора.

Тхе висина бинарног дрвета је број ивица између корена дрвета и њен најдаљи (најдубљи) лист. Ако је дрво празан , висина је 0 . Висина чвора се означава са х .

Висина горњег бинарног стабла је 2.

Можемо израчунати број листова и чворова користећи следећу формулу.

• Максималан број чворова листа је бинарно дрво: 2^х
• Максималан број чворова је бинарно стабло: 2^х+1-1

Где је х висина бинарног стабла.

Пример бинарног стабла

Врсте бинарног стабла

У структури података постоје следећи типови бинарног стабла:

1. Пуно/строго бинарно стабло
2. Комплетно бинарно стабло
3. Савршено бинарно дрво
4. Бинарно стабло равнотеже
5. Укорењено бинарно стабло
6. Дегенерисано/патолошко бинарно стабло
7. Проширено бинарно стабло
8. Искривљено бинарно дрво
   1. Бинарно стабло закривљено улево
   2. Десно искошено бинарно стабло
9. Бинарно дрво са навојем
   1. Бинарно стабло са једним навојем
   2. Двоструко бинарно стабло

Имплементација бинарног стабла у Јави

Постоји много начина за имплементацију бинарног стабла. У овом одељку ћемо имплементирати бинарно стабло користећи структуру података ЛинкедЛист. Заједно са њим, имплементираћемо и налоге преласка, тражење чвора и уметање чвора у бинарно стабло.

Имплементација бинарног стабла користећи ЛинкедЛист

Алгоритам

Дефинишите класу чвора која садржи три атрибута и то: податке лево и десно. Овде лево представља лево дете чвора, а десно десно дете чвора.

• Када се креира чвор, подаци ће проћи у атрибут података чвора и лево и десно ће бити подешене на нулл.
• Дефинишите другу класу која има корен атрибута.
• Корен представља коренски чвор стабла и иницијализује га на нулл.

инсерт()ће додати нови чвор стаблу:
• Проверава да ли је корен нула, што значи да је дрво празно. Додат ће нови чвор као роот.
• У супротном, то ће додати роот у ред.
• Променљиви чвор представља тренутни чвор.
• Прво, проверава да ли чвор има лево и десно дете. Ако јесте, додаће оба чвора у ред чекања.
• Ако лево дете није присутно, оно ће додати нови чвор као лево дете.
• Ако је леви присутан, онда ће додати нови чвор као десно дете.
у реду()ће приказати чворове стабла у редоследу.
• Прелази преко целог стабла, а затим штампа лево дете, праћено кореном, а затим десно дете.

БинариСеарцхТрее.јава

арп-а команда

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

Излаз:

 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 

Операције бинарног дрвета

На бинарном стаблу се могу извршити следеће операције:

• Инсертион
• Брисање
• Претрага
• Траверсал

Јава програм за уметање чвора у бинарно стабло

БинариТрееИнсерт.јава

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

Излаз:

 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 

Јава програм за брисање чвора у Јави

Алгоритам

1. Почевши од корена, пронађите најдубљи и крајњи десни чвор у бинарном стаблу и чвор који желимо да избришемо.
2. Замените податке најдубљег десног чвора са чвором који желите да избришете.
3. Затим избришите најдубљи крајњи десни чвор.

Размотрите следећу слику.

ДелетеНоде.јава

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

Излаз:

тцп и ип модел

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

Јава програм за претрагу чвора у бинарном стаблу

Алгоритам

• Дефинишите класу чвора која има три атрибута и то: подаци лево и десно. Овде лево представља лево дете чвора, а десно десно дете чвора.
• Када се креира чвор, подаци ће проћи у атрибут података чвора и лево и десно ће бити подешене на нулл.
• Дефинишите другу класу која има два атрибута роот и флаг.
  1. Корен представља коренски чвор стабла и иницијализује га на нулл.
  2. Застава ће се користити за проверу да ли је дати чвор присутан у стаблу или не. У почетку ће бити постављено на нетачно.

сеарцхНоде()ће тражити одређени чвор у бинарном стаблу:
• Проверава да ли је корен нула, што значи да је дрво празно.
• Ако дрво није празно, упоредиће податке о темп са вредношћу. Ако су једнаки, поставиће заставицу на труе и вратити.
• Пређите лево подстабло позивањем сеарцхНоде() рекурзивно и проверите да ли је вредност присутна у левом подстаблу.
• Пређите преко десног подстабла позивањем сеарцхНоде() рекурзивно и проверите да ли је вредност присутна у десном подстаблу.

СеарцхБинариТрее.јава

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

Излаз:

 Element is present in the binary tree. 

Прелазак бинарног стабла

Напомена: Осим горња три преласка, постоји још један редослед преласка који се зове прелазак границе.

Јава програм за прелазак по инордеру, препоруку и прелазак постордера

БинариТрее.јава

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

Излаз:

 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 

Поред горе наведених операција, можемо изводити и операције као што су велики чвор, најмањи чвор и збир свих чворова.

Јава програм за проналажење највећег чвора у бинарном стаблу

ЛаргестНоде.јава

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

Излаз:

 Largest element in the binary tree: 99 

Јава програм за проналажење најмањег чвора у бинарном стаблу

Алгоритам

1. Дефинишите класу чвора која има три атрибута и то: подаци, лево и десно. Овде лево представља лево дете чвора, а десно десно дете чвора.
2. Када се креира чвор, подаци ће проћи у атрибут података чвора и лево и десно ће бити подешене на нулл.
3. Дефинишите другу класу која има корен атрибута.
   Коренпредстављају коријенски чвор стабла и иницијализирају га на нулл.

најмањи елемент()ће сазнати најмањи чвор у бинарном стаблу:
1. Проверава да ли корен је нула , што значи да је дрво празно.
2. Ако дрво није празно, дефинишите променљиву мин која ће чувати податке о температури.
3. Пронађите минимални чвор у левом подстаблу рекурзивним позивом смаллестЕлемент(). Сачувајте ту вредност у левоМин. Упоредите вредност мин са левим Мин и сачувајте минимум од два до мин.
4. Пронађите минимални чвор у десном подстаблу рекурзивним позивом смаллестЕлемент(). Сачувајте ту вредност у ригхтМин. Упоредите вредност мин са ригхтМин и сачувајте максимум од два до мин.
5. На крају, мин ће држати најмањи чвор у бинарном стаблу.

СмаллестНоде.јава

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

Излаз:

 Smallest element in the binary tree: 1 

Јава програм за проналажење максималне ширине бинарног стабла

Алгоритам

1. Дефинишите класу чвора која има три атрибута и то: подаци лево и десно. Овде лево представља лево дете чвора, а десно десно дете чвора.
2. Када се креира чвор, подаци ће проћи у атрибут података чвора и лево и десно ће бити подешене на нулл.
3. Дефинишите другу класу која има корен атрибута.
   Коренпредставља коренски чвор стабла и иницијализује га на нулл.

1. Променљива макВидтх ће ускладиштити максималан број чворова присутних на било ком нивоу.
2. Ред се користи за прелазак бинарног стабла по нивоу.
3. Проверава да ли је корен нула, што значи да је дрво празно.
4. Ако није, додајте основни чвор у ред чекања. Променљива нодесИнЛевел прати број чворова на сваком нивоу.
5. Ако је нодесИнЛевел > 0, уклоните чвор са предње стране реда и додајте његово лево и десно дете у ред. За прву итерацију, чвор 1 ће бити уклоњен, а његови потомци чворови 2 и 3 ће бити додати у ред. У другој итерацији, чвор 2 ће бити уклоњен, његови потомци 4 и 5 ће бити додати у ред и тако даље.
6. МакВидтх ће сачувати мак(макВидтх, нодесИнЛевел). Дакле, у било ком тренутку ће представљати максималан број чворова.
7. Ово ће се наставити све док се не пређу сви нивои стабла.

БинариТрее.јава

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

Излаз:

 Maximum width of the binary tree: 4