Binært tre er en tretype ikke-lineær datastruktur som hovedsakelig brukes til sortering og søk fordi de lagrer data i hierarkisk form. I denne delen vil vi lære implementering av binær tredatastruktur i Java . Gir også en kort beskrivelse av binær tredatastruktur.

Binært tre

Et tre der hver node (foreldre) har maksimalt to-barnsnoder (venstre og høyre) kalles binært tre. Den øverste noden kalles rotnoden. I et binært tre inneholder en node dataene og pekeren (adressen) til venstre og høyre barnenode.

De høyde av et binært tre er antall kanter mellom treets rot og dets lengste (dypeste) blad. Hvis treet er tømme , høyden er 0 . Høyden på noden er angitt med h .

Høyden på det binære treet ovenfor er 2.

Vi kan beregne antall blader og node ved å bruke følgende formel.

• Maksimalt antall bladnoder er et binært tre: 2^h
• Maksimalt antall noder er et binært tre: 2^h+1-1

Hvor h er høyden på binært tre.

Eksempel på binært tre

Typer av binære tre

Det er følgende typer binære tre i datastruktur:

1. Fullt / strengt binært tre
2. Komplett binært tre
3. Perfekt binært tre
4. Balanse binært tre
5. Rotfestet binært tre
6. Degenerert/ patologisk binært tre
7. Utvidet binært tre
8. Skeivt binært tre
   1. Venstreskjevt binært tre
   2. Høyreskjevt binært tre
9. Gjenget binært tre
   1. Enkeltgjenget binært tre
   2. Dobbelttrådet binært tre

Binær treimplementering i Java

Det er mange måter å implementere binært tre på. I denne delen vil vi implementere binært tre ved å bruke LinkedList-datastruktur. Sammen med det vil vi også implementere traverseringsordrene, søke i en node og sette inn en node i et binært tre.

Implementering av binært tre ved hjelp av LinkedList

Algoritme

Definer nodeklasse som inneholder tre attributter nemlig: data venstre og høyre. Her representerer venstre det venstre barnet til noden og høyre representerer det høyre barnet til noden.

• Når en node er opprettet, vil data overføres til dataattributtet til noden, og både venstre og høyre vil bli satt til null.
• Definer en annen klasse som har en attributtrot.
• Root representerer rotnoden til treet og initialiser den til null.

sett inn()vil legge til en ny node i treet:
• Den sjekker om roten er null, noe som betyr at treet er tomt. Det vil legge til den nye noden som root.
• Ellers vil det legge rot til køen.
• Variabelnoden representerer gjeldende node.
• Først sjekker den om en node har et venstre og høyre barn. Hvis ja, vil den legge til begge nodene i køen.
• Hvis det venstre barnet ikke er til stede, vil det legge til den nye noden som det venstre barnet.
• Hvis venstre er til stede, vil den legge til den nye noden som høyre barn.
i rekkefølge()vil vise nodene til treet på uordentlig måte.
• Den krysser hele treet og skriver deretter ut venstre barn etterfulgt av rot og deretter etterfulgt av høyre barn.

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

Produksjon:

 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 

Binære treoperasjoner

Følgende operasjoner kan utføres på et binært tre:

• Innsetting
• Sletting
• Søk
• Traversering

Java-program for å sette inn en node i binært tre

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

Produksjon:

 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 for å slette en node i Java

Algoritme

1. Start ved roten og finn den dypeste og lengst høyre noden i binærtreet og noden som vi ønsker å slette.
2. Erstatt dataene til noden lengst til høyre med noden som skal slettes.
3. Slett så den dypeste noden lengst til høyre.

Tenk på følgende figur.

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

Produksjon:

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

Java-program for å søke etter en node i binært tre

Algoritme

• Definer nodeklasse som har tre attributter nemlig: data venstre og høyre. Her representerer venstre det venstre barnet til noden og høyre representerer det høyre barnet til noden.
• Når en node er opprettet, vil data overføres til dataattributtet til noden, og både venstre og høyre vil bli satt til null.
• Definer en annen klasse som har to attributter rot og flagg.
  1. Root representerer rotnoden til treet og initialiserer den til null.
  2. Flagget vil bli brukt til å sjekke om den gitte noden er tilstede i treet eller ikke. I utgangspunktet vil den bli satt til falsk.

