TechCodeview

Arbore binar este o structură de date neliniară de tip arborescent care sunt utilizate în principal pentru sortare și căutare, deoarece stochează date în formă ierarhică. În această secțiune, vom învăța implementarea structurii de date arbore binar în Java . De asemenea, oferă o scurtă descriere a structurii de date a arborelui binar.

Arborele binar

Un arbore în care fiecare nod (părinte) are cel mult două noduri copii (stânga și dreapta) se numește arbore binar. Nodul cel mai de sus se numește nodul rădăcină. Într-un arbore binar, un nod conține datele și indicatorul (adresa) nodului copil stâng și drept.

The înălţime a unui arbore binar este numărul de margini dintre rădăcina copacului și frunza sa cea mai îndepărtată (cea mai adâncă). Dacă copacul este gol , înălțimea este 0 . Înălțimea nodului este notă cu h .

comparare șiruri în java

Înălțimea arborelui binar de mai sus este de 2.

Putem calcula numărul de frunze și nod folosind următoarea formulă.

• Numărul maxim de noduri frunze este un arbore binar: 2^h
• Numărul maxim de noduri este un arbore binar: 2^h+1-1

Unde, h este înălțimea arborelui binar.

Exemplu de arbore binar

Tipuri de arbore binar

Există următoarele tipuri de arbore binar în structura datelor:

1. Arbore complet/ strict binar
2. Arborele binar complet
3. Arborele binar perfect
4. Arborele binar de echilibru
5. Arborele binar înrădăcinat
6. Arborele binar degenerat/patologic
7. Arbore binar extins
8. Arborele binar înclinat
   1. Arborele binar înclinat la stânga
   2. Arborele binar înclinat la dreapta
9. Arborele binar cu filet
   1. Arbore binar cu un singur fir
   2. Arbore binar cu filet dublu

Implementarea arborelui binar în Java

Există multe modalități de implementare a arborelui binar. În această secțiune, vom implementa arborele binar folosind structura de date LinkedList. Odată cu acesta, vom implementa și ordinele de traversare, căutând un nod și inserând un nod într-un arbore binar.

Implementarea arborelui binar folosind LinkedList

Algoritm

Definiți clasa Node care conține trei atribute și anume: date stânga și dreapta. Aici, stânga reprezintă copilul din stânga al nodului și dreapta reprezintă copilul din dreapta al nodului.

• Când este creat un nod, datele vor trece la atributul de date al nodului și atât stânga cât și dreapta vor fi setate la nul.
• Definiți o altă clasă care are o rădăcină de atribut.
• Root reprezintă nodul rădăcină al arborelui și inițializează-l la null.

introduce()va adăuga un nou nod în arbore:
• Verifică dacă rădăcina este nulă, ceea ce înseamnă că arborele este gol. Acesta va adăuga noul nod ca rădăcină.
• În caz contrar, va adăuga rădăcină la coadă.
• Nodul variabil reprezintă nodul curent.
• În primul rând, verifică dacă un nod are un copil stâng și drept. Dacă da, va adăuga ambele noduri la coadă.
• Dacă copilul din stânga nu este prezent, acesta va adăuga noul nod ca copil din stânga.
• Dacă stânga este prezentă, atunci va adăuga noul nod ca copil drept.
în ordine()va afișa nodurile arborelui în ordine.
• Traversează întregul copac, apoi imprimă copilul stâng urmat de rădăcină, apoi urmat de copilul drept.

BinarySearchTree.java

1 milion în cifre

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

Ieșire:

 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 

Operații în arbore binar

Următoarele operații pot fi efectuate pe un arbore binar:

• Inserare
• Ștergere
• Căutare
• Traversare

Program Java pentru inserarea unui nod în arbore binar

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

Ieșire:

 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 pentru a șterge un nod în Java

Algoritm

1. Începând de la rădăcină, găsiți cel mai adânc și cel mai din dreapta nod din arborele binar și nodul pe care vrem să-l ștergem.
2. Înlocuiți datele nodului cel mai adânc din dreapta cu nodul care trebuie șters.
3. Apoi ștergeți nodul cel mai adânc din dreapta.

Luați în considerare următoarea figură.

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

Ieșire:

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

Program Java pentru a căuta un nod în arbore binar

Algoritm

• Definiți clasa Node care are trei atribute și anume: date stânga și dreapta. Aici, stânga reprezintă copilul din stânga al nodului și dreapta reprezintă copilul din dreapta al nodului.
• Când este creat un nod, datele vor trece la atributul de date al nodului și atât stânga cât și dreapta vor fi setate la nul.
• Definiți o altă clasă care are două atribute root și flag.
  1. Root reprezintă nodul rădăcină al arborelui și îl inițializează la null.
  2. Flag va fi folosit pentru a verifica dacă nodul dat este prezent sau nu în arbore. Inițial, va fi setat la fals.

searchNode()va căuta un anumit nod în arborele binar:
• Verifică dacă rădăcina este nulă, ceea ce înseamnă că arborele este gol.
• Dacă arborele nu este gol, va compara datele temp cu valoarea. Dacă sunt egale, va seta steag-ul la adevărat și va reveni.
• Traversați subarborele din stânga apelând recursiv searchNode() și verificați dacă valoarea este prezentă în subarborele din stânga.
• Traversați subarborele din dreapta apelând recursiv searchNode() și verificați dacă valoarea este prezentă în subarborele din dreapta.

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

Ieșire:

care a inventat școala

 Element is present in the binary tree. 

Traversarea arborelui binar

Notă: Cu excepția celor trei traversări de mai sus, există o altă ordine de traversare numită traversare a graniței.

Program Java pentru traversarea în ordine, precomandă și postcomandă

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

Ieșire:

 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 

Pe lângă operațiile de mai sus, putem efectua și operațiuni precum nodul mare, cel mai mic nod și suma tuturor nodurilor.

Program Java pentru a găsi cel mai mare nod din arborele binar

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

Ieșire:

 Largest element in the binary tree: 99 

Program Java pentru a găsi cel mai mic nod din arborele binar

Algoritm

1. Definiți clasa Node care are trei atribute și anume: date, stânga și dreapta. Aici, stânga reprezintă copilul din stânga al nodului și dreapta reprezintă copilul din dreapta al nodului.
2. Când este creat un nod, datele vor trece la atributul de date al nodului și atât stânga cât și dreapta vor fi setate la nul.
3. Definiți o altă clasă care are o rădăcină de atribut.
   Rădăcinăreprezintă nodul rădăcină al arborelui și inițializați-l la null.

cel mai micElement()va afla cel mai mic nod din arborele binar:
1. Se verifică dacă rădăcina este nulă , ceea ce înseamnă că arborele este gol.
2. Dacă arborele nu este gol, definiți o variabilă min care va stoca datele temp.
3. Aflați nodul minim din subarborele din stânga apelând recursiv smallestElement(). Stocați acea valoare în leftMin. Comparați valoarea lui min cu leftMin și stocați minimum doi la min.
4. Aflați nodul minim din subarborele din dreapta apelând recursiv smallestElement(). Stocați acea valoare în rightMin. Comparați valoarea min cu rightMin și stocați maximul de două la min.
5. La sfârșit, min va deține cel mai mic nod din arborele binar.

SmallestNode.java

șir împărțit c++

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

Ieșire:

 Smallest element in the binary tree: 1 

Program Java pentru a găsi lățimea maximă a unui arbore binar

Algoritm

1. Definiți clasa Node care are trei atribute și anume: date stânga și dreapta. Aici, stânga reprezintă copilul din stânga al nodului și dreapta reprezintă copilul din dreapta al nodului.
2. Când este creat un nod, datele vor trece la atributul de date al nodului și atât stânga cât și dreapta vor fi setate la nul.
3. Definiți o altă clasă care are o rădăcină de atribut.
   Rădăcinăreprezintă nodul rădăcină al arborelui și îl inițializează la null.

1. Variabila maxWidth va stoca numărul maxim de noduri prezente la orice nivel.
2. Coada este folosită pentru parcurgerea la nivel de arbore binar.
3. Verifică dacă rădăcina este nulă, ceea ce înseamnă că arborele este gol.
4. Dacă nu, adăugați nodul rădăcină la coadă. Variabila nodesInLevel ține evidența numărului de noduri din fiecare nivel.
5. Dacă nodesInLevel > 0, eliminați nodul din partea din față a cozii și adăugați copilul din stânga și din dreapta în coadă. Pentru prima iterație, nodul 1 va fi eliminat, iar nodurile sale secundare 2 și 3 vor fi adăugate la coadă. În a doua iterație, nodul 2 va fi eliminat, copiii 4 și 5 vor fi adăugați la coadă și așa mai departe.
6. MaxWidth va stoca max(maxWidth, nodesInLevel). Deci, în orice moment dat, va reprezenta numărul maxim de noduri.
7. Acest lucru va continua până când toate nivelurile arborelui vor fi traversate.

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

Ieșire:

 Maximum width of the binary tree: 4