searchNode()vil søke etter en bestemt node i det binære treet:
• Den sjekker om roten er null, noe som betyr at treet er tomt.
• Hvis treet ikke er tomt, vil det sammenligne temps data med verdi. Hvis de er like, vil det sette flagget til sant og returnere.
• Gå gjennom venstre undertre ved å kalle searchNode() rekursivt og sjekk om verdien er tilstede i venstre undertre.
• Gå gjennom høyre undertre ved å kalle searchNode() rekursivt og sjekk om verdien er tilstede i høyre undertre.

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

Produksjon:

 Element is present in the binary tree. 

Binær tregjennomgang

Merk: Bortsett fra de tre traverseringene ovenfor, er det en annen traverseringsrekkefølge som kalles grenseovergang.

Java-program for å krysse inorder, preorder og 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(); } } 

Produksjon:

 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 

I tillegg til operasjonene ovenfor, kan vi også utføre operasjonene som stor node, minste node og summen av alle noder.

Java-program for å finne den største noden i binært tre

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

Produksjon:

solfylt deol alder

 Largest element in the binary tree: 99 

Java-program for å finne den minste noden i binært tre

Algoritme

1. Definer nodeklasse som har tre attributter nemlig: data, venstre og høyre. Her representerer venstre det venstre barnet til noden og høyre representerer det høyre barnet til noden.
2. Når en node er opprettet, vil data overføres til nodens dataattributt, og både venstre og høyre vil bli satt til null.
3. Definer en annen klasse som har en attributtrot.
   Rotrepresenterer rotnoden til treet og initialiser den til null.

smallestElement()vil finne ut den minste noden i binærtreet:
1. Den sjekker om roten er null , som betyr at treet er tomt.
2. Hvis treet ikke er tomt, definer en variabel min som vil lagre temps data.
3. Finn ut minimumsnoden i venstre undertre ved å kalle smallestElement() rekursivt. Lagre den verdien i leftMin. Sammenlign verdien av min med leftMin og lagre minimum to til min.
4. Finn ut minimumsnoden i høyre undertre ved å kalle smallestElement() rekursivt. Lagre den verdien i rightMin. Sammenlign verdien av min med rightMin og lagre maksimalt to til min.
5. På slutten vil min holde den minste noden i det binære treet.

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

Produksjon:

 Smallest element in the binary tree: 1 

Java-program for å finne den maksimale bredden til et binært tre

Algoritme

1. Definer nodeklasse som har tre attributter nemlig: data venstre og høyre. Her representerer venstre det venstre barnet til noden og høyre representerer det høyre barnet til noden.
2. Når en node er opprettet, vil data overføres til dataattributtet til noden, og både venstre og høyre vil bli satt til null.
3. Definer en annen klasse som har en attributtrot.
   Rotrepresenterer rotnoden til treet og initialiserer den til null.

1. Variabel maxWidth vil lagre det maksimale antallet noder tilstede på et hvilket som helst nivå.
2. Køen brukes for å krysse binært tre nivåvis.
3. Den sjekker om roten er null, noe som betyr at treet er tomt.
4. Hvis ikke, legg til rotnoden i køen. Variable nodesInLevel holder styr på antall noder på hvert nivå.
5. Hvis nodesInLevel > 0, fjern noden fra forsiden av køen og legg til venstre og høyre underordnet i køen. For den første iterasjonen vil node 1 bli fjernet og dens underordnede noder 2 og 3 vil bli lagt til i køen. I den andre iterasjonen vil node 2 bli fjernet, dens barn 4 og 5 vil bli lagt til i køen og så videre.
6. MaxWidth vil lagre max(maxWidth, nodesInLevel). Så, på et gitt tidspunkt, vil det representere det maksimale antallet noder.
7. Dette vil fortsette til alle nivåene i treet er krysset.

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

Produksjon:

 Maximum width of the binary tree: 4